Forum de mathématiques - Bibm@th.net

/* -----------------------------INVERSE MODULAIRE -----------------

Créé le 2 Mars 2009
par Shengao
script permettant le calcule de l'inverse modulaire d'un nombre

--------------------------------------------------------------------
composition:
 fonction modulaire: saisie du nombre et de son modulo, appel de fonction plusgrandiv(pgcd) si pgcd=1 appel de
                    calculinverse, affiche l'inverse du nombre et donne k.

 fonction plusgrandiv: calcul du pgcd du nombre et de son modulo
                       (pour calculer l'inverse de a mod m il faut que a soit premier avec m)

 fonction calculinverse: calcule l'inverse du nombre

*/

int plusgrandiv(int nombre1, int nombre2,int *pgcd)
{
    int reste;

    do
    {
    reste = nombre1%nombre2;

    nombre1=nombre2;//décalage pour réaliser euclide

    nombre2 = reste;//décalage pour réaliser euclide

    } while (nombre2 != 0);//tant que le reste est non nul
    *pgcd=nombre1;//puisque nombre1 est désormais le pgcd

    }

void calculinverse(int nombre, int modulo)
{

    int a;    //1+ modulo*k
    int k;    // k désigne le nombre de fois que le modulo doit être multiplier
    int m;    // reste après le modulo
    int b;    //b est l'inverse modulaire du nombre

 k=-9999999;//n'a pas encore bien réfléchi sur la faleur la plus approprier à affecter a k
  do
  {
        k++;

        a=1+modulo*k;
        m= a % nombre;

    }while (m != 0);

    b = a/nombre;
    printf("\nl'inverse de %d par modulo %d est %d avec k= %d\n",nombre,modulo,b,k);
}

int modulaire(void)
{

    int a,k,m,b,modulo,nombre,pgcd;

printf("entrer le chiffre dont on cherche l'inverse\n");
scanf("%d",&nombre);
scanf("%*c");
printf("entrer modulo\n");
scanf("%d",&modulo);
scanf("%*c");

plusgrandiv(nombre,modulo,&pgcd);
printf("%d",pgcd);

if(pgcd==2)
    calculinverse(nombre,modulo);
else
   printf("attention %d, n'est pas premier avec %d, l'inverse de %d n'as pas de solution dans modulo %d",nombre,modulo,nombre,modulo);

}

int main()
{
    modulaire();
    return 0;
}