ALGORITHME D'EUCLIDE ETENDU

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
}