Calcul de modulos

Le modulo est une opération de base dans le calcul cryptographique et des mathématiques sur les entiers: un modulo a en effet des propriétés mathématiques intéressantes et très étudiées depuis très longtemps.

Congruance et modulo sont des concepts proches. Formelement la condruance est définie par: par y mod x = (y+a*x) mod x. Le modulo est quant à lui est le reste de la division entière: 0 < b < x, (a*x+b) mod x = b .

On peut donc préparer deux façon de calculer le modulo: la façon naïve et la façon sioux.

La façon naïve consiste à se rappeler que les congruances sont définies à une constante près. Si on ajoute / soustrait une constante alors on atteint un algorithme qui colle à la définition, qui est sans doute le plus simple à démontrer. Cette manoeuvre est cependant très couteuse en calculs dès que a (dans la formule (a*x+b) mod x) est grand.

La facon la plus sioux est d'utilisé la propriété "reste de la division". On verra que ce reste se calcule très simplement et rapidement.

Le langage C offre un opérateur tout fait. On verra comment il est calculé !

#include < stdio.h >
#include < stdlib.h >
#include < sys/time.h > 
#include < string.h > 
struct timeval tim; 
double t1, t2; 

/* pour demarer le décompte on ajoute à son code */ 
void chrono_start(){ 
 gettimeofday(&tim, NULL); 
 t1=tim.tv_sec+(tim.tv_usec/1000000.0); 
} 

/* pour arreter le décompte un sime appel à stop suffit */ 
double chrono_stop(){
 gettimeofday(&tim, NULL);
 t2=tim.tv_sec+(tim.tv_usec/1000000.0);
 return t2 - t1;
}

 /** le modulo avec une soustraction */
int modulo_sou(int a, const int b){
 do{
 a = a-b;
 }while( a >= b );
 return a+b;
 }

 /** le modulo avec une addition */
 int modulo_som( const int a, int b){
 int tmp = b ;
 while( tmp < a ){
  tmp=tmp + b; 
 } 
 return a - tmp +b;
}

 /** le modulo avec une division */
int modulo_div(int a, int b){
 int tmp = a/b;
 return a - b*tmp;
}


/** le modulo avec l'operateur */
int modulo_ope(int a, int b){
 return a % b;
 } 

 /** */ 
double test_ope(int tab[], int round){
 double t;
 int a,i;
 chrono_start();
 for ( a = 0; a < 64; a++){
  for ( i = 1; i < round; i++){
  tab[i]=modulo_ope(i,7+a);
  }
 }
 t = chrono_stop();
 for ( i = 1; i < round; i++){a = tab[i];}
 return t/64;
 } 

 /** */ 
double test_div(int tab[], int round){
 double t;
 int a,i;
 chrono_start();
 for ( a = 0; a<64; a++){
  for ( i = 1; i < round; i++){
  tab[i]=modulo_div(i,7+a);
  }
 }
 t = chrono_stop();
 for ( i = 1; i < round; i++){a = tab[i];}
 return t/64;
 } 
 /** */ 
void affiche(int a){
 printf("résultat: %d.n",a); 
} 
 /*
 printf("operateur ");
 affiche(modulo_ope(177,200));
 printf("division ");
 affiche(modulo_div(177,200));
 printf("somme ");
 affiche(modulo_som(177,200));
 printf("soustration ");
 affiche(modulo_sou(177,200));
*/

int main(void){
 const int MAX = 2090000;
 int tab[MAX+1];
 int round;
 printf("< table style="border: 1px solid gray;">n");
 printf("< tr >nt< td>nombre d'essais< / td >nt< td >operateur %%< / td >nt< td >perso< / td >n< / tr >n");
 round = 500; printf("< tr >nt< td > %d < / td >n",round);
 printf("t< td > %f< / td >n", test_ope(tab,round));
 printf("t< td > %f< / td >n", test_div(tab,round));
 printf("< / tr >n");
 round = 5000;
 printf("< tr >nt< td > %d < / td >n",round)
 printf("t< td > %f< / td >n", test_ope(tab,round));
 printf("t< td > %f< / td >n", test_div(tab,round));
 printf("< / tr >n");
 round = 50000;
 printf("< tr >nt< td > %d < / td >n",round);
 printf("t< td > %f< / td >n", test_ope(tab,round));
 printf("t< td > %f< / td >n", test_div(tab,round));
 printf("< / tr >n");
 round = 50000;
 printf("< tr >nt< td > %d < / td >n",round);
 printf("t< td > %f< /td >n", test_ope(tab,round));
 printf("t< td > %f< /td >n", test_div(tab,round));
 printf("< / tr >n");
 round = 500000;
 printf("< tr >nt< td > %d < / td >n",round);
 printf("t< td > %f< / td >n", test_ope(tab,round));
 printf("t< td > %f< / td >n", test_div(tab,round));
 printf("< / tr >n"); round = 1000000; 
 printf("< tr >nt< td > %d < / td >n",round);
 printf("t< td > %f< / td >n", test_ope(tab,round));
 printf("t< td > %f< / td >n", test_div(tab,round));
 printf("< / tr >n");
 round = 2000000;
 printf("< tr >nt< td > %d < / td >n",round);
 printf("t< td > %f< / td >n", test_ope(tab,round));
 printf("t< td > %f< / td >n", test_div(tab,round));
 printf("< / tr >n");
 round = MAX;
 printf("< tr>nt< td > %d < / td >n",round);
 printf("t< td > %f< / td >n", test_ope(tab,round));
 printf("t< td > %f< / td >n", test_div(tab,round));
 printf("< / tr >n"); printf("< / table >n");
 return 0;
} 

On note que dans ce code la sortie est formatée en xhtml avec des espaces supplémentaires à cause de l'éditeur, pareil pour les \n qui sont mangés en 'n' ... bref.

Ci dessous sans l'optimisation, l'exécution du code donne les résultats suivants. Les valeurs sont à comprendre relativement les unes aux autres et non pas de réelle valeurs intrisèques

J'ai décidé de ne pas montrer les résultats d'exécution des fonctions modulo_sou(int a, const int b) modulo_som( const int a, int b) car ses deux algo issues de la méthode naïve n'ont pas de résultats dans des temps raisonnables (complexité polynomiale de degré deux).

sans l'optimisation de code, les temps d'exécutions sont:

avec l'optimisation de code -O3, les temps d'exécutions sont

Attention! avec l'optimisation on rencontre un problème: le code inutile est supprimé. (le compilateur détecte les initialisations de variable qui ne sont pas réutilisée ). Ainsi pour lutter contre cette comportement on ajoute la ligne:

for ( i = 1; i < round; i++){a = tab[i];}