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).
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)
|
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= af2 + bi2 avec f2= – q2 et i2=1+q1q2 …….. On cherche une récurrence sur les fk et ik tels que rk= afk + 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
|
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
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+r2 avec 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 !