Menu principal

Des algorithmes en Arithmétique

 

Document issu des journées inter-académiques des 8 et 9 octobre 2001

 

Voici quelques algorithmes écrits en « langage algorithmique » ce qui permettra de les programmer « simplement » avec des calculatrices au langage de programmation proche du « basic », du pascal, ou autres comme Maple possédant les structures de boucles avec tests.

Les problèmes rencontrés sont liés à la « taille » des entiers représentés en machine en particulier pour éviter le passage en notation scientifique ! Des algorithmes peuvent permettrent de travailler sur des entiers « longs » en « multiprécision » (cf D. Monasse mathématiques et informatiques chez Vuibert 1988 par exemple).

 

Recherche du PGCD de deux nombres a et b

 

Version 1 à l’aide de l’algorithme d’Euclide

Entrer a

Entrer b

x :=a

y :=b

Si a<b alors début c :=b  b :=a  a :=c  fin

r :=mod(a,b) 

 

 

 

 

 

Tant que r>0 faire

Début

  a :=b

  b :=r

  r :=mod(a,b)

fin

 

 

 

 

 

afficher « le pgcd de » x « et de » y « est » b

 

 

 

 

 

échange de a et de b si a est inférieur à b

on peut prendre r :=a - b*ent(a/b) où ent(n) désigne la partie entière de n si la fonction mod(a,b) qui donne le reste de la division euclidienne n’existe pas dans le langage de programmation utilisé

 

rappel : l’algorithme d’Euclide conduit à la suite des calculs suivants (qui sont effectués dans la boucle Tant que) :

a=bq1+r1 avec r1<b

b=r1q2+r2 avec r2<r1

……..

rk-2=rk-1qk+rk avec rk<rk-1

…….

rn-2=rn-1qn +rn avec rn<rn-1

rn-1=rnqn+1 donc rn+1=0

 

pgcd(a,b) = rn

 

 

Version 2 à l’aide des différences

Entrer a

Entrer b

x :=a

y :=b

Si a<b alors début c :=b  b :=a  a :=c  fin

 

Tant que a¹b faire

Début

Si a>b alors a :=a–b sinon b :=b–a

Fin

 

 

afficher « le pgcd de » x « et de » y « est » b

 

 

 

 

L’échange ici n’est pas nécessaire voire inutile

 

 

 

Si a>b alors le pgcd(a,b)=pgcd (a – b,b) sinon pgcd(a,b)= pgcd (a, b – a)

 

 

 

 

Identité de Bézout

Recherche de f et i entiers relatifs tels que pgcd (a,b)=af+bi

 

L’algorithme reprend le premier algorithme du pgcd et profite de chaque boucle pour calculer f et i tel que xf +yi=b (en fait, mathématiquement, cela devrait être r mais, du fait de l’affectation b :=r, c’est b). De plus on obtient le couple tel que |f| < b et |i| < a.

Entrer a

Entrer b

x :=a

y :=b

Si a<b alors début c :=b  b :=a  a :=c  fin

d :=1  e :=0  g :=0  h :=1

r :=mod(a,b)  q := ent(a/b)

 

 

 

 

Tant que r>0 faire

Début

  f :=d-q*e

  i :=g-q*h

  d :=e   e :=f

  g :=h   h :=i

  a :=b b :=r

  r :=mod(a,b)  q := ent(a/b)

fin

afficher « le pgcd de » x « et de » y « est » b

afficher « et » f * x +i * y = b

 

 

 

D’après l’algorithme d’Euclide :

r1= a – bq1  d’où r1 = af1 + bi1 avec f1= 1 et i1= – q1

r2= b – r1q2 d’où r2 = – q2a+(1+q1q2)b d’où r2= af+ bi2 avec f2= – q2 et i2=1+q1q2

……..

On cherche une récurrence sur les fk et ik tels que

rk= af+ bik

Or rk = rk-2 – rk-1qk

d’où rk = afk-2 + bik-2 – qk(afk-1 + bik-1)

d’où rk = a (fk-2 – fk-1qk)+b(ik-2 – ik-1qk)…….

Donc fk = fk-2 – qk fk-1  et ik= ik-2 – qkik-1

…….

Les mémoires d, e et f jouent les rôles de dk-2, dk-1 et dk. Leurs initialisations sont telles que f1=1 et i1= – q1 ; d’où d := 1 e := 0 g := 0 et h := 1

Les mémoires g, h et i jouent les rôles de gk-2, gk-1 et gk

Les mémoires a, b, q et r jouent les rôles rk-2, rk-1, qk et rk

 

 

 

Tests de primalité (pour savoir si un entier n est un nombre premier)

 

Le test de primalité qui suit est simple et s’applique à des nombres premiers relativement petits. Il n’est pas optimisé pour minimiser le nombre d’opérations.

Il s’agit de rechercher le plus petit nombre premier d diviseur de n s’il existe.

