Cryptage RSA + nombre premier

[plotix]

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.

[invité576543]

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?

Cordialement,

[plotix]

Non pas vraiment.
Pourrais-tu détailler les calculs pour me montrer comment trouver d ?

Merci

[invité576543]

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...

Cordialement,

[plotix]

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...

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

[Arkangelsk]

Salut,

Quelle est la particularité de 71 et 1008 ?

[plotix]

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 ?

[Arkangelsk]

OK.

Bon, maintenant il s'agit de trouver et .

Tu peux utiliser pour cela l'algorithme d'Euclide : http://fr.wikipedia.org/wiki/Algorithme_d%27Euclide

[plotix]

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 ?

[Arkangelsk]

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.

[invité576543]

Je nage toujours, en quoi le couple (u,v) va m'aider ?

Si 71*u +1008*v = 1, que donne cette équation modulo 1008?

Cordialement,