Algorithme d'euclide etendu

Commenter

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

S'inscrire maintenant

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.

Du même auteur (nickydaquick)