Entrer n

d :=2

p := vrai

Tant que d² £ n et p faire

Début

  r= mod(n,d)

  si r=0 alors p := faux sinon d :=d+1

fin

si p alors afficher n « est premier » sinon afficher n « est divisible par » d

 

 

p est une variable booléenne qui prend deux valeurs : vrai ou faux. On peut choisir, selon le langage de programmation de prendre une variable numérique à deux valeurs  1 ou 0, le test devenant (d² £ n et p = 1)

 

 

 

 

On peut améliorer ce test  en sortant le cas « 2 » et en démarrant à 3 et en balayant de 2 en 2 les impairs. Mieux encore : on sort les cas « 2 » et « 3 » et on balaye les nombres de la forme 6n+1 et 6n+5 (ou encore 6n-1) car il est clair que les nombres premiers sont de cette forme mais hélas tous les nombres de cette forme ne sont pas premiers. Il faut bien que le test ait son intérêt !

 

Algorithme 2 de primalité

 

Entrer n

d :=2

p := vrai

r= mod(n,d)

si r=0 alors p := faux sinon d :=d+1

Tant que d² £ n et p faire

Début

  r= mod(n,d)

  si r=0 alors p := faux sinon d :=d+2

fin

si p alors afficher n « est premier » sinon afficher n « est divisible par » d

 

 

 

 

 

En fait d :=3

 

 

 

On saute d’impair en impair

 

Algorithme 3 de primalité

 

Entrer n

d :=2

p := vrai

r= mod(n,d)

si r=0 alors p := faux

          sinon début d :=d+1  r= mod(n,d) fin

si r=0 alors p := faux

          sinon début d :=d+2  i :=1 fin

Tant que d² £ n et p faire

Début

  r= mod(n,d)

  si r = 0 alors p := faux

              sinon si i est impair alors  début i := i + 1 d :=d+2 fin

                                             sinon  début i := i + 1 d :=d+4 fin

fin

si p alors afficher n « est premier » sinon afficher n « est divisible par » d

 

 

 

 

 

 

En fait d :=3

 

En fait d :=5   de la forme 6n-1

 

 

 

 

Si i est impair alors d est de la forme (6n+1)

Si i est pair alors d est de la forme (6n+4)

 

 


On peut en déduire la construction d’une table des nombres premiers compris entre deux entiers positifs a et b

 

Entrer a

Entrer b

d :=2

n :=a

p := vrai

r= mod(n,d)

si r=0 alors début si n=2 alors afficher n

                                   sinon début n :=n+1 fin

Tant que n<b faire

Début

  p := vrai

  d :=3

  Tant que d² £ n et p faire

  Début

       r= mod(n,d)

       si r=0 alors p := faux sinon d :=d+2

  fin

  si p alors afficher n

  n :=n+2

fin

 

 

 

 

On élimine le cas où a est pair différent de 2

 

 

 

Dans le cas où a<3

 

 

 

 

 

Décomposition d’un nombre entier n en produit de facteurs premiers p1, p2, …pn

 

Entrer n

p :=2

a :=n

d := vrai

Tant que d

Début

  r= mod(a,p)

  si r=0 alors début afficher p   a :=a/p fin

                                   sinon d :=faux

fin

p :=3

d :=vrai

Tant que p2£a faire

Début

  d := vrai

  Tant que d

  Début

     r= mod(a,p)

     si r=0 alors début afficher p   a :=a/p fin

                                   sinon d :=faux

  fin

  p :=p+2

fin

si a ¹1 alors afficher a

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

On peut modifier le programme de façon à n’afficher qu’une fois le diviseur premier pi et de l’élever à la puissance ai du nombre de fois où il est diviseur. Pour ce faire il suffit insérer ici un compteur de boucle pour avoir les exposants ai des pi et de modifier l’affichage :

 

 

Entrer n

p :=2

a :=n

d := vrai

i :=0

Tant que d

Début

  r= mod(a,p)

  si r=0 alors début afficher i :=i+1   a :=a/p fin

            sinon d :=faux

fin

si i¹0 alors afficher p puissance i

p :=3

d :=vrai

i :=0

Tant que p2£a faire

Début

  d := vrai

  i :=0

  Tant que d

  Début

     r= mod(a,p)

     si r=0 alors début i :=i+1   a :=a/p fin

                                   sinon d :=faux

  fin

  si i¹0 alors afficher p puissance i

  p :=p+2

fin

si a¹1 alors afficher a

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

En fait on essaie les nombres impairs dont le carré est inférieur à a car on n’a pas la liste utile de nombres premiers

 

 

 

 

 

C’est le cas d’un dernier diviseur premier

 

 

 

Il existe d’autres tests de primalité basés sur les propriétés des congruences .

D’après le « petit » théorème de Fermat :

si p est premier et si n n’est pas un multiple de p alors np–1 º 1 (modulo p).

