Comme des milliers de personnes, recevez gratuitement chaque semaine << Forum maths || En bas
Calcul inv et modulo
Message de antoine posté le 12-04-2009 à 12:56:40 (S | E | F)
Bonjour,
J'ai un petit soucis pour appliquer l'algorithme d'Euclide étendu (inv et modulo).
Je ne trouve jamais le même résultat que sur le site Lien Internet
par exemple :
je cherche inv (13) mod 27
27 = 2 x 13 + 1
13 = 13 x 1 + 0
ensuite on fait
1 = 1 x 27 - 2 x 13
le site me donne 25 et je ne vois pas d'ou cela vient (27 - 2 ?)
Enfin je dois mal m'y prendre à un moment...
un autre exemple :
inv 5 mod 17
17 = 3 x 15 + 2
5 = 2 x 2 + 1
2 = 2 x 1 + 0
1 = 1 x 5 - 2 x 2
1 = -2 x 17 + 7 x 5
Le site me donne 7 en résultat.
Pouvez vous m'aider, cela serait cool, car j'ai cherché sur différents
sites sans réponse, je dois mal m'y prendre.
Message de antoine posté le 12-04-2009 à 12:56:40 (S | E | F)
Bonjour,
J'ai un petit soucis pour appliquer l'algorithme d'Euclide étendu (inv et modulo).
Je ne trouve jamais le même résultat que sur le site Lien Internet
par exemple :
je cherche inv (13) mod 27
27 = 2 x 13 + 1
13 = 13 x 1 + 0
ensuite on fait
1 = 1 x 27 - 2 x 13
le site me donne 25 et je ne vois pas d'ou cela vient (27 - 2 ?)
Enfin je dois mal m'y prendre à un moment...
un autre exemple :
inv 5 mod 17
17 = 3 x 15 + 2
5 = 2 x 2 + 1
2 = 2 x 1 + 0
1 = 1 x 5 - 2 x 2
1 = -2 x 17 + 7 x 5
Le site me donne 7 en résultat.
Pouvez vous m'aider, cela serait cool, car j'ai cherché sur différents
sites sans réponse, je dois mal m'y prendre.
Réponse: Calcul inv et modulo de antoine, postée le 15-04-2009 à 23:00:24 (S | E)
personne ne sait ?
Réponse: Calcul inv et modulo de iza51, postée le 16-04-2009 à 06:54:32 (S | E)
Bonjour,
l'algorithme donné donne bien 25 comme résultat à inv(13) [mod 27]quand on fait les calculs demandés "à la main"
Pour espérer trouver la même réponse, il faut suivre les étapes de l'algorithme
b=13 et n=27
n0=n=27
b0=b=13
t0=0
t=1
q=E(n0/b0)=E(27/13)=2
r=n0-qb0=27-2*13=1
début boucle: r>0 donc temp=t0-qt=-2
temp <0
donc nouveau temp= n-((-ancien (temp) mod 27)=27-(2 mod 27)=27-2=25
t0=t=1
t=25
n0=13
b0=1
q=E(n0/b0)=E(13/1)=13
r= 13 -13*1 = 0
fin de la boucle
inv(b) mod n est égal à t
ici inv(13 )mod 27 est égal à 25
Réponse: Calcul inv et modulo de ajl, postée le 16-04-2009 à 10:56:12 (S | E)
Bonjour,
Une tentative de réponse :
soit a l'inverse de 13 modulo 27. Il faut donc que le reste de la division de 13a par 27 donne 1. Ou encore que 13a - 1 soit un multiple de 27.
Or si on prend a=-2 on trouve 13(-2)-1=-27. Or "a" doit être un nombre entier compris entre 0 et 26. Il faut donc "convertir" -2 en un nombre compris entre 0 et 26 d'où -2= 25 - 27.
On vérifie que 13(-2)=-27 peut s'écrire 13(25)=27(26) puisque -1 = 26 -27
De la même façon :
Soit b l'inverse de 5 modulo 17. Il faut que 5b-1 soit un multiple de 17.
Or 5(7)-1=34 donc b=7.
Réponse: Calcul inv et modulo de antoine, postée le 18-04-2009 à 14:02:25 (S | E)
d'accord merci beaucoup pour vos différentes réponses, j'ai enfin compris
INDISPENSABLES : 