Bonjour,
Dans le cadre d'un exercice de programmation, je dois re-coder le système RSA.
Je bloque au moment où je dois trouver d tel que :
71*d mod 1008 = 1
Le d à trouver est 1079 sachant que celui-ci doit être premier avec 1008.
Merci d'avance pour votre aide.
Connais-tu l'algorithme de calcul des coefficients de Bezout?Envoyé par plotix
Cordialement,
Non pas vraiment.
Pourrais-tu détailler les calculs pour me montrer comment trouver d ?
Merci
Hmm.. Si c'est un exercice, faut un minimum de travail. Un peu de recherche sur le Web à partir de l'indication devrait te donner des réponses...Non pas vraiment.
Pourrais-tu détailler les calculs pour me montrer comment trouver d ?
Merci
Cordialement,
C'est pas un exercice, c'est un bonus de mon tp d'algorithme.
C'est la partie "pour les warriors".
D'après mes recherches, bezout nous permet de trouver le PGCD de deux nombres.
Si a et b sont premiers entre eux, alors il existe des entiers relatifs u et v tels que au +bv = 1
Ca m'aide pas beaucoup...
Je précise que je n'ai pas fais spé maths
Salut,
Quelle est la particularité de 71 et 1008 ?
Ils sont premiers entre eux.
Donc on peut trouver u et v tels que
71*u +1008*v = 1
Seulement j'ai toujours du mal à comprendre on quoi ce théorème va m'aider ?
OK.
Bon, maintenant il s'agit de trouveret
Tu peux utiliser pour cela l'algorithme d'Euclide : http://fr.wikipedia.org/wiki/Algorithme_d%27Euclide
D'après l'algo d'euclide :
1008 = 71 * 14 + 14
71 = 14 * 5 + 1
1008 et 71 sont bien premiers entre eux.
On remonte :
1 = 71 - 14 *5
Or 14 = 1008 - 71 * 14
Donc 1 = 71 - (1008 -71 *14) * 5
<=> 1 = 71 - [1008 * 5 - 71 * 70]
<=> 1 = 71 - 1008 * 5 + 71*70
u = 71 et v = - 5
Je nage toujours, en quoi le couple (u,v) va m'aider ?
Le couple (u,v) que tu as trouvé est une solution particulière, il faut maintenant chercher l'ensemble des solutions de ton équation diophantienne.
Si 71*u +1008*v = 1, que donne cette équation modulo 1008?
Cordialement,
