Bonjour , d'après la théorie RSA , on a :
Choisir deux grands nombres premiers, p et q et calculer le produit, il faut choisir également un entier aléatoire e tel que e et ((p-1).(q-1)) soient premiers entre eux.
Mais pourquoi e et p-1 * q-1 doivent-ils être premier entre eux ?
Merci
salut,
e et (p-1)(q-1) doivent être premiers entre eux pour que e soit inversible modulo (p-1)(q-1).
Cet inverse sera alors un entier d tel que ed= 1 modulo (p-1)(q-1), qui servira lors du déciffrement au possesseur de la clef privée.
e et (p-1)(q-1) doivent être premiers entre eux pour que e soit inversible modulo (p-1)(q-1).
Heu c'est-à-dire?
Soit l'anneau des entiers modulo n. Soit p un élément de cet anneau (donc une classe modulo n). p admet un inverse (pour la loi * sur l'anneau) si et seulement si l'entier p associé à cette classe est tel que p et n sont premiers entre eux.
Entre autre, cela signifie que si n est premier, l'anneau ci-dessus est un corps
Démonstration :
_ supposons p inversible ; alors il existe une classe q telle que p*q = 1 (1 est la classe de 1). Je note pareil les entiers représentatifs des classes, donc ici p et q. On a pq=1 modulo n donc cela signifie que n divise (pq-1) : il existe un entier k tel que pq-1=nk : p*q+n*k = 1 donc d'après le théorème de Bezout on a bien pgcd(n,p)=1
_ supposons pgcd(p,n)=1 : toujours d'après le théorème de Bezout il existe deux entiers k et r tels que pr+kn = 1 : on a donc modulo n pr=1 : p est inversible et son inverse est r (en tant qu'élément de l'anneau des enties modulo n bien sûr)
CQFD
