Forum de mathématiques - Bibm@th.net

RideOrDie

Invité

a^b mod n rapidement

Bonjour,
J'aimerais savoir comment vérifier cette égalité : 17 = 73^7 mod 77 en maximum 4 opérations.
C'était une question de partiel pour vérifier une signature RSA.
Merci !

cube

Invité

Re : a^b mod n rapidement

Bonjour,

Je suppose qu'il faut opérer sur des entiers et que par "opération" on entend "multiplication modulo 77".
alors :
x2=73*73 [77]=16
x4=x2*x2 [77]=25
x6=x4*73 [77]=15
x7=x6*73 [77]=17

yoshi

Modo Ferox

Inscription : 20-11-2005

Messages : 16 989

Re : a^b mod n rapidement

Bonjour,

Ma proposition, pas très loin de celle de Cube :

[tex]73 \equiv -4 \;[77][/tex]

[tex]73^3 \;\equiv (-4)^3 \;[77][/tex] soit [tex]73^3 \;\equiv -64 \;\equiv 13\;[77][/tex]

[tex]73^6 ≡ (13)^2 \; [77][/tex] soit [tex]73^6 \;\equiv 169 \;\equiv 15\;[77][/tex]

[tex]73^7 ≡ 15 \times 73 = 15\times (-4)\;[77][/tex] soit [tex]73^7 \;\equiv -60 \;\equiv 17 \;[77][/tex]

@+

---

Arx Tarpeia Capitoli proxima...

RideOrDie

Invité

Re : a^b mod n rapidement

Merci pour vos réponses :)