Salut a tous, j'espere que le premier article sur les calculs avec les grands nombres vous a interesse.
Avant de commencer a vous presente le sommaire de cet article, je tiens a inclure un rectificatif au code associe a la division euclidienne.
Tout d'abord j'ai oublie d'incorporer une ligne de code necessaire au bon fonctionnement de la routine :
//****************
//* Sinon l'algo *
//****************
vald=nb2.nomb[nb2.nb]+1;
nb3=nb1;
while(varcomp!=-1)
{
mula=zeronb10(); // -----------------------> Ligne a rajouter !
j3=nb3.nb-nb2.nb;
mula.nb=j3;
| l |
En effet, si on ne place pas cette ligne le quotient de la division euclidienne est faux : une addition s'opere avec mula et l'algorithme utilise pour l'addition ne verifie pas si dans l'espace memoire utilise par mula les donnees se situant a l a suite des chiffres de mula sont egales a zero !
Copie du message envoye au forum de prograzine :
Salut,
Dans l'article consacre aux calculs avec les grands nombres,
l'algorithme utilise pour la division comporte une erreur!
En effet, j'ai recemment decouvert le probleme suivant:
Je desirais effectuer la division euclidienne de 2530 par 10
J'ai donc fait appel a la fonction reste qui a alors procede de la maniere suivante:
nb1=2530 et nb2=10
2530 / 11 = 230
muld=230
2530 - 230*10 = 230
230 / 11 = 20 + 10
muld=230+20=250
230 - 20*10 = 30
30 / 11 = 2 + 8
muld=230+20+2=252
30 - 2*10=10
nb2=10 donc reste=0
Ainsi on obtenait 2350 = 252*10
Or 2350 = 253*10!
Comme vous pouvez le constater l'algorithme a malheureusement oublie de tenir compte du fait
que si le reste de la division de 30 par 11 est egal a 10 soit nb2
il faut incrementer la valeur du quotient.
Donc il faut operer le rectificatif suivant:
Au lieu de:
--------------------------------------------------------------
//nb5=multiplicatio(mula,nb2);
//nb3=soustractio(nb3,nb5);
//varcomptps=comp(nb3,nb2);
//if(varcomptps<=0) varcomp=-1>
//
//if(varcomptps==0) nb3=zeronb();
--------------------------------------------------------------
Vous devez mettre:
nb5=multiplicatio(mula,nb2);
nb3=soustractio(nb3,nb5);
varcomptps=comp(nb3,nb2);
if(varcomptps<=0) varcomp=-1>
if(varcomptps==0)
{
nb3=zeronb();
mula.nb=0;
mula.nomb[0]=1;
muld=additio(muld,mula);
}
Voila j'espere avoir ete suffisamment clair!
N'hesitez pas me poser des questions.
Loubail
| l |
| >Sommaire |
Dans l'article precedent nous avons etudie les operations suivantes : addition, multiplication, soustraction et division. Ces operations ne s'appliquaient alors qu'aux nombres entiers positifs.
Dans le present article je vais traiter les sujets suivants:
- Extension de l'addition, la soustraction, la multiplication et la division aux entiers relatifs (entiers positifs et negatifs).
- La conversion des nombres representes en base 256 en nombres en base 10
- La conversion des nombres representes en base 10 en nombres en base 256
- L'operation puissance
- L'operation puissance modulo
- Le calcul du pgcd de 2 entiers
- Le calcul du pgcd de n entiers
- Bezout
- Le calcul de l'inverse modulo n
- 4 operations logiques : and, or, xor et not
Ainsi nous aurons traiter les principales operations pouvant etre effectuees avec des entiers relatifs. Neanmoins cet article ne constitue pas le dernier de la serie d'articles a propos du calcul avec les grands nombres. En effet, pour la cryptographie l'ensemble de ces connaissances de base peut suffire. Mais en ce qui concerne les fractales ou la determination de n decimales de pi ou de e par exemple, nous devons operer des calculs avec les nombres complexes ou / et les nombres a virgule flottante. Ainsi 2 a 3 articles viendront completer ces 2 premiers articles. Donc, normalement (sauf si je change d'avis : c'est a dire que des lecteurs m'ecrivent en me demandant d'ecrire en parallele des articles sur les calculs avec les nombres complexes et les nombres a virgule flottante des articles sur la cryptographie) je ne redigerai pas d'articles sur la cryptographie avant d'avoir termine cette serie d'article.
| >Extension de l'addition, la soustraction, la multiplication et la division aux entiers relatifs: |
Dans le type bignum est inclus l'entier signe. Cet entier determine, comme son nom l'indique, le signe du grand nombre concerne. Si cette valeur vaut -1 alors le nombre est negatif. Si cette valeur vaut 0 alors le nombre est positif.
| >L'addition et la soustraction: |
Ces deux operations sont intimenent liees lorsqu'on effectue des operations avec les entiers relatifs.
| >L'addition: |
Soient a et b deux entiers relatifs
Nous devons effectuer l'operation: a + b en utilisant seulement l'addition et la soustraction appliques aux entiers naturels.
3 cas se presentent:
- a.signe = b .signe. Dans ce cas la valeur absolue du resultat est |a+b| et le signe du resultat est a.signe (on peut evidemment prendre aussi b.signe)
- sinon le signe de a differe du signe de b.
on fait en sorte que a soit positif et b negatif
- Si a>b alors le resultat est positif et la valeur absolue du resultat vaut |a-b|
- Sinon le resultat est negatif et la valeur absolue du resultat vaut |b-a|.
Il est important de noter que l'on effectue l'operation qui determine la valeur absolue du resultat en utilisant la fonction qui s'applique uniquement aux entiers naturels positifs.
Donc pour une des 4 operations traitees dans cette partie il existe deux fonctions : une qui s'applique aux entiers naturels et l'autre aux entiers relatifs.
| >La soustraction: |
Comme lors de l'addition nous devons effectuer l'operation: a - b en utilisant seulement l'addition et la soustraction appliquees aux entiers naturels positifs.
4 cas se presentent:
- Si le signe de a est egal au signe de b:
- Si le signe de a est positif alors:
- Si a<b la valeur absolue du resultat vaut |b-a| et le resultat est negatif.
- Sinon la valeur absolue du resultat vaut |a-b| et le resultat est positif
- Sinon si le signe de a est negatif alors:
- Si a<b la valeur absolue du resultat vaut |b-a| et le resultat est positif
- Sinon la valeur absolue du resultat vaut |a-b| et le resultat est negatif
- Si le signe de a est positif alors:
- Sinon si le signe de a et de b sont differents: La valeur absolue du resultat vaut |a+b| et le signe du resultat est le signe de a.
Desormais nous pouvons donc effectuer une addition et une soustraction avec des entiers relatifs.
Code genere pour effectuer une addition avec des entiers relatifs : (Je ne commente pas ce code etant donne que l'algorithme utilise vient d'etre detaille)
//Addition de grands nombres entiers positifs
bignb additio(bignb nb1,bignb nb2)
{
int i;
int j;
bignb nb3=zeronb();
if(nb1.nb>nb2.nb) j=nb1.nb;
else j=nb2.nb;
nb3.nb=j;
for(i=0;i<=j;i++>
{
nb3.nomb[i]+=(nb1.nomb[i]+nb2.nomb[i])%256;
nb3.nomb[i+1]+=(nb1.nomb[i]+nb2.nomb[i])/256;
}
if(nb3.nomb[nb3.nb+1]!=0) nb3.nb++;
return(nb3);
}
//Addition de grands nombres relatifs
bignb addition(bignb nb1,bignb nb2)
{
bignb nb3;
int i;
if(nb1.signe==nb2.signe)
{
nb3=additio(nb1,nb2);
nb3.signe=nb1.signe;
return(nb3);
}
if(nb1.signe==-1)
{
nb3=nb1;
nb1=nb2;
nb2=nb3;
}
if(comp(nb2,nb1)!=-1)
{
i=-1;
nb2.signe=0;
nb1.signe=0;
nb3=soustractio(nb2,nb1);
}
else
{
i=0;
nb2.signe=0;
nb1.signe=0;
nb3=soustractio(nb1,nb2);
}
nb3.signe=i;
return(nb3);
}
| l |
Code genere pour effectuer une soustraction avec des entiers relatifs : (Je ne commente pas ce code etant donne que l'algorithme utilise vient d'etre detaille)
bignb arrangesous(bignb nb3,int i)
{
int j;
for(j=i;j<=nb3.nb;j++>
{
nb3.nomb[j]+=255; //(256-1)
if(nb3.nomb[j+1]!=0)
{
nb3.nomb[j+1]--;
return(nb3);
}
else nb3=arrangesous(nb3,j+1);
}
return(nb3);
}
//Soustraction de grands nombres entiers positifs
bignb soustractio(bignb nb1,bignb nb2)
{
int i;
int j;
bignb nb3;
if(comp(nb1,nb2)==-1)
{
nb3=nb1;
nb1=nb2;
nb2=nb3;
}
nb3=nb1;
j=nb2.nb;
for(i=0;i<=j;i++>
{
if(nb3.nomb[i]<nb2.nomb[i]>
{
nb3.nomb[i]+=256;
if(nb3.nomb[i+1]!=0) nb3.nomb[i+1]--;
else nb3=arrangesous(nb3,i+1);
}
nb3.nomb[i]=(nb3.nomb[i]-nb2.nomb[i]);
}
if(nb3.nomb[nb3.nb]==0) nb3.nb--;
return(nb3);
}
//Soustraction de grands nombres relatifs
bignb soustraction(bignb nb1,bignb nb2)
{
bignb nb3;
if(nb1.signe==nb2.signe)
{
if(nb1.signe==0)
{
if(comp(nb1,nb2)==-1)
{
nb3=soustractio(nb2,nb1);
nb3.signe=-1;
return(nb3);
}
else
{
nb3=soustractio(nb1,nb2);
nb3.signe=0;
return(nb3);
}
}
else
{
if(comp(nb1,nb2)==-1)
{
nb3=soustractio(nb2,nb1);
nb3.signe=0;
return(nb3);
}
else
{
nb3=soustractio(nb1,nb2);
nb3.signe=-1;
return(nb3);
}
}
}
nb3=additio(nb1,nb2);
nb3.signe=nb1.signe;
return(nb3);
}
| l |
| >La multiplication: |
Des 4 operations etudiees dans cette partie la multiplication etendue aux entiers relatifs est la sous-partie la plus courte et la plus simple.
La valeur absolue du resultat de l'operation a*b vaut |a*b|. Si le signe de a et le signe de b sont identiques alors le signe du resultat est positif. Sinon le signe de a et celui de b different et le signe du resultat est negatif.
Code genere pour effectuer une multiplication avec des grands nombres relatifs: (Je ne commente pas ce code etant donne que l'algorithme utilise vient d'etre detaille)
//Multiplication de grands nombres entiers positifs
bignb multiplicatio(bignb nb1,bignb nb2)
{
int i;
int j;
int nbch;
bignb nb3;//=zeronb();
bignb nb4[100];
if(nb1.nb>nb2.nb)
{
nb3=nb1;
nb1=nb2;
nb2=nb3;
}
nbch=nb1.nb;
for(i=0;i<=nbch;i++>
{
for(j=0;j<=nb2.nb+i+1;j++) nb4[i].nomb[j]=0>
for(j=i;j<=nb2.nb+i;j++>
{
nb4[i].nomb[j]+=(nb2.nomb[j-i]*nb1.nomb[i])%256;
nb4[i].nomb[j+1]+=(nb2.nomb[j-i]*nb1.nomb[i])/256;
}
nb4[i].nb=nb2.nb+i;
if(nb4[i].nomb[nb4[i].nb+1]!=0) nb4[i].nb++;
}
nb3=zeronb();
for(i=0;i<=nbch;i++) nb3=additio(nb4[i],nb3)>
return(nb3);
}
//Multiplication de grands nombres relatifs
bignb multiplication(bignb nb1,bignb nb2)
{
bignb nb3;
nb3=multiplicatio(nb1,nb2);
if(nb1.signe==nb2.signe) nb3.signe=0;
else nb3.signe=-1;
return(nb3);
}
bignb arrangesous(bignb nb3,int i)
{
int j;
for(j=i;j<=nb3.nb;j++>
{
nb3.nomb[j]+=255; //(256-1)
if(nb3.nomb[j+1]!=0)
{
nb3.nomb[j+1]--;
return(nb3);
}
else nb3=arrangesous(nb3,j+1);
}
return(nb3);
}
| l |
| >La division: |
La methode utilisee differe de celle utilisee pour l'addition et celle utilisee pour la soustraction.
Tout d'abord on calcul le quotient et le reste de la division de a par b. Ensuite on modifie ce resultat selon le signe de a et de b. Avant de traiter les differents cas je tiens a vous rappeler que le reste dans la division de a par b doit appartenir a [0;b[.
Ceci etant dit nous pouvons traiter les differents cas:
- Si le signe de a et de b sont identiques:
- Si le signe de a est positif alors aucune modification n'est necessaire
- Sinon le signe de a est negatif.
a = bq + r |a| = |b|q2 + r2 a = b(q2+1) + (|b|-r2)
l
Dans ce cas le reste de la division de a par b vaut - le reste de la division de |a| par |b|. Donc le reste est negatif. Or le reste doit etre positif. Il suffit d'attribuer au reste de la division de a par b le resultat de |b|-| reste de la division de |a| par |b| | et le quotient de la division de a par b est egal au quotient de la division de |a| par |b| + 1. Le reste appartient ainsi a [0;b[ (N.B.: le quotient est alors positif).
- Sinon le signe de a et de b sont differents:
-
a = bq + r |a| = |b|q2 + r2 a = -bq2 + r
l
Si a est positif alors le quotient de la division de a par b vaut - le quotient de la division de |a| par |b|.
-
a = bq +r |a| = |b|q2 + r2 a = -b(q2+1) + (|b|-r2)
l
Sinon le reste est negatif. On attribue ainsi au reste de la division de a par b le resultat de |b|-| reste de la division de |a| par |b| | et le quotient de la division de a par b vaut - le quotient de la division de |a| par |b| -1 (N.B. le quotient est alors negatif).
Code genere pour effectuer une division avec deux grands nombres relatifs : (Je ne commente pas ce code etant donne que l'algorithme utilise vient d'etre detaille)
//Division avec deux grands nombres entiers positifs bigdiv resteo(bignb nb1,bignb nb2) { int i; int j,j2; int j3; int vald; int j4; bignb nb3,nb4,nb5; bignb mula; bignb muld=zeronb(); bigdiv result; int varcomp=0; int varcomptps; //**************** //* Cas evidents * //**************** if(comp(nb1,nb2)==-1) { result.bgdiv.nb=0; result.bgdiv.nomb[0]=0; result.bgrest=nb1; return(result); } if(nb2.nb==0) if(nb2.nomb[0]==0) { result.bgdiv.nb=0; result.bgdiv.nomb[0]=0; result.bgrest=nb1; return(result); } if(nb2.nb==0) if(nb2.nomb[0]==1) { result.bgrest.nb=0; result.bgrest.nomb[0]=0; result.bgdiv=nb1; return(result); } //**************** //* Sinon l'algo * //**************** vald=nb2.nomb[nb2.nb]+1; nb3=nb1; while(varcomp!=-1) { j3=nb3.nb-nb2.nb; mula.nb=j3; for(j=0;j<=j3;j++) mula.nomb[j]=0> mula.nomb[j3]=nb3.nomb[nb3.nb]/vald; if(mula.nomb[j3]==0) { j3=nb3.nb-nb2.nb-1; mula.nb=j3; for(j=0;j<=j3;j++) mula.nomb[j]=0> mula.nomb[j3]=((nb3.nomb[nb3.nb-1]+256*nb3.nomb[nb3.nb])/vald)%256; mula.nomb[j3+1]=((nb3.nomb[nb3.nb-1]+256*nb3.nomb[nb3.nb])/vald)/256; if(mula.nomb[j3+1]!=0) { mula.nb++; j3++; } if(nb3.nb-1<nb2.nb> { mula.nb=0; j3=0; mula.nomb[j3]=1; } if (mula.nomb[j3]==0) { mula.nomb[j3]=1; } } muld=additio(muld,mula); nb5=multiplicatio(mula,nb2); nb3=soustractio(nb3,nb5); varcomptps=comp(nb3,nb2); if(varcomptps<=0) varcomp=-1> if(varcomptps==0) { nb3=zeronb(); mula.nb=0; mula.nomb[0]=1; muld=additio(muld,mula); } } result.bgdiv=muld; result.bgrest=nb3; return(result); } //Division avec deux grands nombres relatifs bigdiv reste(bignb nb1,bignb nb2) { bignb unite; bigdiv nb3; unite.nb=0; unite.nomb[0]=1; nb3=resteo(nb1,nb2); if(nb1.signe==nb2.signe) { if(nb1.signe==0) return(nb3); else { nb3.bgdiv=additio(nb3.bgdiv,unite); nb3.bgrest=soustractio(nb2,nb3.bgrest); nb3.bgdiv.signe=0; nb3.bgrest.signe=0; return(nb3); } } if(nb1.signe==0) { nb3.bgdiv.signe=-1; return(nb3); } else { nb3.bgdiv=additio(nb3.bgdiv,unite); nb3.bgdiv.signe=-1; nb3.bgrest=soustractio(nb2,nb3.bgrest); } return(nb3); }l >Conversion des nombres representes en base 256 en nombres en base 10:
Plusieurs methodes peuvent etre utilisees. Je vais d'abord presentez deux methodes qui ne sont pas tres performantes.
>Methode 1:
Cette methode est la plus simple des 3. Soit nb256 un grand nombre en base 256 et nb10 un grand nombre en base 10.
Trois operations sont necessaires: La soustraction en base 256, L'addition en base 10, et La comparaison du nombre en base 256 avec 0
On utilise l'algorithme suivant:
On soustrait au nombre en base 256 1 (nb256 = nb256 - 1) On ajoute au nombre en base 10 1 (nb10 = nb10 + 1) On compare nb256 avec 0 : si nb256=0 on stoppe l'algorithme sinon on continue a l'appliquer
nb10 est alors egal a nb256 mais en base 10.
>Methode 2:
Cette methode est assez proche de la premiere methode.
Quatre operations sont necessaires:
La division euclidienne par 2 en base 256 L'addition en base 10, La multiplication par 2 en base 10, et La comparaison du nombre en base 256 avec 0
L'algorithme utilise utilise la decomposition en base 2 du nombre en base 256 (ce qui est rendu aise car 256 = 2^7).
L'algorithme utilise est le suivant:
On divise nb256 par 2 et on conserve le reste. ( r=nb256 (mod 2) ) nb256=nb256/2 On multiplie nb10 par 2 et on lui ajoute le reste precedemment calcule (nb10 = nb10*2 +r) On compare nb256 avec 0. Si nb256=0 on stoppe l'algorithme sinon on continue a l'appliquer.
l N.B.: Pour diviser nb256 par 2, deux methodes peuvent etre utilisees On peut diviser tout betement par 2 nb256 ou on peut diviser par 2 un chiffre qui constitue nb256. Si on divise par 2 un chiffre qui constitue nb256, on procede de la maniere suivante:
On ne traite pas entierement nb256 mais chaque chiffre le constituant un a un. Ainsi ceci equivaut a utiliser la decomposition en abse 2 de chaque chiffre constituant nb256. Donc on commence par traiter un a un les 8 bits du premier chiffre de nb256 puis on traite un a un les bits du second chiffre de nb256, etc...
>Methode 3:
Je considere que cette methode est la plus performante des 3. Je vous conseille donc d'utiliser cette methode. De plus elle possede l'avantage de permettre la conversion du nombre en base 256 en n'importe quelle base.
L'algorithme utilise deux operations: La division euclidienne de nb256 par 10, et La comparaison de nb256 avec 0
L'algorithme utilise est le suivant:
On effectue la division euclidienne de nb256 par 10. Soit r le reste et q le quotient. On pose nb256=q et nb10 = nb10*10 + r Ensuite on copare nb256 avec 0, si nb256=0 alors on stoppe l'algorithme sinon on continue a l'appliquer.
Comme je l'ai dit precedemment cette methode possede l'avantage d'incorporer dans une et meme fonction une technique permettant de convertir le nombre en base 256 en n'importe quelle base.
Code genere pour effectuer la conversion des nombres en base 256 en base 10 :
void conv256to10(bignb a) { bignb nb10; bignb nb3; bigdiv nbdiv; int ui=0; int stre=0; nb3.nb=0; nb10.nb=0; nb10.nomb[0]=10; while(stre!=1) { nbdiv=resteo(a,nb10); nb3.nomb[ui]=nbdiv.bgrest.nomb[0]; ui++; nb3.nb++; a=nbdiv.bgdiv; if(a.nb==0) if(a.nomb[0]==0) { stre=1; } } nb3.nb--; printf(" RE:"); for(stre=nb3.nb;stre>=0;stre--) printf("%d",nb3.nomb[stre]); }l >Conversion des nombres representes en base 10 en nombres en base 256:
Comme precedemment 3 methodes se profilent. Ces trois methodes sont indentiques a celles decrites auparavant. Donc je vais simplement vous presenter l'algorithme tel qu'il doit etre utilise.
Soit nb256 le nombre en base 256 et nb10 le nombre en base 10.
>Methode 1:
On soustrait a nb10 1. (nb10=nb10-1) On ajoute a nb256 1. (nb256=nb256+1) Si nb10=0 on stoppe l'algorithme sinon on continue a l'appliquer
>Methode 2:
On divise nb10 par 2. Soit r le reste et q le quotient. nb10=q et nb256=nb256*2 + r Si nb10=0 on stoppe l'algorithme sinon on continue a l'appliquer
>Methode 3:
On effectue la division euclidienne de nb10 par 256. Soit r le reste et q le quotient. nb10=q et nb256=nb256*256 + r Si nb10=0 on stoppe l'algorithme sinon on continue a l'appliquer
Evidemment cette methode est utile si et seulement si nb10 est inferieur a 2^16 (car cette serie d'articles est destinee a au moins des processeurs 16 bits). Sinon il faut mettre au point un algorithme de division euclidienne en base 10 (ce qui n'est pas tres difficile). La division euclidienne en base 10 doit etre implementer de la meme maniere que la division euclidienne en base 256 (Cf. article precedent). Donc je vais inclure le code necessaire sans aucune explication.
Evidemment ce code utilise une representation des nombres en base 10 d'une maniere predefinie. Pour plus de facilite j'ai decide de creer le type bignum10 qui possede les memes caracterisitques que bignum et dont chaque chiffre appartient a [0;10[ au lieu de [0;256[.
Code genere pour effectuer la conversion des nombres en base 10 en base 256 :
Tout d'abord je place les deux nouveaux types :
typedef struct bignb10 { int signe; int nb; unsigned int nomb[200]; } bignb10; typedef struct bigdiv10 { bignb10 bgdiv; bignb10 bgrest; } bigdiv10;l
Puis je place les routines permettant d'effectuer des calculs sur des grands nombres en base 10 :
//******************************************************************* // // BASE 10 // //******************************************************************* bignb10 zeronb10(void) { int i; bignb10 nb1; nb1.nb=0; for(i=0;i<200;i++) nb1.nomb[i]=0> nb1.signe=0; return(nb1); } int comp10(bignb10 nb1,bignb10 nb2) { int i; if(nb1.nb>nb2.nb) return(1); if(nb1.nb<nb2.nb) return(-1)> for(i=nb1.nb;i>=0;i--) { if(nb1.nomb[i]>nb2.nomb[i]) return(1); if(nb1.nomb[i]<nb2.nomb[i]) return(-1)> } return(0); } //Addition de grands nombres bignb10 additio10(bignb10 nb1,bignb10 nb2) { int i; int j; bignb10 nb3=zeronb10(); if(nb1.nb>nb2.nb) j=nb1.nb; else j=nb2.nb; nb3.nb=j; for(i=0;i<=j;i++> { nb3.nomb[i]+=(nb1.nomb[i]+nb2.nomb[i])%10; nb3.nomb[i+1]+=(nb1.nomb[i]+nb2.nomb[i])/10; } if(nb3.nomb[nb3.nb+1]!=0) nb3.nb++; return(nb3); } //Multiplication de grands nombres bignb10 multiplicatio10(bignb10 nb1,bignb10 nb2) { int i; int j; int nbch; bignb10 nb3;//=zeronb(); bignb10 nb4[100]; if(nb1.nb>nb2.nb) { nb3=nb1; nb1=nb2; nb2=nb3; } nbch=nb1.nb; for(i=0;i<=nbch;i++> { for(j=0;j<=nb2.nb+i+1;j++) nb4[i].nomb[j]=0> for(j=i;j<=nb2.nb+i;j++> { nb4[i].nomb[j]+=(nb2.nomb[j-i]*nb1.nomb[i])%10; nb4[i].nomb[j+1]+=(nb2.nomb[j-i]*nb1.nomb[i])/10; } nb4[i].nb=nb2.nb+i; if(nb4[i].nomb[nb4[i].nb+1]!=0) nb4[i].nb++; } nb3=zeronb10(); for(i=0;i<=nbch;i++) nb3=additio10(nb4[i],nb3)> return(nb3); } bignb10 arrangesous10(bignb10 nb3,int i) { int j; for(j=i;j<=nb3.nb;j++> { nb3.nomb[j]+=9; //(10-1) if(nb3.nomb[j+1]!=0) { nb3.nomb[j+1]--; return(nb3); } else nb3=arrangesous10(nb3,j+1); } return(nb3); } //Soustraction de grands nombres bignb10 soustractio10(bignb10 nb1,bignb10 nb2) { int i; int j; bignb10 nb3; if(comp10(nb1,nb2)==-1) { nb3=nb1; nb1=nb2; nb2=nb3; } nb3=nb1; j=nb2.nb; for(i=0;i<=j;i++> { if(nb3.nomb[i]<nb2.nomb[i]> { nb3.nomb[i]+=10; if(nb3.nomb[i+1]!=0) nb3.nomb[i+1]--; else nb3=arrangesous10(nb3,i+1); } nb3.nomb[i]=(nb3.nomb[i]-nb2.nomb[i]); } if(nb3.nomb[nb3.nb]==0) nb3.nb--; return(nb3); } bigdiv10 reste10(bignb10 nb1,bignb10 nb2) { int i; int j,j2; int j3; int vald; int j4; bignb10 nb3,nb4,nb5; bignb10 mula; bignb10 muld=zeronb10(); bigdiv10 result; int varcomp=0; int varcomptps; //**************** //* Cas evidents * //**************** if(comp10(nb1,nb2)==-1) { result.bgdiv.nb=0; result.bgdiv.nomb[0]=0; result.bgrest=nb1; return(result); } if(nb2.nb==0) if(nb2.nomb[0]==0) { result.bgdiv.nb=0; result.bgdiv.nomb[0]=0; result.bgrest=nb1; return(result); } if(nb2.nb==0) if(nb2.nomb[0]==1) { result.bgrest.nb=0; result.bgrest.nomb[0]=0; result.bgdiv=nb1; return(result); } //**************** //* Sinon l'algo * //**************** vald=nb2.nomb[nb2.nb]+1; nb3=nb1; while(varcomp!=-1) { mula=zeronb10(); j3=nb3.nb-nb2.nb; mula.nb=j3; for(j=0;j<=j3;j++) mula.nomb[j]=0> mula.nomb[j3]=nb3.nomb[nb3.nb]/vald; if(mula.nomb[j3]==0) { j3=nb3.nb-nb2.nb-1; mula.nb=j3; for(j=0;j<=j3;j++) mula.nomb[j]=0> mula.nomb[j3]=((nb3.nomb[nb3.nb-1]+10*nb3.nomb[nb3.nb])/vald)%10; mula.nomb[j3+1]=((nb3.nomb[nb3.nb-1]+10*nb3.nomb[nb3.nb])/vald)/10; if(mula.nomb[j3+1]!=0) { mula.nb++; j3++; } if(nb3.nb-1<nb2.nb> { mula.nb=0; j3=0; mula.nomb[j3]=1; } if (mula.nomb[j3]==0) { mula.nomb[j3]=1; } } muld=additio10(muld,mula); nb5=multiplicatio10(mula,nb2); nb3=soustractio10(nb3,nb5); varcomptps=comp10(nb3,nb2); if(varcomptps<=0) varcomp=-1> if(varcomptps==0) { nb3=zeronb10(); mula.nb=0; mula.nomb[0]=1; muld=additio10(muld,mula); } } result.bgdiv=muld; result.bgrest=nb3; return(result); }l
Et je place enfin ici la routine permettant de convertir des nombres en base 10 en base 256 :
bignb conv10to256(bignb10 a) { bignb nb1; bignb n256; bignb10 nb2; bigdiv10 nbd10; int stre=0; int place=0; n256.nb=1; n256.nomb[0]=0; n256.nomb[1]=1; nb2.nb=2; nb2.nomb[0]=6; nb2.nomb[1]=5; nb2.nomb[2]=2; nb1=zeronb(); while(stre!=1) { nbd10.bgrest=zeronb10(); nbd10=reste10(a,nb2); a=nbd10.bgdiv; nb1.nomb[place]=(nbd10.bgrest.nomb[0]+10*nbd10.bgrest.nomb[1]+100*nbd10.bgrest.nomb[2]); place++; if(a.nb==0) if(a.nomb[0]==0) stre=1; } nb1.nb=place-1; return(nb1); }l >Puissance (a^b (avec b un entier positif)):
Je vais vous decrire deux methodes.
>Methode 1:
Cette premiere methode est tres simple et peu performante. Lorsque vous effectuer l'operation a^b vous multiplier b fois a par a. Donc cette premiere methode consiste a multiplier b fois a par a. Elle risque donc d'etre tres lente.
>Methode 2 :
Cette seconde methode utilise la decomposition de b en base 2. Elle est beaucoup plus performante.
L'algorithme utilise est le suivant: Tout d'abord il faut creer une variable temporaire egale a 1. Soit c cette variable. On pose a2=a
On effectue la division euclidienne de b par 2. Soit q le quotient et r le reste. si r=1 alors c=c*a2 a2=a2^2 si q=1 alors on stoppe l'algorithme sinon on continue a l'appliquer
Ainsi a^b=a2*c
Explications:
b=b0*2^0 + b1*2^1 + b2*2^2 + ... + 1*2^n (n est egal au nombre de bits -1 constituant b)
a^b=a^(b0*2^0 + b1*2^1 + b2*2^2 + ... + 1*2^n) =(a^(b0*2^0)) * (a^(b1*2^1)) * (a^(b2*2^2)) * ... * (a^(1*2^n))
Apres avoir applique l'algorithme on a:
c=(a^(b0*2^0)) * (a^(b1*2^1)) * (a^(b2*2^2)) * ... * (a^(bn-1*2^(n-1))) et a2=(a^(1*2^n)
Donc on a bien a^b=a2*c
Pourquoi c=(a^(b0*2^0)) * (a^(b1*2^1)) * (a^(b2*2^2)) * ... * (a^(bn-1*2^(n-1))) ?
Dans l'algorithme a2=2^2 meme si r != 0. Donc a constitue le a^(2*1) .. a^(2*2) ... a^(2*n)
Si r=1 alors il faut a^(bi*2^i) = a^(2*i) sinon a^(bi*2^i)=1 Comme c est constitue d'une serie de multiplication il faut donc multiplier l'ancienne valeur de c par a^(2*i)
Exemple:
130^15 15=1111b *R=1 Q=7 c=1*130=130 a=130*130 *R=1 Q=3 c=130*130*130 a=130*130*130*130 *R=1 Q=1 c=130*130*130*130*130*130*130 a=130*130*130*130*130*130*130*130
l
Comme Q=1 130^15=a*c Le resultat comme vous pouvez le constater est alors correcte.
l N.B.: Si a est negatif pour connaitre le signe de a^b il suffit de savoir si b est pair ou impair. Il suffit d'appliquer la division euclidienne de b par 2. Si le reste est nul b est pair et a^b est positif, sinon a^b est negatif.
Code genere pour appliquer une puissance sur un entier positif:
bignb puissanc(bignb a,bignb b) { bignb P2,TA,TA3,Q,R; bignb un,deux; bigdiv nbdiv; int io=0; un=zeronb(); un.nb=0; un.nomb[0]=1; deux=zeronb(); deux.nb=0; deux.nomb[0]=2; P2=b; TA=a; TA3=un; while(io!=1) { nbdiv=resteo(P2,deux); R=nbdiv.bgrest; P2=nbdiv.bgdiv; Q=P2; if(comp(R,un)==0) TA3=multiplicatio(TA3,TA); TA=multiplicatio(TA,TA); if(comp(Q,un)==0) io=1; } TA=multiplicatio(TA,TA3); return(TA); }l
Code genere pour appliquer une puissance sur un nombre relatif:
bignb puissance(bignb a,bignb b) { bignb result; bigdiv nbdiv; bignb deux; deux=zeronb(); deux.nb=0; deux.nomb[0]=2; result=puissanc(a,b); if(a.signe==-1) { nbdiv=resteo(b,deux); if(nbdiv.bgrest.nomb[0]==0) result.signe=0; else result.signe=-1; } return(result); }l >Puissance modulo (a^b (mod d)) (avec b positif):
Je vais vous decrire deux methodes:
>Methode 1:
On calcule d'abord a^b puis on effectue la division euclidienne de a^b par d. Le reste constitue alors le resultat de a^b (mod d). Comme vous pouvez vous en douter cette methode est loin d'etre performante elle est d'autant plus lente que a b et d sont grands.
>Methode 2:
On applique l'algorithme decrite dans la methode 2 utilisee pour calculer a^b mais en y incorporant une petite modification.
L'algorithme utilise pour calculer a^b(mod d) est le suivant: Tout d'abord il faut creer une variable temporaire egale a 1. Soit d cette variable. On pose a2=a
On effectue la division euclidienne de b par 2. Soit q le quotient et r le reste. si r=1 alors c=c*a2 (mod d) a2=a2^2 (mod d) si q=1 alors on stoppe l'algorithme sinon on continue a l'appliquer
Ainsi a^b (mod d) = a2*c (mod d)
l N.B.: Si a est negatif pour connaitre le signe de a^b il suffit de savoir si b est pair ou impair. Il suffit d'appliquer la division euclidienne de b par 2. Si le reste est nul b est pair et a^b est positif, sinon a^b est negatif.
Code genere pour appliquer une puissance modulo a un entier positif :
bignb puissancemodul(bignb a,bignb b,bignb n) { bignb P2,TA,TA3,Q,R; bignb un,deux; bigdiv nbdiv; int io=0; un=zeronb(); un.nb=0; un.nomb[0]=1; deux=zeronb(); deux.nb=0; deux.nomb[0]=2; P2=b; TA=a; TA3=un; while(io!=1) { nbdiv=resteo(P2,deux); R=nbdiv.bgrest; P2=nbdiv.bgdiv; Q=P2; if(comp(R,un)==0) { TA3=multiplicatio(TA3,TA); nbdiv=resteo(TA3,n); TA3=nbdiv.bgrest; } TA=multiplicatio(TA,TA); nbdiv=resteo(TA,n); TA=nbdiv.bgrest; if(comp(Q,un)==0) io=1; } TA=multiplicatio(TA,TA3); nbdiv=resteo(TA,n); TA=nbdiv.bgrest; return(TA); }l
Code genere pour appliquer une puissance modulo a un nombre relatif :
bignb puissancemodulo(bignb a,bignb b,bignb n) { bignb result; bigdiv nbdiv; bignb deux; deux=zeronb(); deux.nb=0; deux.nomb[0]=2; result=puissancemodul(a,b,n); if(a.signe==-1) { nbdiv=resteo(b,deux); if(nbdiv.bgrest.nomb[0]==1) result=soustractio(n,result); } return(result); }l >pgcd(a,b):
Pour calculer le pgcd de deux nombres differentes methodes peuvent etre utilisees.
Je ne vais vous en decrire qu'une : l'algorithme d'euclide.
Description de l'algorithme d'euclide.
Soit a et b deux entiers naturels
On effectue la division euclidienne de a par b. Soit r le reste et q le quotient. Si r <=> 0 alors a=b et b=r et on continue a appliquer l'algorithme. Sinon r=0 et le reste precedent constitue le pgcd de a et b.
Exemple:
pgcd(1357,134): Quotient |10 |7 |1 |7|2| ---------|---|--|--|-|-| 1357 |134|17|15|2|1| Donc pgcd(1357,134)=1 ---------|---|--|--|-|-| Reste |17 |15|2 |1|0|l
Code genere pour calculer le pgcd de deux nombres entiers :
bignb pgcd(bignb nb1,bignb nb2) { bignb nb3,resttps; bignb rester=zeronb(); int fin=0; int j; if(comp(nb1,nb2)==-1) { nb3=nb1; nb1=nb2; nb2=nb3; } while(fin!=1) { rester=resteo(nb1,nb2).bgrest; if(rester.nb==0) { if(rester.nomb[0]==0) { fin=1; resttps.signe=0; return(resttps); } } if(fin==0) { nb1=nb2; nb2=rester; } resttps=rester; } return(rester); }l >pgcd (a0,a1,a2,a3,...,an) :
Pour calculer le pgcd de a0,a1,a2,a3,..., et an il suffit d'utiliser la methode suivante:
On desire calculer le pgcd de n entiers naturels. On effectue des n/2 regroupements de 2 entiers naturels. On calcule le pgcd de chaque groupe de 2 entiers naturels. Puis on regroupe a nouveau les resultats en groupe de 2, et on recalcule des pgcds, etc.., etc.., jusqu'a obtenir un seul groupe de 2. On obtient alors le pgcd des n entiers naturels.
Il y a deux types de traitement. Je vais traiter ces deux types de traitement sous des exemples:
* Si n est impair: On veut par exemple calculer le pcdg de a0,a1,a2, et a3. pgcd(a0,a1,a2,a3) = pgcd( pgcd(a0,a1), pgcd(a2,a3))
l N.B.: On peut evidemment effectuer d'autres regroupements.
* Si n est pair: On veut par exemple calculer le pgcd de a0,a1,a2,a3, et a4. pgcd(a0,a1,a2,a3,a4) = pgcd( pgcd(a0,a1), pgcd(a2,a3), a4) = pgcd( pgcd( pgcd(a0,a1), pgcd(a2,a3) ), a4)
l N.B. On peut evidemment effectuer d'autres regroupements.
Exemple numerique:
On desire calculer le pgcd de 128,266,34, et 82 On calcule d'abord le pgcd de 128 et 266 pgcd(128,266)=2 , puis on calcule le pgcd de 34 et 82 pgcd(34,82)=2 , enfin on calcule le pgcd de 2 et 2 pgcd(2,2)=2 ;) Donc pgcd(128,266,34,82)=2
l >Bezout:
L'utilisation de l'egalite de Bezout et de la propriete de Gauss permet de resoudre des equations du type ax + by = c ( avec c=pgcd(a,b) )
Egalite de Bezout : a et b sont premiers entre eux si et seulement si il existe 2 entiers relatifs u et v tels que a*u + b*v = 1
Propriete de Gauss : si a divise b*c et si a est premier avec b alors a divise c
l (N.B. : En fait l'egalite de Bezout s'applique a des polynomes et est donc plus generale !)
J'ai ainsi decide de vous presenter l'algorithme suivant:
On cherche un couple (a,b) tel que ax + by = 1 On fait en sorte que a soit superieur a b On pose k=1, k2=0, l=0, et l2=1 Tant que x1 on effectue ceci Soit i le quotient de la division de x par y *on pose e=y On attribue a y la valeur du reste de la division de x par y On attribue a x la valeur de e *On pose e=l2 l2 = l - i*l2 et l=e *On pose e=k2 k2 = k - i*k2 et k=e Lorsque x=1 on a l*x + k*y = 1
l
Explications:
Cette algorithme est base sur l'algortihme d'euclide. En effet x et y evoluent comme dans l'algorithme d'euclide.
L'evolution de x et y s'effectue ainsi comme ceci:
On effectue la division euclidienne de x par y. Soit r le reste et q le quotient. Si r <=> 0 alors x=y et y=r et on continue a appliquer l'algorithme. Sinon r=0 et le reste precedent constitue le pgcd de x et y.
l N.B. Donc avec l'algorithme utilise pour bezout on obtient egalement le pgcd de x et y.
i represente le quotient de la division de x par y.
L'evolution de k, k2, l, et l2 est telle que: xi*(li+1) + yi*k(i+1) = le reste de la division de xi par yi
Appliquer cet algorithme equivaut donc a remplir le tableau suivant :
Ai Bi Ii Ki Li A0 B0 I0 1 0 A1 B1 I1 0 1 A2 B2 K2 L2 K3 L3 K4 L4 K5 L5 Avec : A1=B0 B1=A0 (mod B0) I0 = A0/B0 L2=L1 L3=L0-I0*L1 K2=K1 K3=K0-I0*K1 A2=B1 B2=A1 (mod B1) I1 = A1/B1 L4=L3 L5=L2-I1*L3 K4=K3 K5=K2-I1*K3l
Pour eclairer vos esprit je vais inclure un exemple :
Je vais inclure tableau associe a l'algorithme d'euclide c'est a dire au calcul de pgcd(21,13) puis le tableau associe a la resolution de 13*u + 21*v = 1
pgcd(21,13): Quotient |1 |1|1|1|1|2| | ---------|--|-|-|-|-|-|-| 21 |13|8|5|3|2|1|0| ---------|--|-|-|-|-|-|-| Reste |8 |5|3|2|1|0| | Donc pgcd(21,13)=1 ;)l 13*a + 21*b = 1 Ai Bi Ii Ki Li 21 13 1 1 0 0 1 13 8 1 0 1 1 -1 8 5 1 1 -1 -1 2 5 3 1 -1 2 2 -3 3 2 1 2 -3 -3 5 2 1 2 -3 5 5 -8 1 0 5 -8 Donc 13*-8 + 5*21 = 1 !l
Code genere pour resoudre un equation du type a*x + b*y = pgcd(a,b) :
bigdiv bezout(bignb a, bignb b) { bignb k,k2,l,l2,e; bigdiv i,result; bignb un; k=zeronb(); k2=k; k.nb=0; k.nomb[0]=1; k2.nb=0; k2.nomb[0]=0; l=k2; l2=k; un=k; if(comp(a,b)<0> { e=b; b=a; a=e; } while(comp(a,un)!=0) { i=reste(a,b); a=b; b=i.bgrest; e=l2; l2=soustraction(l,multiplication(i.bgdiv,l2)); l=e; e=k2; k2=soustraction(k,multiplication(i.bgdiv,k2)); k=e; } result.bgdiv=k; result.bgrest=l; //ATTENTION le resultat est de type bgdiv: //Le resultat devra etre traite ainsi: //a*result.bgdiv + b*result.bgrest = 1 return(result); }l >Inverse modulo:
Soit c et n deux entiers naturels.
Si pgcd(c,n)=1 Alors il existe un entier x tel que c*x est congru a 1 modulo n On appelle x l'inverse de c modulo n.
c*x (mod n) = 1 c*x = 1 + k*n (avec k un entier relatif) c*x - k*n = 1l
Donc chercher l'inverse modulo n de c equivaut a resoudre l'equation c*x + k*n = 1 a l'aide de l'algorithme de bezout presente precedemment.
Code genere pour calculer l'inverse modulo d'un entier positif :
bignb inversemodulo(bignb c,bignb n) { bignb un,moinsun; bigdiv result; un=zeronb(); un.nb=0; un.nomb[0]=1; moinsun=un; moinsun.signe=-1; //S'il n'existe pas d'inverse modulo la valeur -1 sera renvoyee if(comp(pgcd(c,n),un)!=0) return(moinsun); //On resout l'equation c*x + k*n = 1 result=bezout(c,n); //On fait en sorte que le resultat soit positif if(result.bgdiv.signe==-1) result.bgdiv=soustractio(n,result.bgdiv); return(result.bgdiv); }l >Operations logiques:
Je vais traiter les quatre operations logiques suivantes: AND, OR, XOR et NOT.
>operation logique AND:
Table de verite de a AND b
a b a AND b 1 0 0 1 1 1 0 0 0 0 1 0l
a et b sont des grands nombres ecrits en base 256. On considere que a<=b. >Donc d'apres le tableau de verite de l'operation logique AND le resultat de a AND b possede au maximum a.nb chiffres en base 256.
Pour calculer a AND b j'ai decide d'operer un AND entre chaque chiffre de a et b possedant le meme indice dans le nombre en base 256. Des lors un seul probleme se pose: etablir le nombre de chiffre du resultat de a AND b.
Je vous propose d'utiliser l'algorithme suivant:
i varie de 0 a a.nb: ci=ai AND bi si ci=0 alors si i-1tps tps=i Lorsqu'on a effectuer les a.nb + 1 operations, on sait alors que c possede : - tps chiffre si le dernier chiffre de c est nul ! - sinon a.nb
l
Code genere pour appliquer l'operation logique and :
bignb bgand(bignb a,bignb b) { bignb result; int i,tps; if(comp(a,b)>0) { result=a; a=b; b=result; } result=zeronb(); for(i=0;i<=a.nb;i++> { result.nomb[i]=a.nomb[i]&b.nomb[i]; if(result.nomb[i]==0) if((i-1)!=tps) tps=i; } if(result.nomb[a.nb]==0) result.nb=tps; else result.nb=a.nb; return(result); } bignb bgor(bignb a,bignb b) { bignb result; int i; if(comp(a,b)<0> { result=a; a=b; b=result; } result=zeronb(); for(i=0;i<=a.nb;i++> { result.nomb[i]=a.nomb[i]|b.nomb[i]; } result.nb=a.nb; return(result); }l >operation logique OR:
Table de verite de a OR b
a b a OR b 1 0 1 1 1 1 0 0 0 0 1 1l
a et b sont des grands nombres ecrits en base 256. On considere que a>=b. Donc d'apres le tableau de verite de l'operation logique OR le resultat de a OR b possede nb.a chiffres en base 256.
Pour calculer a OR b j'ai decide d'operer un OR entre chaque chiffre de a et b possedant le meme indice dans le nombre en base 256.
Je vous propose d'utiliser l'algorithme suivant:
i varie de 0 a a.nb: ci=ai OR bi Lorsqu'on a effectuer les a.nb + 1 operations, on sait alors que c= a OR b
l
Code genere pour appliquer l'operation logique or :
bignb bgor(bignb a,bignb b) { bignb result; int i; if(comp(a,b)<0> { result=a; a=b; b=result; } result=zeronb(); for(i=0;i<=a.nb;i++> { result.nomb[i]=a.nomb[i]|b.nomb[i]; } result.nb=a.nb; return(result); }l >operation logique XOR:
Table de verite de a XOR b
a b a XOR b 1 0 1 1 1 0 0 0 0 0 1 1l
a et b sont des grands nombres ecrits en base 256. on considere que a>=b.
Pour calculer a XOR b j'ai decide d'operer un XOR entre chaque chiffre de a et b possedant le meme indice dans le nombre en base 256. Des lors un seul probleme se pose: etablir le nombre de chiffre du resultat de a XOR b.
Je vous propose d'utiliser l'algorithme suivant:
i varie de 0 a a.nb: ci=ai XOR bi si ci=0 alors si i-1<=sup>tps tps=i Lorsqu'on a effectuer les a.nb + 1 operations, on sait alors que c possede : - tps chiffre si le dernier chiffre de c est nul ! - sinon a.nb
l
Code genere pour appliquer l'operation logique xor :
bignb bgxor(bignb a,bignb b) { bignb result; int i,tps; if(comp(a,b)<0> { result=a; a=b; b=result; } result=zeronb(); for(i=0;i<=a.nb;i++> { result.nomb[i]=a.nomb[i]^b.nomb[i]; if(result.nomb[i]==0) if((i-1)!=tps) tps=i; } if(result.nomb[a.nb]==0) result.nb=tps; else result.nb=a.nb; return(result); }l >operation logique NOT:
Table de verite de NOT:
a NOT a 1 0 0 1
l
a est un grand nombre ecrit en base 256.
Pour calculer NOT a j'ai decide d'operer un NOT sur chaque chiffre de a. Des lors un seul probleme se pose: etablir le nombre de chiffre du resultat de NOT a.
Je vous propose d'utiliser l'algorithme suivant:
i varie de 0 a a.nb: ci= NOT ai si ci=0 alors si i-1tps tps=i Lorsqu'on a effectuer les a.nb + 1 operations, on sait alors que c possede : - tps chiffre si le dernier chiffre de c est nul ! - sinon a.nb
l
Code genere pour appliquer l'operation logique not :
bignb bgnot(bignb a) { bignb result; int i,tps; result=zeronb(); for(i=0;i<=a.nb;i++> { result.nomb[i]=255-a.nomb[i]; if(result.nomb[i]==0) if((i-1)!=tps) tps=i; } if(result.nomb[a.nb]==0) result.nb=tps; else result.nb=a.nb; return(result); }l
Ceci termine ainsi ce second article sur les calculs avec les grands nombres ! Si vous rencontrez des problemes, si quelque chose vous paraŒt incoherent, si vous avez ameliore les algorithmes, si vous voulez me donner votre point de vue sur cet article : ecrivez-moi a : loubail@club-internet.fr
Enfin n'hesitez pas a venir visiter mon site : http://www.multimania.com/loubail : vous y trouverez de nombreuses sources/programmes ;) -