Forum de mathématiques - Bibm@th.net

shengao

Membre

Inscription : 26-02-2009

Messages : 16

[C] Programme calculant l'inverse modulo n d'un nombre

Bonjour,

Voici un petit programme mettant en pratique ce que j'ai appris en crypto et arithmétique ces 5 derniers jours (pouvant donc comporter quelques faiblesses sur certaines méthodes)

Encore merci a yoshi.

#include <stdio.h>
#include <stdlib.h>

/* -----------------------------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;
}

Frank

Invité

Re : [C] Programme calculant l'inverse modulo n d'un nombre

LOL, comme c'est bien crade... ET pas du tout optimisé.. Faut utiliser l'algo d'euclide étendu..

yoshi

Modo Ferox

Inscription : 20-11-2005

Messages : 17 385

Re : [C] Programme calculant l'inverse modulo n d'un nombre

Re,

Le post date de 2009... 3 ans déjà !
Son auteur ne repassera sûrement pas, et il a précisé qu'il était débutant...
D'autres oui...
Alors, tu oublies qu'on est toujours le "crade" de quelqu'un.
Pourquoi cette moquerie ?

Et puisque ton intervention ne fait pas avancer d'un pouce la connaissance, je t'invite et incite vigoureusement à publier ta version : c'est au pied du mur qu'on voit le maçon dit le proverbe...
Je préfère encore dire comme en Italie :
A chi consiglia non duole il capo dont une traduction littérale est : A celui qui conseille la tête ne fait pas mal...

@+

.