Introduction
Les nombres entiers positifs peuvent représenter toute donnée, toute information qu'un être humain peut posséder. Nous avons vu que les nombres entiers positifs peuvent être manipulés, ce qui sera très important pour des applications comme la cryptographie. Si nous voulons traiter une quantité d'information finie, il faudra se limiter à des sous-ensembles de nombres entiers. Alors, il est possible de construire des anneaux et des champs sur certains de ces ensembles. Au cœur de tous ces traitements se trouvent des opérations avec lesquelles nous sommes tous familiers: addition, soustraction, multiplication et division longue. La plupart d'entre nous ont appris à faire ces calculs à la main à l'école primaire, mais de façon "professionnelle" nous utilisons une calculatrice ou un ordinateur pour faire de l'arithmétique. Il ne faut plus y penser, "c'est fait par la machine", semble-t-il. Souvent, c'est même disponible au niveau hardware: il ne faut même plus le programmer à bas niveau: il ne faut plus expliquer à l'électronique comment faire une multiplication: les circuits qui le font sont là.
Et maintenant vient la difficulté et peut-être la surprise: le hardware a été fait pour un jeu fini de nombres entiers qui est ridiculement petit comparé à nos besoins pour nos applications. Sur toutes les machines, l'arithmétique en 32 bits est présente et presque partout, au moins au niveau des logiciels système, l'arithmétique de 64 bits est là. Un entier signé de 64 bits a une valeur positive maximale de 9 223 372 036 854 775 807. C'est largement suffisant pour la plupart des applications terrestres où les entiers servent a compter des choses. Les gens ne vont en général pas s'en apercevoir que ce qui est implémenté en hardware ou en logiciel est un anneau de taille fini au lieu de l'anneau des entiers Z. Les entiers de 32 bits ont une valeur maximale bien plus petite, à peu près 2 milliards et cela pose des problèmes, par exemple pour les comptes en banque de personnes très riches ; mais les entiers de taille 64 bits sont largement suffisants, même pour Bill Gates. Ainsi, les entiers de 64 bits sont largement suffisants pour essentiellement toutes les applications d'arithmétique. Aucun maître d'école n'a jamais eu l'idée de torturer des écoliers avec des opérations manuels contenant plus de chiffres que ceux de nombres de 64 bits (j'espère).
Seulement, les champs et anneaux finis nécessaire quand les entiers représentent des données, sont énormément plus grandes que ce qui est possible avec des nombres de 64 bits. Beaucoup de systèmes cryptographiques ont besoin de nombres qui peuvent se représenter sur 3000 bits ou plus. En fait, aucun système cryptographique actuel peut utiliser des entiers de 64 bits sauf DES, ce qui est considéré, exactement pour cette raison, considéré non sûr. La plupart des anneaux finis qu'on va utiliser en cryptographie possèdent beaucoup plus d'éléments qu'il y ait de particules élémentaires dans l'univers visible. C'est pour cela que ces anneaux ne sont jamais nécessaire quand on utilise des entiers pour compter des choses: il n'y en a pas assez dans l'univers !
Il faudra donc implémenter à la main ces opérations sur des très grands nombres en logiciel. Bien sûr, il y a de très bonnes librairies qui sont disponibles, mais pour maîtriser le sujet, il n'y pas mieux que d'y mettre les mains. C'est le but de cette contribution: implémenter de l'arithmétique de champs et anneaux finis de taille arbitraire.
Le code est fonctionnel, mais sert seulement comme illustration, et nous avons évité autant que nous pouvions, toute connaissance informatique qui peut rendre le code plus utilisable mais les algorithmes moins visibles. C'est pourquoi on s'est limité à du code C très simple. Bien sûr il y a quelques spécificités en C (par exemple, le fait de devoir passer les paramètres comme des pointeurs), mais nous avons essayé de limiter cela au stricte nécessaire pour faire marcher le code.
Représentation des nombres et systèmes numérales.
Les nombres sont des concepts mathématiques abstraits, et quand nous les écrivons, ou quand nous les utilisons dans un ordinateur, ou quand on les manipule d'une façon ou d'une autre, nous avons besoin de les représenter. Comme nous nous sommes limités à des anneaux et champs finis, à première vue, cela semble simple: il suffit d'avoir un symbole unique pour chaque élément. Cependant, il va de soi que si on parle d'anneaux contenant plus d'éléments que de particules élémentaires dans l'univers visible, ce n'est pas une méthode pratique. Déjá une liste de quelques milliers de symboles nous dépasserait. Il faut donc un système plus intelligent.
Notre système décimal actuel est basée sur le système numéral Hindu-Arabe qui peut représenter des nombres très grands avec une facilité étonnante. Son principe est l'utilisation répétée d'un ensemble de symboles de base relativement petit, et de former des n-tuples de ces symboles. Notre système décimal utilise une base avec 10 symboles de base: {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}. Ils ont des symboles individuels et on les appelle des chiffres. Un nombre est représenté par un n-tuple de ces éléments: (7, 3, 0, 5) par exemple. Chaque position dans le tuple a un poids qui est égal aux puissances successives du nombre d'éléments dans la base, ici donc 10. Ainsi, 5 a le poids de 1 (100). 0 a le poids de 10 (101). 3 a le poids de 100 (102). Et 7 a le poids de 1000 (103). Nous représentons donc le nombre 7305 avec 4 chiffres. La puissance du système Hindu-Arabe se trouve dans le fait que la plage des nombres représentés monte de façon exponentielle avec le nombre de chiffres utilisés dans le tuple ; pour le dire autrement, la complexité de la représentation ne monte que de façon logarithmique avec la taille des nombres qu'il faut représenter. La tradition veut qu'on écrive le chiffre avec le plus faible poids (1) à droite, et que les puissances montent quand on va vers la gauche dans le tuple. A gauche se trouve donc le chiffre avec le plus grand poids.
Quand on compte "vers le haut" dans un tel système numéral, c'est à dire, quand on ajoute 1, nous changeons le digit de plus faible poids (lsd) dans le suivant dans la base. Si c'est un 6, cela devient donc un 7. Quand on arrive au plus grand digit (9 donc), on le remplace par le plus petit (0), mais nous retenons qu'il faut maintenant augmenter le chiffre à la deuxième plus faible place de 1. Si celui-la est aussi égal à 9, il faut le remplacer par 0 à son tour, et retenir qu'il faut augmenter le chiffre de poids plus fort. Ceci s'arrête forcément quelque part, sauf si tuple n'est fait que de 9. Alors, il faut remplacer tous les 9 par 0, et augmenter la taille du n-tuple, pour en faire un (n+1)-tuple, où le chiffre à gauche (qui était implicitement 0) devient 1. Si nous avions [9,8,8], le suivant est [9,8,9]. Le suivant deviendra [9,9,0]. Si nous avions [9,9,9], alors le suivant deviendra un 4-tuple, égal à [1,0,0,0]. Ça, vous le saviez depuis l'école primaire. Il y a beaucoup de choses qu'il faudra se rappeler de cette époque.
Ainsi, le système Hindu-Arabe peut représenter tout nombre entier positif avec seulement 10 symboles. Dans les cas qui nous intéressent, nous voulons représenter des anneaux finis. Ainsi, nous n'avons même pas besoin de représenter des nombres arbitrairement grands. Dans un anneau cyclique, il y a un "plus grand nombre", et le suivant est "mis à 0". Ce nombre est l'ordre de l'anneau, et on l'appelle aussi le module. Le module est un nombre comme un autre, et peut donc être représenté dans le système Hindu-Arabe par un n-tuple, par exemple, [8,5,7]. Ainsi, il faudra changer notre règle du "suivant"; tout marche comme avant, sauf si on atteint [8,5,6]. Alors, le suivant est [0,0,0]. C'est ainsi qu'on représente un anneau ou un champs modulaire. L'avantage est que cette représentation est possible avec des tuples d'une taille fixe, dans notre exemple, des 3-tuples. Un anneau ou champs fini se représente avec des tuples d'une taille bien définie.
Le système Hindu-Arabe traditionnel a une base avec 10 chiffres, mais ce système peut fonctionner avec n'importe quelle base. Si la base contient deux chiffres, {0,1}, le système est le système binaire bien connu en électronique. Une base avec 16 chiffres, souvent notés {0,1,2,3,4,5,6,7,8,9,A,B,C,D,E,F} est le système hexadécimal, connu en électronique et informatique. On peut s'imaginer n'importe quelle base: il faut juste avoir des symboles pour représenter chaque chiffre de la base.
#include <stdio.h>
#define basis 10
#define nofdigits 4
#define printlevel 0
/* "number" is a structure with nofdigits digits, the normal number in the
ring structure we consider ; number1 has one more digit to allow for the
overflow when multiplying a number with a single digit and other intermediate
results ; bignum has twice as much digits, to allow for the product of two numbers
before the modulo operation ; we also need bignum1 which has one single extra digit
more than bignum for overflow results when working with the product */
typedef struct digits {unsigned int digit[nofdigits];} number;
typedef struct digitus {unsigned int digit[nofdigits + 1];} number1;
typedef struct digitis {unsigned int digit[nofdigits * 2];} bignum;
typedef struct digitas {unsigned int digit[nofdigits*2+1];} bignum1;
Dans ce morceau de code C, nous introduisons des n-tuples qui représenteront des nombres dans le système Hindu-Arabe. La taille des tuples est fixée par nofdigits, qui est mis à 4 dans cet exemple. Nous fixons la base. Ici, nous avons fixé la taille de la base à 10, mais nous pouvons augmenter la base jusqu'à la taille d'un nombre qui se représente par un entier-machine de 32 bits style C, ici donc à peu près 2 milliard.
Nous avons utilisé une structure contenant un tableau, pour que le tableau soit "à l'intérieur" du truc qui représente le nombre.
Ainsi, nous déclarons un nombre:
number mynumber;
et nous accédons à ces chiffres de la façon suivante:
mynumber.digit[0]
qui indiquera le lsd, et nous utilisons
mynumber.digit[3]
pour indiquer le chiffre numéro 4 dans le tuple, ce qui est, dans notre exemple, aussi le msd.
Le "printlevel" n'est rien d'autre que le niveau de verbosité du programme, c'est à dire, combien d'explications il imprimera sur ses opérations. Dans les commentaires de code, il est expliqué que nous avons besoin de tuples de plus grande taille pour des résultats intermédiaires, avant d'appliquer le module. Nous allons voir pourquoi nous avons parfois besoin de plus grands nombres que ceux qui "entrent" dans l'anneau.
Finalement, il faut exprimer la taille de l'anneau (ou champs) modulaire à utiliser:
number modulo = {{7,5,8}}; // warning: lsd first !
Notez qu'ici, nous n'utilisons pas la notation traditionnelle de droite à gauche. Ainsi, l'écriture en C de {7,5,8} représente le nombre 857 en notation standard. Le langage C ne permet pas d'inverser l'écriture (en VHDL, ceci aurait été possible). Nous avons deux fonctions auxiliaires qui peuvent lire des nombres de l'entrée standard, et qui peuvent imprimer des nombres sur la sortie standard (l'écran):
/* ----------------------------------------------- */
int readnum(number* x)
/* This function reads in the digits of a number from stdin */
/* The reading is from lsb to msb */
{
printf("Read digits : \n");
int i;
int mydigit;
for (i = 0; i < nofdigits ; i++)
{
scanf("%d",&mydigit);
if (mydigit < 0)
{
printf("negative digit ! \n");
return 1;
}
if (mydigit >= basis)
{
printf("digit out of range ! \n");
return 1;
}
x->digit[i] = mydigit;
}
return 0;
} // end readnum
/* ----------------------------------------------- */
void printnum(number* x)
/* this function prints out a number on stdout */
{
int i;
for (i = nofdigits - 1 ; i >= 0 ; i--)
{
printf("%d ",x->digit[i]);
}
printf("\n");
} // end printnum
/* ----------------------------------------------- */
Après ces quelques éléments techniques, nous pouvons attaquer le plat de résistance: les algorithmes d'arithmétique.
Nous allons tricher un peu: nous allons utiliser l'arithmétique de l'ordinateur pour implémenter les calculs à 1 chiffre. Comme nos chiffres sont représentés en C par des entiers machine (en C, ce sont des entiers 32 bits dans la plupart des cas, même si le standard C n'exige que 16 bits, ce qui est toujours largement suffisant pour les bases qu'on pourrait raisonnablement choisir), nous allons utiliser la machinerie d'arithmétique implémentée en hardware et au niveau système pour calculer, par exemple, la somme de deux chiffres a et b, en utilisant l'opérateur + en C. Il nous faudra bien sûr implémenter les retenus. Si nous ne voulions pas tricher, il faudrait d'abord construire les tables d'addition de taille n x n, et les tables de multiplication de taille n x n, qui contiennent la somme (et le produit), et le retenu à passer au chiffre suivant. Il faudrait aussi construire des tables de soustraction (avec les empruntes). Avec chaque système Hindu-Arabe, on peut construire ces tableaux en "comptant" sans faire d'opérations ; mais ce n'est pas pratique. C'est pour cela qu'il faut apprendre ces tables par coeur en école primaire. Ici, nous considérons que l'ordinateur a "appris ses tables" et nous utilisons donc les opérations système pour y accéder.
Soustraction
Il peut paraître étrange, mais la soustraction est plus facile à implémenter que l'addition. Allons-y:
void difnum(number* x, number* y, number* s)
/* under the condition that x and y are numbers within
the modulo ring, s is the difference of x - y in the
modulo ring */
{
int i;
int borrow;
int dd;
int ss;
int carry;
borrow = 0;
// calculation of the difference using borrowing
// but not taking into account the modular structure
if (printlevel > 0)
printf("Difference without modular structure: \n");
for (i = 0 ; i < nofdigits ; i++)
{
dd = x->digit[i] - y->digit[i] - borrow;
if (printlevel > 0)
printf("i is %d and dd is %d ",i,dd);
if (dd < 0)
{
dd += basis;
borrow = 1;
}
else
{
borrow = 0;
}
s->digit[i] = dd;
if (printlevel > 0)
printf(" --> borrow is %d and finally digit is %d \n",borrow,dd);
}
// in the case of a "negative" result,
// we add one time the modulo size.
if (borrow != 0)
{
if (printlevel > 0)
printf("Negative ! \n");
carry = 0;
for (i = 0; i < nofdigits ; i++)
{
ss = s->digit[i] + modulo.digit[i] + carry;
carry = ss / basis;
s->digit[i] = ss % basis;
if (printlevel > 0)
printf(" -> ss is %d, carry is %d and digit is %d \n",ss,carry,s->digit[i]);
}
}
} // end difnum
Notez une petite technicité: comme il faut passer les paramètres en C par référence, il faut passer les pointeurs vers des nombres. En utilisant des pointeurs vers des structures, nous accédons à leur contenu avec une flèche au lieu d'un point. On écrit donc:
x->digit[i]
au lieu de:
x.digit[i]
parce que x est un pointeur vers un nombre, et pas un nombre même.
Le mécanisme important est la soustraction, chiffre par chiffre. Nous utilisons le fait que l'ordinateur peut avoir des chiffres négatifs (des symboles supplémentaires en fait) qui ne sont pas présent dans la base des chiffres. Ceci indique qu'il faut "emprunter" chez le voisin du haut. Un emprunt de 1 est toujours suffisant pour ramener ce "chiffre négatif" dans la base.
On travaille du lsd vers le msd. Ainsi, quand nous traitons un chiffre, l'emprunte "d'en-dessous" est déjà établie, et nous pouvons en tenir compte. S'il faut emprunter quand on arrive au msd, en nombres entiers, cela voudrait dire que nous avons un résultat négatif. Mais dans une structure modulaire, cela signifie qu'il faut ajouter le module. Nous implémentons donc une addition. Ceci semble contradictoire avec ce que nous avions dit, que la soustraction est plus simple que l'addition. Mais l'addition dont nous parlons ici ne dépassera jamais le module (car nous partons d'un nombre négatif et nous ajoutons une fois le module), et c'est justement ce dépassement qui rend l'addition plus complexe. Ainsi, dans cette soustraction modulaire, l'addition à utiliser est simple. Notre addition finira en une retenue, qui neutralisera l'emprunt impossible que nous avions rencontré lors de la soustraction.
Addition
Afin que l'addition soit implementée, il faut une façon de comparer des nombres. Effectivement, l'addition peut résulter en un nombre, plus grand que le module, mais pour le savoir, il faut pouvoir comparer le résultat et le module.
/* ----------------------------------------------- */
int isbigger(number* x, number* y)
/* indicates whether a number x is larger than the number
y in the modulo field (this is an Euclid function) */
{
int bibi;
int i;
bibi = 0;
for (i = nofdigits - 1 ; i >= 0 ; i--)
{
if (x->digit[i] > y->digit[i])
{
bibi = 1;
break;
}
else if (x->digit[i] < y->digit[i])
{
bibi = -1;
break;
}
}
return bibi;
} // end isbigger
/* ----------------------------------------------- */
int isbigger1(number1* x, number1* y)
/* indicates whether a number x is larger than the number
y with extended length */
{
int bibi;
int i;
bibi = 0;
for (i = nofdigits ; i >= 0 ; i--)
{
if (x->digit[i] > y->digit[i])
{
bibi = 1;
break;
}
else if (x->digit[i] < y->digit[i])
{
bibi = -1;
break;
}
}
return bibi;
} // end isbigger
/* ----------------------------------------------- */
Dans ce code, nous avons implémenté deux versions de la fonction de comparaison, une pour les nombres avec n chiffres, et une pour des nombres avec n+1 digits. La fonction retourne 1 si x est strictement plus grand que y, elle retourne 0 en cas d'égalité, et elle retourne -1 si x est plus petit que y. Avec cette fonction de comparaison, nous pouvons implémenter l'addition:
/* ----------------------------------------------- */
void sumnum(number* x, number* y, number* s)
/* under the assumption that x and y are within the modulo
ring, s is the sum x + y in this ring */
{
int i;
int carry;
int ss;
int borrow;
int dd;
number sups;
carry = 0;
/* calculate sum without modulo structure */
if (printlevel > 0)
printf("Sum without modular structure \n");
for (i = 0 ; i < nofdigits ; i++)
{
ss = x->digit[i] + y->digit[i] + carry;
carry = ss / basis;
sups.digit[i] = ss % basis;
if (printlevel > 0)
printf("i is %d, ss is %d, carry is %d and digit is %d \n",i,ss,carry,sups.digit[i]);
}
/* if "overflow" we subtract one time the modulo */
if (carry != 0)
{
borrow = 0;
if (printlevel > 0)
printf("Overflow ! \n");
for (i = 0 ; i < nofdigits ; i++)
{
dd = sups.digit[i] - modulo.digit[i] - borrow;
if (printlevel > 0)
printf("i is %d, dd is %d ",i,dd);
if (dd < 0)
{
dd += basis;
borrow = 1;
}
else
{
borrow = 0;
}
if (printlevel > 0)
printf(" -> after correction: dd is %d and borrow is %d \n",dd,borrow);
sups.digit[i] = dd;
}
if (borrow != carry)
{
printf("Internal inconsistency: Dikken ambras !! \n");
}
}
/* if the number is bigger than the modulo we subtract modulo.
note that the subtraction fills in the output ;
if the subtraction is not needed, we need to copy
the result into the output */
int big;
big = isbigger(&sups,&modulo);
if (big >= 0)
{
difnum(&sups,&modulo,s);
}
else
{
for (i = 0 ; i < nofdigits ; i++)
{
s->digit[i] = sups.digit[i];
}
}
} // end sumnum
/* ----------------------------------------------- */
Le code d'addition fait les choses suivantes. Dans la première partie, l'addition chiffre par chiffre est implémentée, et nous utilisons le fait que l'ordinateur peut traiter des "chiffres" plus grands que ceux de la base. Le reste par division par la taille de la base donne le chiffre (dans la base) du résultat, et le quotient de la division longue des deux chiffres est la retenue qu'il faut passer au chiffre "au-dessus". Il faut travailler du lsd vers le msd. Ainsi, nous avons en fait implémenté l'addition standard de l'école primaire dans le système Hindu-Arabe.
Nous avons deux difficultés. La première est que nous pouvons avoir une retenue après avoir ajouté les deux chiffres msd. Cela voudrait dire qu'il nous faut un digit de plus, et nous ne voulons pas faire cela, car il est alors sûr que nous dépassons le module. Dans un anneau modulaire, cela veut dire qu'en fait, il faudrait soustraire un module du résultat. Ceci est fait avec une copie quasi-identique de la fonction de soustraction. La soustraction doit normalement faire un emprunt qui neutralisera la retenue ce qui nous permet de rester dans n chiffres.
La deuxième difficulté est que bien que le résultat reste confiné à n chiffres, il est cependant plus grand que le module. Dans ce cas, il faut aussi soustraire le module. Cette fois, on peut appeler la fonction de soustraction que nous avions déjà implémentée, car il n'y a pas de "retenue cachée".
Une simple somme de deux nombres plus petits que le module ne peut pas dépasser deux fois le module, donc une seule soustraction ramènera toujours le résultat dans l'anneau.
La multiplication
Pour pouvoir appliquer une multiplication dans un anneau cyclique, nous avons besoin de deux outils supplémentaires, car nous voulons réduire la multiplication normale à l'anneau en prenant le reste de la division par le module. Le premier outil nécessaire sera la multiplication d'un nombre par un seul chiffre, sans structure modulaire:
/* ----------------------------------------------- */
void digittimesnumber(int dig,number* x,number1* s)
/* multiplication of a single digit with a number */
{
int i;
int j;
int carry;
int ss;
carry = 0;
if (printlevel > 0)
printf("Digit times number; digit is %d \n",dig);
for (i = 0 ; i < nofdigits ; i++)
{
ss = dig * x->digit[i] + carry;
s->digit[i] = ss % basis;
carry = ss / basis;
if (printlevel > 0)
printf("i is %d, ss is %d, carry is %d and digit is %d \n",i,ss,carry,s->digit[i]);
}
s->digit[nofdigits] = carry;
}
/* ----------------------------------------------- */
Il faut noter que le résultat sera un nombre représenté par un tuple avec un chiffre de plus que le nombre d'origine. C'est la multiplication simple dans le système Hindu-Arabe où on utilise l'implémentation machine de la multiplication des chiffres simples et la division longue. Le nouveau chiffre sera la dernière retenue.En suite, nous avons besoin d'une version de la division longue pour calculer le reste quand on divise par le module. Comme nous allons appliquer cette division à un produit, nous acceptons comme nombres d'entrée ceux qui ont deux fois le nombre de chiffres que les nombres de l'anneau. Effectivement, le résultat d'une multiplication d'un nombre avec n chiffres avec un nombre avec m chiffres peut avoir, dans le système Hindu-Arabe, au plus n + m chiffres. La multiplication de deux nombres de n chiffres pourra donc avoir 2n chiffres.
/* ----------------------------------------------- */
void bigmodulo(bignum* x,number* r)
{
int i;
int k;
int km;
int ll;
bignum1 rr;
number1 high;
number1 testhigh;
/* We copy the dividend into a working number */
for (i = 2*nofdigits - 1; i >= 0 ; i--)
{
rr.digit[i] = x->digit[i];
}
rr.digit[2*nofdigits] = 0;
/* we will now apply long division, digit by digit */
for (i = 2*nofdigits - 1 ; i >= nofdigits - 1 ; i--)
{
/* we estimate a lower boundary on the digit of the quotient */
km = rr.digit[i+1]*basis + rr.digit[i];
ll = km / (modulo.digit[nofdigits - 1] + 1);
/* we copy the relevant part of the dividend */
/* we have to copy nofdigits + 1 digits */
if (printlevel > 0)
printf("i is %d . Estimated q: %d ; Relevant part of dividend : \n",i,ll);
for (k = i + 1 ; k >= i - nofdigits + 1 ; k--)
{
high.digit[k - i + nofdigits - 1] = rr.digit[k];
if (printlevel > 0)
printf("digit %d is %d \n",k,rr.digit[k]);
}
/* we have to find out how many times to subtract "modulo"
before this number is bigger than the relevant part of the
dividend */
do
{
digittimesnumber(ll,&modulo,&testhigh);
ll++;
}
while (isbigger1(&high,&testhigh) >= 0);
ll--;
ll--;
if (printlevel > 0)
printf("Quotient digit number %d is %d \n",i,ll);
/* we will now do the subtraction */
digittimesnumber(ll,&modulo,&testhigh);
int borrow;
int dd;
borrow = 0;
for (k = 0 ; k <= nofdigits ; k++)
{
dd = high.digit[k] - testhigh.digit[k] - borrow;
if (dd < 0)
{
dd = dd + basis;
borrow = 1;
}
else
{
borrow = 0;
}
high.digit[k] = dd;
}
if (high.digit[nofdigits] !=0 || borrow != 0)
{
printf("Internal inconsistency: Vried ambras ! \n");
}
/* we update the intermediate result */
for (k = i + 1; k >= i - nofdigits + 1; k--)
{
rr.digit[k] = high.digit[k - i + nofdigits - 1];
}
}
/* we copy the remainder into the result */
for (i = nofdigits - 1 ; i >= 0 ; i--)
{
r->digit[i] = rr.digit[i];
}
} // end bigmodulo
/* ----------------------------------------------- */
L'idée générale est la suivante: nous copions le dividende dans un registre de travail qui a 2n+1 chiffres, dont le chiffre supérieur sera donc mis à 0. Ce registre sera réduit avec des multiples du module, jusqu'à ce qu'il ne reste que le reste. Nous appliquons le schéma de la division longue de notre temps d'école: nous regardons les n+1 chiffres de poids les plus élevés (c'est parce qu'il y a ce n+1, qu'il nous fallait 2n+1 chiffres et non 2n chiffres pour commencer). Nous prenons le chiffre du poids le plus fort du diviseur, et nous ajoutons 1. Par exemple, dans une base décimale, si nous voulons diviser 2398062 par 79, nous allons prendre les 3 chiffres de poids le plus fort du dividende, à savoir 239, et nous allons soustraire un certain nombre de fois 79. Nous prenons le chiffre de poids le plus fort du diviseur, 79, c'est donc 7, et nous ajoutons 1, ce qui fait 8. Nous allons voir combien de fois 8 va dans 23. C'est 2 fois. Ce nombre sera une limite inférieure du nombre de fois le diviseur va dans cette partie du dividende. On va augmenter ce quotient potentiel jusqu'à ce que le produit du diviseur et ce quotient potentiel dépasse la partie du dividende que nous avions sélectionnée. Dans notre exemple, nous multiplions 2 avec 79, ce qui fait 158. 158 est forcément plus petit que 239. Essayons 2+1 = 3. 3 fois 79 fait 237. C'est toujours plus petit que 239. Essayons maintenant 3 + 1 = 4. 4 fois 79 fait 316, ce qui est plus grand. Ainsi, il faut soustraire 3 fois 79 de 239. Si nous faisons cela, le chiffre de poids plus fort doit devenir 0.
La méthode recommence, avec tout décalé d'un chiffre.
Chaque fois que nous appliquons une soustraction du genre, nous allons soustraire un nombre entier de fois le module si le diviseur est le module. Quand nous arrivons aux n+1 chiffres de poids inférieur du dividende qui reste dans le registre de travail, après soustraction d'un nombre maximal de fois le module, nous obtenons le reste que nous cherchions.
On peut donc finalement implémenter la multiplication modulaire:
/* ----------------------------------------------- */
void timesnum(number* x, number* y, number* p)
/* multiplication in the modular field */
{
int i;
int j;
bignum pp;
int ss;
for (i = 0 ; i < 2*nofdigits ; i++)
{
pp.digit[i] = 0;
}
/* rough multiplication, out of scope of basis per digit */
for (i = 0 ; i < nofdigits ; i++)
{
for (j = 0 ; j < nofdigits ; j++)
{
pp.digit[i+j] += x->digit[i] * y->digit[j];
}
}
/* limiting each digit to the basis, generalized carry */
for (i = 0 ; i < 2 * nofdigits - 1 ; i++)
{
ss = pp.digit[i];
pp.digit[i+1] += ss / basis;
pp.digit[i] = ss % basis;
}
/* applying modulo */
bigmodulo(&pp,p);
} // end multiplynum
/* ----------------------------------------------- */
Nous utilisons le fait que l'implémentation machine des "chiffres" peut aller bien plus loin que la base qu'on a définie. Ainsi, nous appliquons la multiplication chiffre par chiffre et nous accumulons le résultat dans les "chiffres" du résultat (qui dépassent donc largement la base). Les surplus vont ensuite êtres convertis en retenues, en prenant le reste par division par la taille de la base qui reste dans le chiffre même, et le quotient qui passe comme retenue au chiffre de poids supérieur. Cette technique est assez brutale, mais permet une implémentation simple. Quand le produit est établi sur 2n chiffres, il faudra encore appliquer une division longue par le module et garder le reste pour rester dans l'anneau.
La division longue
Nous allons maintenant attaquer la division longue pour de bon. En fait, la division longue est un peu spéciale dans un anneau modulaire, car nous allons explicitement pas utiliser la structure modulaire de l'anneau. Nous allons implémenter la version classique, standard, de la division longue. En fait, nous avons déjà implémenté cette division longue dans le cas de la multiplication modulaire. Mais maintenant, nous allons fabriquer une version qui ne fonctionne que sur de nombres avec n chiffres pour le dividende et le diviseur. Pour obtenir le quotient, il suffit de faire la bonne comptabilité des résultats de division.
/* ----------------------------------------------- */
void dividenum(number* x, number* y, number* q, number* r)
/* Euclidean division */
{
int i;
int k;
int km;
int ll;
int divlen;
number zero;
number1 rr;
number1 high;
number1 testhigh;
/* We copy the dividend into an intermediate working number */
for (i = nofdigits - 1; i >= 0 ; i--)
{
rr.digit[i] = x->digit[i];
q->digit[i] = 0; // we put to zero the quotient
zero.digit[i] = 0;
}
rr.digit[nofdigits] = 0;
if (isbigger(y,&zero) == 0)
{
printf("Division by zero doesn't work ! \n");
return;
}
/* we determine the number of active digits in the divider */
for (divlen = nofdigits - 1 ; divlen >= 0 ; divlen--)
{
if (y->digit[divlen] != 0)
{
break;
}
}
if (printlevel > 0)
printf("Divlen is : %d \n",divlen);
/* divlen will contain the index of the first
non-zero divider digit */
/* we will now apply long division, digit by digit */
for (i = nofdigits - 1 ; i >= divlen ; i--)
{
/* we estimate a lower boundary on the digit of the quotient */
km = rr.digit[i+1]*basis + rr.digit[i];
ll = km / (y->digit[divlen] + 1);
if (printlevel > 0)
{
printf("Quotient estimate %d \n",ll);
printf("Relevant part of dividend : \n");
}
/* we copy the relevant part of the dividend */
/* we have to copy nofdigits + 1 digits */
for (k = i + 1 ; k >= i - divlen ; k--)
{
high.digit[k - i + divlen] = rr.digit[k];
if (printlevel > 0)
printf("digit %d is %d \n",k,rr.digit[k]);
}
for (k = divlen + 2 ; k < nofdigits + 1 ; k++)
{
high.digit[k] = 0;
}
/* we have to find out how many times to subtract "modulo"
before this number is bigger than the relevant part of the
dividend */
do
{
digittimesnumber(ll,y,&testhigh);
ll++;
}
while (isbigger1(&high,&testhigh) >= 0);
ll--;
ll--;
if (printlevel > 0)
printf("Quotient digit number %d is %d \n",i,ll);
q->digit[i - divlen] = ll;
/* we will now do the subtraction */
digittimesnumber(ll,y,&testhigh);
int borrow;
int dd;
borrow = 0;
for (k = 0 ; k <= divlen + 1 ; k++)
{
dd = high.digit[k] - testhigh.digit[k] - borrow;
if (dd < 0)
{
dd = dd + basis;
borrow = 1;
}
else
{
borrow = 0;
}
high.digit[k] = dd;
}
if (high.digit[divlen + 1] !=0 || borrow != 0)
{
printf("Internal inconsistency: Hiel vried ambras ! \n");
}
/* we update the intermediate result */
for (k = i+1 ; k >= i - divlen ; k--)
{
rr.digit[k] = high.digit[k - i + divlen];
}
}
/* we copy the remainder into the result */
for (i = nofdigits - 1 ; i >= 0 ; i--)
{
r->digit[i] = rr.digit[i];
}
} // end dividenum
/* ----------------------------------------------- */
L'algorithme Euclidien étendu
Nous avons l'habitude d'utiliser l'algorithme Euclidien dans l'anneau des entiers, mais en fait, il fonctionne aussi dans tout anneau Euclidien (et un anneau modulaire est un anneau Euclidien).
/* ----------------------------------------------- */
void exteuclid(number* a, number* b, number* gcd, number* s, number* t)
{
number rm1; // (r-1) ; gcd is (r-2)
number s1; // (s-1) ; s is (s-2)
number t1; // (t-1) ; t is (t-2)
number q;
number r;
number d;
number dodo;
number sn;
number tn;
number zero;
int i;
for (i = 0 ; i < nofdigits ; i++)
{
gcd->digit[i] = a->digit[i];
rm1.digit[i] = b->digit[i];
s1.digit[i] = 0;
t1.digit[i] = 0;
s->digit[i] = 0;
t->digit[i] = 0;
zero.digit[i] = 0;
}
if (isbigger(a,&zero) == 0 || isbigger(b,&zero) == 0)
{
printf("Algorithm doesn't work with 0 as input !\n");
return;
}
s->digit[0] = 1;
t1.digit[0] = 1;
do
{
/* Extended Euclidean algorithm iteration */
dividenum(gcd,&rm1,&q,&r); // r = (r-2) mod (r-1)
difnum(gcd,&r,&d);
dividenum(&d,&rm1,&q,&dodo); // q = { (r-2) - r } / (r-1)
timesnum(&q,&s1,&dodo);
difnum(s,&dodo,&sn); // s = (s-2) - q * (s-1)
timesnum(&q,&t1,&dodo);
difnum(t,&dodo,&tn); // t = (t-2) - q * (t-1)
/* preparing next iteration i -> i+1 */
for (i = 0 ; i < nofdigits ; i++)
{
gcd->digit[i] = rm1.digit[i]; // (r-1) -> (r-2)
rm1.digit[i] = r.digit[i]; // r -> (r-1)
s->digit[i] = s1.digit[i]; // (s-1) -> (s-2)
s1.digit[i] = sn.digit[i]; // s -> (s-1)
t->digit[i] = t1.digit[i]; // (t-1) -> (t-2)
t1.digit[i] = tn.digit[i]; // t -> (t-1)
}
}
while (isbigger(&r,&zero) != 0);
} // end exteuclid
/* ----------------------------------------------- */
L'algorithme Euclidien étendu calcule le PGDC de deux nombres, et l'écrit comme une combinaison des deux nombres. Il n'y a rien d'explicitement modulaire dans cet algorithme, sauf que nous utilisons la multiplication modulaire, et la soustraction modulaire. La division longue est la "normale". La raison pour laquelle ceci fonctionne, sera expliqué dans la partie "two's compliment" et "one's compliment" plus loin.
L'inverse multiplicatif modulaire
Nous sommes maintenant en mesure de calculer l'inverse multiplicatif dans l'anneau modulaire. Nous avons implémenté déjà la division longue, qui n'était pas la division modulaire. L'inverse multiplicatif existe dans un anneau, si le PGDC avec le module est égal à 1, ce qui est donc toujours le cas si le module est un nombre premier (et alors l'anneau devient un champs). Si le module n'est pas un nombre premier, alors certains éléments de l'anneau n'auront pas d'inverse multiplicatif.
/* ----------------------------------------------- */
void inversenum(number* x,number* invx)
{
number oldmodulo;
number maxmodulo;
number gcd;
number s;
number een;
number zero;
number invx1;
number q;
int i;
/* we put the modulo value in a safe place, and put the
current modulo parameter to its maximum */
if (modulo.digit[nofdigits-1] >= basis/2)
{
printf("Error: number space not large enough to apply extended Euclid! \n");
return;
}
for (i = 0 ; i < nofdigits ; i++)
{
maxmodulo.digit[i] = basis - 1;
oldmodulo.digit[i] = modulo.digit[i];
modulo.digit[i] = maxmodulo.digit[i];
een.digit[i] = 0;
zero.digit[i] = 0;
invx->digit[i] = 0;
}
if (isbigger(x,&zero) == 0)
{
printf("Inverse of zero not possible !\n");
for (i = 0 ; i < nofdigits ; i++)
{
modulo.digit[i] = oldmodulo.digit[i];
}
return;
}
/* we apply the extended Euclidean algorithm to find 1/x */
een.digit[0] = 1;
exteuclid(&oldmodulo,x,&gcd,&s,&invx1);
if (isbigger(&gcd,&een) != 0)
{
printf("GCD is not one ! \n");
}
if (isbigger(&invx1,&oldmodulo) >= 0)
{
sumnum(&invx1,&oldmodulo,invx);
}
else
{
sumnum(&invx1,&zero,invx);
}
/* we put the original modulo parameter back */
for (i = 0 ; i < nofdigits ; i++)
{
modulo.digit[i] = oldmodulo.digit[i];
}
} // end inversenum
/* ----------------------------------------------- */
L'astuce qu'on utilise est d'appliquer l'algorithme étendu d'Euclide, mais nous ne pouvons bien sûr ne pas l'appliquer dans le même anneau que celui dont nous voulons l'inverse multiplicatif: l'ordre de "l'anneau de travail" doit être au moins deux fois plus grand que l'anneau sous étude. C'est pourquoi nous changeons provisoirement le module à sa valeur maximale possible (on mettra le module à sa valeur correcte à la fin). Le coefficient, dans l'algorithme étendu d'Euclide, du nombre à inverser, est l'inverse recherchée, ou l'inverse moins le module (d'origine). Si ce coefficient n'est pas dans l'anneau, cela veut dire qu'il faut ajouter une fois le module.
Two's complement et one's complement
Nous avons implémenté l'arithmétique dans un anneau modulaire (c'est à dire, l'addition, la soustraction, la multiplication), et nous avons implémenté l'inverse multiplicatif qui prend toute sa valeur dans un champs modulaire, donc quand le module est un nombre premier. Mais nous avons aussi implémenté quelques algorithmes qui n'ont, normalement, un sens que dans l'anneau des entiers: la division longue et l'algorithme d'Euclide. Comment ça peut fonctionner ?
Dans l'arithmétique "normale" d'une machine comme un ordinateur, la représentation du système Hindu-Arabe est aussi limité (d'ailleurs, beaucoup plus que dans les anneaux potentiellement énormes que nous avons implémentés !). La plupart des ordinateurs utilisent la base 2 (le système binaire). La plupart des implémentations machine représentent aussi des nombres négatifs en utilisant la technique du "two's complement" (ou parfois la technique du "one's complement", mais c'est plus rare), au lieu d'utiliser un "bit de signe". Pourquoi ? Il s'avère que l'avantage des systèmes two complement et one's complement est que les algorithmes de calcul arithmétique sont les mêmes, indépendant du signe des nombres ; là où un vrai bit de signe nécessiterait des traitements différents selon les signes des opérandes (4 possibilité: ++, +-, -+ et --).
Mais que sont ces "two's complement" et "one's complement" en fait ? Dans les deux systèmes, des nombres positifs sont représentés comme dans le système Hindu-Arabe binaire. La différence réside dans la représentation des nombres négatifs. Dans le "one's complement", un nombre négatif a la représentation de sa valeur absolue, mais tous les bits sont inversés. Par exemple, dans un système à 8 bits, si 0001011 est un nombre positif binaire (qui est égal à 7), alors la représentation de -7 dans le système "one's complement" est: 1110100. C'est en fait, faire 0 - 7 dans l'anneau modulaire de modulus 11111111 !
En d'autres termes, la représentation "one's complement" n'est rien d'autre que l'anneau modulaire avec modulus 11111111 !
Il faut juste limiter la taille des nombres "positifs" et "négatifs" pour qu'ils ne se confondent pas. En d'autres termes, un anneau modulaire peut représenter des nombres "positifs" et "négatifs", si on les limite en valeur absolue à moins que la moitié du module. Les nombres positifs sont des nombres avec une représentation "normale", et les nombres négatifs sont 0 - X, comme il se doit pour un nombre négatif (inverse pour l'addition), qui se représente donc comme un nombre de "grande taille" dans l'anneau.
Le problème avec "one's complement" est que 0 a deux représentations: 0000 0000 et 1111 1111. Car -0 est 0. Ce problème est résolu dans le système "two's complement". Ici, un nombre négatif a la représentation du "one's complement" plus 1. Cela fait que 0 est 0000 0000, et -0 est 1111 1111 + 0000 0001 = 0000 0000. Donc 0 et -0 ont bel et bien la même représentation.
Mais on peut voir two's complement aussi d'une autre façon:
Le "two's complement" n'est rien d'autre que l'anneau modulaire de module 1 0000 0000, où on a ajouté un chiffre binaire en plus.
Ainsi, nous voyons que la représentation des "entiers" dans un ordinateur n'est rien d'autre que l'utilisation du système Hindu-Arabe dans un anneau modulaire, où une partie des éléments est considéré comme nombres positives, et leurs inverses additionnels comme leurs négatifs.
Ceci explique aussi pourquoi l'algorithme Euclidien étendu marchait aussi dans un anneau qui était "suffisamment large" et pourquoi on pouvait l'utiliser pour calculer l'inverse multiplicatif dans un anneau modulaire de plus petite taille.
