Algorithme d'Euclide

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
}