Vous n'êtes pas identifié.
// 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 .
Hors ligne
Hello,
Comme tu l'as écrit, le but de l'algorithme est de résoudre
p_i*a0 + q_i*b0 = c_i
avec c minimum. On peut utiliser les propriétés de linéarité de ce système pour l'écrire sous forme de matrice augmentée S:
( p q a ) ( r s b )
.
On calcule l'étape suivante S' = M * S, ou M est:
( 0 1 ) ( 1 -Q*r )
Note que cette transformation conserve l'invariant, et que l'on a bien
r' = p - Q*r
s = q - Q*r
c = a - Q*b
la dernière découle de la définition c = a % b (équivalente à a = Q*b + c). Comme on à 0 < c < b, la termination de l'algorithme est garantie.
PS: le commentaire indique que ce serait du javascript. JavaScript est trop lent pour faire du RSA sur des clefs de taille réelle.
Hors ligne
On calcule l'étape suivante S' = M * S, ou M est:
Code:
( 0 1 )
( 1 -Q*r )
Heu oui ok d'accord mais je comprends pas trop comment on multiplie une matrice 2*3 (S) par une 2*2 (M)
Hors ligne
Je suis pas sur d'avoir bien compris ton problème, je crois que c'est dans la mutliplication M*S.
Quand tu multiplie 2 matrices, elles ne doivent pas forcément être carré.
Dans ce cas :
(2x2)*(2x3)
Ce qui est important c'est que les deux chiffres du millieu sont égaux (dans ce cas c'est OK).
Donc il est possible de multiplier ces deux matrices.
Par contre S*M n'est pas possible : (2x3)*(2x2) car 2 n'est pas égal à 3 !
Il y a plus de détail ici : http://fr.wikipedia.org/wiki/Produit_matriciel
Un peu hors sujet :
Il existe ce très bon livre sur la cryptographie (avec RSA) : http://www.vsmp.ch/crm/ed_cahier_02.htm
C'est publié par la commision romande de math. On l'avait utilisé au lycée. Il faut juste quelque notion très basique de théorie des nombres.
Dernière modification par tguillod (30 Dec 2007 13:36:05)
Hors ligne
Si l'approche matricielle te perturbe, tu peux voir ça comme la résolution d'un système d'équations à deux inconnues "par addition", c'est a dire que tu multiplies les coefficients d'une des équations par Q*r puis la soustrait de l'autre. Le but est que la dernière colonne corresponde à l'algorithme d'Euclide, pour converger le plus vite possible vers le GCD.
Hors ligne