Résoudre cette équation, ou l'inverse modulo

[Boublita]

Bonjour,
Depuis peu je m'interesse à RSA, la crypto.
Et je dois calculer un nombre que l'on nomme exposant de déchiffrage.
Ce nombre est d:
ed mod((p-1)(q-1)) = 1

Donc moi je cherche d sachant que p et q sont connus et sont premiers, mais surtout la démonstration pour comprendre car la réponse est facilement trouvable sur internet c'est:
ed = -1 mod((p-1)(q-1))
e^-1mod((p-1)(q-1))=d

Tout d'abord je ne comprend comment on arrive à ceci, et e^-1 ne signifie pas [I]puissance -1[/], car sinon le truc fonctionne pas et je ne comprend que moin ^^

Merci de votre aide
-----

[invitebb921944]

Bonjour !
e^(-1) est l'inverse de e dans Z/(p-1)(q-1)Z
Par exemple, résoudre
3x=2mod(7)
revient à résoudre
x=3mod(7)

En fait, on sait que 3*5mod(7)=15mod(7)=1 (5 est l'inverse de 3 dans Z/7Z)

Donc
3x=2mod(7)
<=>
3*5x=2*5mod(7)
<=>
15x=10mod(7)
<=>
x=3mod(7)

[invite1237a629]

Bonjour,

J'ai eu un cours sur ça et on m'a donné les méthodes générales d'étude. Si cela peut vous intéresser... :

2 personnes A et B échangent un message.
Soit n un nombre quelconque.
On calcule , qui est l'indicatrice d'Euler.

• Parenthèse :
  
  (décomposition en facteurs premiers)
  
  D'où on peut dire que

Puis, on a e tel que pgcd(e,)=1

Donc,

Ce groupe est le groupe inversible, contenant tous les nombres premiers avec phi(n).
Donc il existe un inverse de e dans ce groupe, d.

ed = 1 dans

La clé publique est : (n,e)

La clé privée est : (,d)

Soit un message M envoyé.

Le message codé envoyé (et donc reçu par l'autre) est
Donc

Que ce soit M ou C, on le "simplifie" en se plaçant dans



Pour résumer, l'étape la plus "ardue" est peut-être de trouver l'inverse de e, d, dans l'ensemble désiré.