probléme rsa

Question

// Ce programme ne fonctionne qu'avec des entiers naturels
// demande les données à l'utilisateur et convertit les chaînes de caractères en entiers
var a = parseInt(prompt("Entrer un entier naturel  a",0))
var b = parseInt(prompt("Entrer un entier naturel  b",0))

// On sauvegarde les valeurs de a et b.
a0 = a;
b0 = b;
// Initialisations. On laisse invariant p*a0 + q*b0 a et  r*a0 + s*b0 b.p 1; q 0;r 0; s 1;

// La boucle principale:
while (b != 0) { 
  c = a % b;
  quotient = Math.floor(a/b);  //Javascript n'a pas d'opération de division entière.
  a = b;
  b = c;  nouveau_r p - quotient * r; nouveau_s q - quotient * s;  p r; q s;  r nouveau_r; s nouveau_s;
}

// Affiche le résultat.

alert("pgcd(" + a0 + "," + b0 + ")=" + p + "*" + a0 + "+(" + q + ")*" + b0 + "=" + a)

Bonjour
, j'ai un petit problème avec cette algorithme qui permet de trouver
les deux coefficients de Bezout , est ce que quelqu'un pourrait me dire
comment on trouve les deux coefficient avec ces deux lignes :
nouveau_r = p - quotient * r; 
nouveau_s = q - quotient * s;

Algo trouvé sur Wikipédia  : (http://fr.wikipedia.org/wiki/Algorithme … C3%A9tendu)

je ne comprend pas trop comment en fesant :
nouveau_r = p - quotient * r;
nouveau_s = q - quotient * s;

On à les coeficient intermédiaire de bezout .

Voila un screen que j'ai fais :

La valeur a affiche 1 * 120 + 0 * 23
Resultat de l'operation entre 120 et 23
Le reste 5
Le quotient 5
nouvelle valeur de a , l'ancien diviseur 23
nouvelle valeur de b , le nouveau reste 5
Valeur de nouveau_r u 1 - quotient 5 * r 0 =1 ->>>>>> je comprends pas pq ca marche ?
Valeur de nouveau_s v 0 - quotient 5 * s 1 =-5
nouvelle valeur de u 0
nouvelle valeur de v 1
nouvelle valeur de r 1
nouvelle valeur de s -5
-----------------------------
La valeur a affiche 0 * 120 + 1 * 23
Resultat de l'operation entre 23 et 5
Le reste 3
Le quotient 4
nouvelle valeur de a , l'ancien diviseur 5
nouvelle valeur de b , le nouveau reste 3
Valeur de nouveau_r u 0 - quotient 4 * r 1 =-4
Valeur de nouveau_s v 1 - quotient 4 * s -5 =21
nouvelle valeur de u 1
nouvelle valeur de v -5
nouvelle valeur de r -4
nouvelle valeur de s 21
-----------------------------
La valeur a affiche 1 * 120 + -5 * 23
Resultat de l'operation entre 5 et 3
Le reste 2
Le quotient 1
nouvelle valeur de a , l'ancien diviseur 3
nouvelle valeur de b , le nouveau reste 2
Valeur de nouveau_r u 1 - quotient 1 * r -4 =5
Valeur de nouveau_s v -5 - quotient 1 * s 21 =-26
nouvelle valeur de u -4
nouvelle valeur de v 21
nouvelle valeur de r 5
nouvelle valeur de s -26

Je me suis servi d'un exemple comme celui de wikipedia avec 120 et 23 .

nickydaquick · Answer

Salut,
algorithme d'euclide etendu : http://www.cppfrance.com/codes/ALGORITHME-EUCLIDE-ETENDU_36400.aspx
tu trouveras aussi dans les discussion une implementation recursive des coefficients de Bezout

 je suis heureux de faire partie d'une grande famille ...!

Probléme rsa

1 réponse

Votre réponse

Discussions similaires