Algorithme d'euclide etendu

Soyez le premier à donner votre avis sur cette source.

Snippet vu 21 267 fois - Téléchargée 30 fois

Contenu du snippet

Voici une implementation tres simple de l'algorithme d'Euclide Etendu. L'algorithme consiste a trouver pour 2 entiers a et b , 2 autres entiers x et y tels que ax + by = pgcd(a,b). Cette formule est utile en cryptographie RSA, pour la generation de cle de decryptage pour une cle de cryptage E donnee.

Il s'agit de ma 2eme source, soyez indulgents je vous en prie ... j'attends vos critiques avec impatience.

Source / Exemple :


int find_pgcd(int a , int b)
{
	if(a==0)
		return b;
	if(a<b)
		return find_pgcd(b%a,a);
	else
		return find_pgcd(a%b,b);
}

void algorithme_euclide_ex(int a , int b, int* x, int* y)
{
	/******************************************************
	*

  • objectif : retourner x et y tels que
  • ax + by = pgcd(a,b);
  • avec a <= b
                                                                                                              • /
// posons y1 = -y int x1,y1; int x2,y2; int x3,y3; int status; int reste; int quotient; int pgcd; char positionChangeante; x1 = y1 = 0; x2 = y2 = 0; x3 = y3 = 0; //reordonnons a et b if(a>b) { a ^= b; b ^= a; a ^= b; } // a ce niveau a est inferieur ou egal a b pgcd = find_pgcd(a,b); reste = b%a; quotient = b/a; status = 1; //prochaine mise a jour , les variables x1 , et y1; //on se met a la position bx + ay1 [ notre but c (ax + by1) <= positionChangeante = 0] positionChangeante = 1; //tant que l'on progresse vers la decouverte du pgcd de a et b sans atteindre 0 comme reste while((reste!=pgcd) && (reste!=0)) { switch(status) { case 1://mise a jour des variables x1 , et y1; if(!x1)// il s'agit de la premiere mise a jour des variables x1 et y1 { x1 = 1; y1 = quotient; } else { x1 = x2 + quotient*y3; y1 = quotient*x3 + y2; } status = 2;//prochaine mise a jour , les variables x2 , et y2; break; case 2://mise a jour des variables x2 , et y2; if(!x2)// il s'agit de la premiere mise a jour des variables x2 et y2 { x2 = 1+quotient*y1; y2 = quotient; } else { x2 = x3 + quotient*y1; y2 = quotient*x1 + y3; } status = 3;//prochaine mise a jour , les variables x3 , et y3; break; case 3://mise a jour des variables x3 , et y3; x3 = x1 + quotient*y2; y3 = quotient*x2 + y1; status = 1;//prochaine mise a jour , les variables x1 , et y1; break; } // les prochains operateurs : a et b seront , le b%a et a b = a; a = reste; reste = b%a; quotient = b/a; positionChangeante = !positionChangeante;//on change la position des coefficients } if(status == 1) // si on sort avant la mise a jour de x1 et y1 { if(!x1)//on est pas entre dans la boucle { if(b%a==0)// cas de a et b / a divise b {
  • x = 1;
  • y = 0;
} else // cas de b%a = pgcd(a,b) {
  • x = -1;
  • y = -1;
} } else //execute le calcul des variables x1, y1 mais dans *x et *y {
  • x = x2 + quotient*y3;
  • y = quotient*x3 + y2;
} } else if(status == 2) //execute le calcul des variables x2, y2 {
  • x = x3 + quotient*y1;
  • y = quotient*x1 + y3;
} else if(status == 3) //execute le calcul des variables x3, y3 {
  • x = x1 + quotient*y2;
  • y = quotient*x2 + y1;
} //si on est arrive a un changement de position , intervertir les coefficients if(positionChangeante && x1) {
  • x ^= *y;
  • y ^= *x;
  • x ^= *y;
} // a ce niveau *y contient y1 / y1 = -y <=> *y = -y
  • y = 0 - *y; // reajuste y , ce qui donne *y = y
}

Conclusion :


Enjoy it :D

A voir également

Ajouter un commentaire

Commentaires

svenstek
Messages postés
5
Date d'inscription
jeudi 8 mai 2008
Statut
Membre
Dernière intervention
17 mars 2010
-
Bonjour je cherche a ecrire un programme en C qui permet de calculer le pgcd de deux nombres quelconques et de aussi de calculer les coefficients de Bezout avez vous une idée ?
nickydaquick
Messages postés
416
Date d'inscription
vendredi 31 janvier 2003
Statut
Membre
Dernière intervention
19 décembre 2013
1 -
Merci Pamaury. Ton algorithme est en effet tres efficace. Je dirais meme que C'est l'algorithme pour les coefficients de Bezout. Moi j'ai en fait tente une autre approche en utilisant une formule tire d'une recurrence par des suites numeriques.
Merci Pamaury , pour ton commentaire.
Pamaury
Messages postés
341
Date d'inscription
jeudi 3 avril 2003
Statut
Membre
Dernière intervention
17 juin 2008
2 -
moi je t'ai mis un algo dans mon précédent message et il me semble qu'il est plus simple que le tiens mais je me trompe . En tout cas il est en récursif .
nickydaquick
Messages postés
416
Date d'inscription
vendredi 31 janvier 2003
Statut
Membre
Dernière intervention
19 décembre 2013
1 -
Merci pour tous vos commentaires ... Je suis d'avis avec vous que le recursif est plus couteux que l'iteratif . Seulement comme l'indique le titre de ma source mon but n'est pas d'ecrire une fonction trouver_pgcd , mais trouver les coefficients de Bezout grace a l'algorithme d'euclide etendu. J'aimerais bien avoir des commentaires la dessus. Et en passant , trouver un pgcd c faire des soustractions successives :D . J'attends vos commentaires avec impatience sur mon algorithme d'euclide Etendu.
Merci et aurevoir
BruNews
Messages postés
21042
Date d'inscription
jeudi 23 janvier 2003
Statut
Modérateur
Dernière intervention
21 août 2019
16 -
La récurrence implique des passages de params et appels de fonction, l'empilage des params est très couteux. Un algo en itératif correctement écrit DOIT être plus performant car il n'a pas tout ces emplilages dépilages.

Vous n'êtes pas encore membre ?

inscrivez-vous, c'est gratuit et ça prend moins d'une minute !

Les membres obtiennent plus de réponses que les utilisateurs anonymes.

Le fait d'être membre vous permet d'avoir un suivi détaillé de vos demandes et codes sources.

Le fait d'être membre vous permet d'avoir des options supplémentaires.