Probleme du logarithme discret

Commenter

Contenu du snippet

ce bout de code résous le problème du logarithme discret pour les entier de certaines tailles.
c'est un essaie de code et il n'est pas tout a fais au point.
l’algorithme implémenté est celui du "PAS DE BEBE PAS DE GEANT " ou encore "BABY STEP-GIANT STEP"

Source / Exemple : 


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

typedef struct{
    int a;
    int b;
}Couple;

void afficher(){
        printf( "****************************************************************\n");
        printf( "*                                                              *\n");
         printf("*          BIENVENNUE DANS LE MONDE DU CALCUL RAPIDE           *\n");
         printf("*                EXPOSEE ARITHMETIQUE SPECIAL                  *\n");
         printf("*   INSTITUT SUPERIEUR DU SAHEL :MAROUA-CAMEROUN               *\n");
         printf("*        GROUPE I: PROBLEME DU LOGARITHME DISCRET              *\n");
         printf("*  Exposant:                                                   *\n");
         printf("*           1.NKOUDJOU TAGHEU Ghislain Arnaud                  *\n");
        printf( "****************************************************************\n");
printf("\n\n\n");

}
int modulo(int a, int b){
int r;
if(a>0) r = a%b;
else r = b - (-a)%b;
return r;
}
int inverse(int a, int b){

// déclaration et initialisation des valeurs
int q, pgdc;
int U0 = 1;
int V1 = 1;
int U1 = 0;
int V0 = 0;
int R0 = a;
int R1 = b;
int U=0, Rn, Un, Vn;

if(a==0) pgdc = b;
else{
do{
q = R0/R1;
Rn = R0-(q*R1);
R0 = R1;
R1 = Rn;
Un = U0-(q*U1);
U0 = U1;
U1 = Un;
Vn = V0-(q*V1);
V0 = V1;
V1 = Vn;
}while (R1!=0);
}
pgdc = R0;
// Affichage des résultats
if (pgdc == 1){
U=modulo(U0,b);
return U;
}
else{
return 0;
}
}

int PuissanceModulo(int x, int y, int z){
int u, v, q;
u=x%z;
v=1;
q=y;
do{
y=q/2;
if((q%2)==0) v=v%z;
else v=(u*v)%z;
v=v;
u =(u*u)%z;
q=y;
}while(y!=1);
return (u*v)%z;
}
// verifier si le nombre à entrer est premier
int pgdc( int a, int b){
int r, q, pgdc;
do{
q = a/b;
r = a -(b*q);
a = b;
pgdc = b;
b = r;
}while (r!=0);
return pgdc;
}

int calculPuissanceRapide(int g, int n, int m){
    int v=1, x;
do{
if(n%2==0) v = v%m;
else v = (v*g)%m;
n = n/2;
g =(g*g)%m;
}while(n!=1);
x = modulo(g*v,m);
return x;
}

void tri_rapide(Couple tab[], int taille)
{
    Couple temoin, temp;
    int ind_inf, ind_sup;

    if (taille > 1)
    {
        ind_inf = 0;
        ind_sup = taille-1;
        temoin = tab[0];
        while(ind_inf <= ind_sup)
        {
            if ((tab[ind_inf]).a < temoin.a)
                ind_inf++;
            else
            {
                temp = tab[ind_inf];
                tab[ind_inf] = tab[ind_sup];
                tab[ind_sup] = temp;
                ind_sup--;
            }
        }
        tri_rapide(tab, ind_inf);
        tri_rapide((tab+ind_inf), taille - ind_inf);
    }

}

int logarithme(int a, int n, int p){
   // int m=sqrt(p);
   int m=8;
    int i,gamma;
    Couple couple[m];
    // On verifie si m est une puissance de 2

    for(i=0; i<m ; i++){
        (couple[i]).a = (int)pow(a,i)%p;
        (couple[i]).b = i;
    //    printf("tablo (%d,%d)",couple[i].b,couple[i].a);

    }
    printf("debut du test du tri \n");
       tri_rapide(couple, m);
         for (i=0; i<=m ; i++){
        printf("tablo (%d,%d)",couple[i].b,couple[i].a);
    }
    printf("fin du test du tri \n");
    //int inv = inverse(a,p);
   gamma = PuissanceModulo(a,m,p);
    printf("au début  gamma vaut %d\n",gamma);
   int gamma_ini=n;
   int    c,j=0,r=0;

    while(j<m){
      // printf("trouvé %d\n",j);
       for(i=0;i<m;i++){
      if((couple[i]).a==n){
           printf("voici la valeur de c %d\n",couple[i].b);
           c=couple[i].b;
           r=n;
         break;
      }
         printf("tour numero  %d\n",i);
       }
       j++;
         n= (int)(gamma_ini*pow(gamma,j))%p;
               printf("voici la valeur de n %d\n",n);
    }

      return (c-r);
}

int main()
{
    int a,n,p;
    afficher();
    printf("Hello! entrer les valeurs:\n");
     do{
printf("\n Veuillez saisir la valeur de g: ");
scanf("%d",&a);
}while(a>p);
//        printf("nombre : ");
//        scanf("%d",&a);
        printf("puissance n: ");
        scanf("%d",&n);
        printf("modulo  p: ");
        scanf("%d",&p);
        printf("Nous allons travailler dans Z/%dZ  \n",p);
        getch();
        printf("le logarithme discret est  %d\n",logarithme(a,n,p));
         printf("ou encore on peut avoir la valeur  %d \n",modulo(logarithme(a,n,p),p-1));
        printf("\n");
        printf("                   MERCI D' AVOIR ESSAYE NOTRE APPLICATION\n");

getch();
    return 0;
}

Conclusion :


je compte sur bonne bonne compréhension pour des proposition et l amélioration de ce bout de code

A voir également

S'inscrire maintenant

Vous n'êtes pas encore membre ?

inscrivez-vous, c'est gratuit et ça prend moins d'une minute !

Les membres obtiennent plus de réponses que les utilisateurs anonymes.

Le fait d'être membre vous permet d'avoir un suivi détaillé de vos demandes et codes sources.

Le fait d'être membre vous permet d'avoir des options supplémentaires.