Probleme du logarithme discret
Soyez le premier à donner votre avis sur cette source.
Snippet vu 5 906 fois - Téléchargée 19 fois
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"
je compte sur bonne bonne compréhension pour des proposition et l amélioration de ce bout de code
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
- Probleme du logarithme discret
- Calcul logarithme ✓ - Forum C# / .NET
- Logarithme puissance - Forum Visual Basic 6
- Logarithme java ✓ - Forum Java
- Logarithme - Forum VB.NET
- Conversion logarithme ✓ - Forum Visual Basic
16 avril 2015 à 20:43
Merci en avance
2 juin 2013 à 16:09
Merci et cordialement de faire avancer l'informatique.
citation
"Les codes Gouvernet le mondes par ricochet les informaticiens contiennent le monde"
20 mai 2013 à 06:19
if ((tab[ind_inf]).a < temoin.a)
devrait plutôt être:
if ((tab[ind_inf]).a <= temoin.a)
Tout bonnement parce que cela assure la "stabilité" du tri, et cela évite aussi de procéder à l'échange quand le témoin est égal à la valeur testée de l'intervalle (ce qui est vrai dès le début puisque au départ ind_inf==0 et c'est déjà la position du témoin.
Ensuite pas la peine de comparer cette position de départ : on sait que c'est déjà le témoin, la boucle devrait donc commencer à la position suivante donc remplacer:
ind_inf = 0;
par
ind_inf = 1;
Pas d'inquiétude : c'est suivi du test while() permettant de sortir de la boucle tout de suite (et on sait déjà à l'entrée de la fonction que taille > 1 donc que le témoin en position [0] est toujours présent dans l'intervalle ainsi que le suivant [1] à comparer.
Ce qui amène à une autre optimisation puisqu'on sait alors qu'il est inutile de tester au début de la boucle, mais uniquement à la fin avec:
do{...}while(ind_inf <= ind_sup);
au lieu de:
while(ind_inf <= ind_sup){...}
(en effet le premier test est déjà fait sur if(taille>1)...
Enfin pourquoi garder dans la boucle "temoin.a" via une variable de structure Couple quand temoin pourrait directement contenir la valeur comparée ?
Finalement tu n'optimises pas la récursion terminale (le langage C ne l'optimise pas automatiquement comme pour les langages fonctionnels) : normalement on utilise une boucle pour le faire. Mais ici on a deux récursions, et la récursion terminale devrait être sur la longueur d'intervalle la plus longue afin que son remplacement par une boucle réduise le plus possible les autres récursions (qui ne persisteront que sur la récussion la plus courte des deux, donc nécessiront moins d'espace annexe en pile d'appel).
Pour un tri optimal en fait dans ton algo, un meilleur candidat est le "tri de Tim" (TimSort) qui est dorénavant celui par défaut dans Perl, Java, OpenJDK, Android, etc... car il est stable, est O(n.log n) pratiquement tout le temps même dans le pire cas, et quasi linéaire en O(n) pour les cas pratiques, et optimal en terme de localité (réduction du swap, maximisation de l'efficacité des caches, réduction des I/O si tri externe, ou si la mémoire de travail est non volatile mais utilise des cellules Flash dont les cycles d'écriture doivent être réduits en maximum, réduction de l'énergie consommée, etc...). Le Timsort est un hybeide entre un tri par fusion (Mergesort), et un tri par insertion et il s'avère même en pratique plus rapide que le "tri rapide", ùême s'il demande un peu de mémoire de travail (mais en fait moins que pour les récursions du tri rapide). Le Timsort fonctionne aussi bien pour trier des vecteurs que des listes chainées.
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.