On en déduit le corollaire :

si a et n sont premiers entre eux et si n divise an–1–1 alors n n’est pas premier.

Cela pourrait constituer un test s’il n’existait des nombres n dit pseudo premiers en base a qui vérifie an–1 º 1 (modulo n) et sont premiers avec a. Le plus petit pseudo premier en base 2 est 341=11 ´ 31. Et s’il n’existait des nombres qui vérifierait la congruence pour tout a premier avec n. Par exemple 1729=7´13´19. On fait appel au concept de pseudo primalité forte de base a.

Définition : soit n un entier impair (alors on peut écrire que n–1=2s.m avec m impair) n est pseudo premier fort en base a si ou bien am º 1 (modulo n), ou bien il existe r tel que 0£r£s–1 vérifiant

m2r = k  et  ak º  – 1 (modulo n).

Le plus petit nombre pseudo premier pour la base 2 et non premier est 2047=23´89, 1373653=829´1657 pour les bases 2 et 3, 25326001=2251´11251 pour les bases 2,3 et 5, 3215031751=151´751´78351 pour les bases 2,3,5,7.

Cela procure un test de primalité de n selon la taille de n :

On cherche s et m tel que n=1+ 2s.m avec m impair et on vérifie l’une ou l’autre des congruences

 am º 1 (modulo n). ou bien il existe r tel que 0£r£s–1 vérifiant  m2r = k  et  ak º  – 1 (modulo n) pour a premier pris dans 2,3,5,7 si n a neuf chiffres.

Ces tests sont difficiles à écrire ici car il nécessite de travailler en « double précision » ou mieux en « multiprécision ». Ils utilisent le calcul de ak (modulo n).

 

Algorithme « rapide » du calcul de ak (modulo n).

 

Entrer a

Entrer n

Entrer k

u :=1

v :=mod(a,n)

h :=k

tant que h>0 faire

  début

   i := mod(h,2)

   si i =1 alors u := mod(v.u , n)

   h :=ent(h/2)

   v :=mod(v2 , n)

  fin

afficher u

 

Preuve :

h décroît vers 0

 

 

 

 

 

à chaque passage dans la boucle « tant que » on a

uvh º ak (modulo n)

i permet de savoir si h est impair

 

exemple : calcul de a11 modulo n

u prend successivement les valeurs 1, a, a3,a3,a11 tandis que v est congru à a, a2, a4, a8,a16 , h prend les valeurs 11, 5, 2, 1, 0 et i prend les valeurs 1, 1, 0, 1 évidemment cela est à rapprocher de l’écriture en base 2 de 11 soit 1011.

.

 

Enfin voici un

Algorithme permettant de faire la division euclidienne de a par b

Cet algorithme a la particularité importante en informatique (où les nombres sont représentés en binaire) de ne faire que des additions ou des soustractions ou des multiplications par 2 ou divisions par 2. Cet algorithme est l’équivalent itératif de la propriété récursive basée sur les remarques suivantes : a et b étant donnés dans le cas général a = bq + r avec r < b

 

si a < b alors q=0 et r= a sinon si on pose q=2q1+q2 avec q2=o ou q2=1 on a alors a= 2bq1+ravec r2 < 2b et  r2= bq2+r  d’où  r2=r  si q2=0 et r2=r+b si q2=1

autrement dit si r < b alors q = 2q1 et r=r2 sinon q =2q1+1 et r = r2–b.


 

D’où la procédure récursive :

 

procédure diveuclid(a,b entiers , var q,r entiers)

variables locales a,b

début

si a<b alors début q :=0  r := a fin

            sinon             début

                                 diveuclid(a, 2*b,q,r)

                        si r<b alors q :=2*q

                                    sinon début

                                                q :=2*q+1

                                                r :=r –u

          fin

                        fin

fin procédure

Attention dans la procédure récursive q et r sont passés par variable et non par valeur. On ne maîtrise donc pas les contenus de ces mémoires.

 

On en déduit l’algorithme itératif associé :

 

Entrer a

Entrer b

 

u :=b

 

Tant que u£a faire

début

u :=2*u

fin

q :=0 r :=a

tant que u ¹ b faire

début

u := u/2

si r < u alors q := 2*q

           sinon début q := 2*q+1   r := r – u fin

fin

 

afficher « quotient » q « et reste » r

Si on regarde l’algorithme itératif :

 

 

 

 

Dans la première boucle, il s’agit donc de trouver le plus petit k tel que 2kb>a (descente dans l’arbre des appels récursifs)

 

 

 

Dans la deuxième boucle, on remonte l’arbre des appels récursifs en calculant de proche en proche q et r.

 

En général on a besoin d’un compteur de première boucle pour contrôler la deuxième boucle, ici c’est inutile de par la condition u ¹ b qui la gère.

 

Reste (et ce n’est pas le plus simple !) à écrire ces programmes pour différentes machines et différents langages !