/*************************************************************************************************************************************/
/*                                                                                                                                   */
/*        C A L C U L   D U   ' PGCD '   D E   D E U X   N O M B R E S   E N T I E R S  :                                            */
/*                                                                                                                                   */
/*                                                                                                                                   */
/*        Author of '$xtc/PGCD.01$c' :                                                                                               */
/*                                                                                                                                   */
/*                    Jean-Francois COLONNA (LACTAMME, AAAAMMJJhhmmss).                                                              */
/*                                                                                                                                   */
/*************************************************************************************************************************************/

#include  <stdio.h>

extern    double    sqrt();

#define   factorisation(a,b)                                                                                                            \
                    {                                                                                                                   \
                    int       racine_carree=(int)sqrt((double)a);                                                                       \
                    int       diviseur_courant=2;                                                                                       \
                    int       nombre_de_facteurs=0;                                                                                     \
                                                                                                                                        \
                    while     (diviseur_courant <= racine_carree)                                                                       \
                              {                                                                                                         \
                              if        ((a%diviseur_courant) == 0)                                                                     \
                                        {                                                                                               \
                                        a = a/diviseur_courant;                                                                         \
                                        nombre_de_facteurs++;                                                                           \
                                        if        ((b%diviseur_courant) == 0)                                                           \
                                                  {                                                                                     \
                                                  b = b/diviseur_courant;                                                               \
                                                  pgcd_courant = pgcd_courant*diviseur_courant;                                         \
                                                  }                                                                                     \
                                        else                                                                                            \
                                                  {                                                                                     \
                                                  }                                                                                     \
                                        }                                                                                               \
                              else                                                                                                      \
                                        {                                                                                               \
                                        diviseur_courant++;                                                                             \
                                        }                                                                                               \
                              }                                                                                                         \
                                                                                                                                        \
                    if        (nombre_de_facteurs == 0)                                                                                 \
                                   {                                                                                                    \
                                   }                                                                                                    \
                    else                                                                                                                \
                                   {                                                                                                    \
                                   }                                                                                                    \
                    }

int  pgcd(x,y)
int  x,y;
     {
     int       Vx=x;
     int       Vy=y;
     int       pgcd_courant=1;
     factorisation(x,y);
     factorisation(y,x);
     return(pgcd_courant);
     }

main()
     {
     printf("\n pgcd(3,5)=%d",pgcd(3,5));
     printf("\n pgcd(24,10)=%d",pgcd(24,10));

     printf("\n pgcd(15,48)=%d",pgcd(15,48));
     printf("\n pgcd(15,50)=%d",pgcd(15,50));
                                        /* Soit :                                                                                    */
                                        /*                                                                                           */
                                        /*                  N = 15    (arbitraire...)                                                */
                                        /*                  X = 7     (arbitraire...)                                                */
                                        /*                                                                                           */
                                        /* et on cherche le plus petit R (dit "ordre de X par rapport a N") satisfaisant :           */
                                        /*                                                                                           */
                                        /*                   R                                                                       */
                                        /*                  X  = 1    modulo N                                                       */
                                        /*                                                                                           */
                                        /*                   4                                                                       */
                                        /*                  7  = 1    modulo 15                                                      */
                                        /*                                                                                           */
                                        /* d'ou :                                                                                    */
                                        /*                                                                                           */
                                        /*                  R = 4     (l'ordre de 7 par rapport a 15 est 4...)                       */
                                        /*                                                                                           */
                                        /* On pose alors :                                                                           */
                                        /*                                                                                           */
                                        /*                        R                                                                  */
                                        /*                       ---                                                                 */
                                        /*                        2         2                                                        */
                                        /*                  A = X    - 1 = 7  - 1 = 48                                               */
                                        /*                                                                                           */
                                        /*                        R                                                                  */
                                        /*                       ---                                                                 */
                                        /*                        2         2                                                        */
                                        /*                  B = X    + 1 = 7  + 1 = 50                                               */
                                        /*                                                                                           */
                                        /* On a alors :                                                                              */
                                        /*                                                                                           */
                                        /*                  PGCD(N,A) = PGCD(15,48) = 3                                              */
                                        /*                  PGCD(N,B) = PGCD(15,50) = 5                                              */
                                        /*                                                                                           */
                                        /* Or {5,3} sont les deux facteurs de 15...                                                  */
                                        /*                                                                                           */
                                        /* Ceci est le point de depart de l'algorithme quantique de factorisation de Shor...         */

     printf("\n pgcd(262144,448500)=%d",pgcd(262144,448500));
     printf("\n pgcd(262144,512)=%d",pgcd(262144,512));
     printf("\n pgcd(512,512)=%d",pgcd(512,512));
     printf("\n pgcd(512,262144)=%d",pgcd(512,262144));
     printf("\n pgcd(945,231)=%d",pgcd(945,231));
     printf("\n pgcd(231,945)=%d",pgcd(231,945));
     printf("\n");
     }