Une partie seulement de cet exposé est présent sur le site. La version complète, qui comprend la démonstration intégrale de la validité de l'algorithme AKS, n'est disponible que dans le fichier rédigé à l'aide d'AMS-LaTeX, téléchargeable dans une version PDF 
pour en faciliter la consultation et l'impression.readlib(iroot):
est_puissance := proc(n :: integer)
local fin, i;
fin := floor(evalf(log[2](n)));
for i from 2 to fin do
if iroot(n, i)^i = n then
RETURN(i);
fi;
od;
RETURN(1);
end:cherche_r := proc(n :: integer)
local fin1, fin2, r, k, test;
fin1 := floor(evalf(16*log[2](n)^5));
fin2 := floor(evalf(4*log[2](n)^2));
for r from 2 to fin1 do
test := true;
for k from 1 to fin2 do
if Power(n, k) mod r = 1 then
test := false;
break;
fi;
od;
if test then
RETURN(r);
fi;
od;
end:est_trivialement_divisible := proc(n :: integer, r :: integer)
local a, diviseur;
for a from 2 to r do
diviseur := gcd(a, n);
if (diviseur <> n) and (diviseur <> 1) then
RETURN(a);
fi;
od;
RETURN(1);
end:teste_congruence := proc(n :: integer, r :: integer)
local a, fin;
fin := floor(evalf(2*sqrt(numtheory[phi](r))*log[2](n)));
for a from 1 to fin do
if Powmod(X + a, n, X^r - 1, X) mod n <> Powmod(X^n + a, 1, X^r - 1, X) mod n then
RETURN(a);
fi;
od;
RETURN(0);
end:premier := proc(n)
local a, b, c, r, compteur;
compteur := time();if not type(n, posint) then
RETURN(n, `n'est pas valable. Veuillez entrer un entier naturel non nul.`);
fi;if n = 1 then
RETURN(`1 n'est pas un nombre premier -- temps : `, time() - compteur, ` s.`);
fi;a := est_puissance(n);
if a <> 1 then
RETURN(cat(n, ` est une puissance d'ordre `, a, ` -- temps : `, time() - compteur, ` s.`));
fi;r := cherche_r(n);
b := est_trivialement_divisible(n, r);
if b <> 1 then
RETURN(cat(n, ` est divisible par `, b, ` -- temps : `, time() - compteur, ` s.`));
fi;if n <= r then
RETURN(cat(n, ` est un nombre premier -- temps : `, time() - compteur, ` s.`));
fi;c := teste_congruence(n, r);
if c <> 0 then
RETURN(cat(n, ` n'est pas un nombre premier. Il ne vérifie pas la congruence : (X + `, c, `)^`, n, ` = X^`, n, ` + `, c, ` [X^`, r, ` - 1, `, n, `] -- temps : `, time() - compteur, ` s.`));
fi;RETURN(cat(n, ` est bien un nombre premier -- temps : `, time() - compteur, ` s.`));
end:
Étudions sur quelques exemples le comportement de l'algorithme :
> for i in [-2, 1, 533, 3^47, 89, 271] do premier(i); od;
-2 n'est pas valable. Veuillez entrer un entier naturel non nul.
1 n'est pas un nombre premier -- temps : 0 s.
533 est divisible par 13 -- temps : .020 s.
26588814358957503287787 est une puissance d'ordre 47 -- temps : .010 s.
89 est un nombre premier -- temps : .070 s.
271 est bien un nombre premier -- temps : .430 s.
271 est en fait le premier nombre qui n'est déclaré premier qu'à la dernière étape – d'où l'utilité de la distinction de la réponse par rapport à la quatrième étape, en rajoutant l'adverbe « bien ».
Testons maintenant le temps mis par l'algorithme pour déterminer la primarité des nombres suivants sur un PC de microprocesseur cadencé à 1,6 GHz :
> for i in [200, 300, 500, 1000, 2000] do premier(ithprime(i)); od;
1223 est bien un nombre premier -- temps : 2.2330 s.
1987 est bien un nombre premier -- temps : 4.637 s.
3571 est bien un nombre premier -- temps : 42.441 s.
7919 est bien un nombre premier -- temps : 109.257 s.
17389 est bien un nombre premier -- temps : 191.506 s.
Il est possible d'implémenter l'algorithme « à vue » dans un langage de calcul formel. Toutefois, on remarque aussitôt que le temps de calcul devient rapidement rédhibitoire, quand bien même les nombres testés sont relativement petits. Assurément, si l'on utilise la fonction prédéfinie isprime de Maple, le même résultat est donné en moins d'un dixième de seconde pour de tels nombres, et en quelques dizaines de secondes pour des nombres de plus de six cents chiffres.
Toutefois, la documentation de Maple précise que la fonction isprime est un test probabiliste de non-primarité, en ce sens qu'il subsiste toujours une probabilité d'erreur lorsque cette fonction retourne que n est premier.
Nonobstant, « aucun contre-exemple n'est connu et il est conjecturé qu'un tel exemple comporte plusieurs centaines de chiffres ».
Il n'en reste pas moins que le test isprime n'est pas déterministe, au contraire de l'algorithme AKS.
On peut aussi vérifier le fonctionnement du test de congruence à la cinquième étape de l'algorithme sur l'exemple traité lors de la présentation de l'algorithme AKS. Le troisième nombre de Carmichael n = 1729 vérifie la congruence pour tous les a testés avec r = 3, mais pas avec r = 5 :
> teste_congruence(1729, 3);
0
> teste_congruence(1729, 5);
1
Notons que la fonction inerte Powmod de Maple, qui permet de calculer des puissances de polynômes, voit ses capacités dépassées pour de grandes valeurs de r et de n.
Il est aussi assuré que la complexité de l'algorithme n'est pas optimale : il faudrait en fait implémenter des outils complexes de calculs rapides, de multiplication de polynômes à base de transformée de Fourier rapide et de congruences modulo un polynôme, pour ne citer que ces exemples.
En outre, ce n'est pas un langage de calcul symbolique comme Maple qui convient pour ce genre d'algorithme ; un langage de programmation plus avancé et optimisé, tel le C++ ou le C#, donnerait des résultats beaucoup plus satisfaisants. Mais une telle implémentation requerrait beaucoup plus de travail.
De nombreuses personnes ont proposé une implémentation de l'algorithme AKS en divers langages de programmation.
En pratique, les tests de Miller sont beaucoup plus rapides, bien qu'ils soient quand même lents à cause du calcul de nombreuses exponentielles modulaires ; l'algorithme à base de courbes elliptiques dû à Atkin est à même de prouver la primarité de nombres de 512 bits en une seconde, de 1024 bits en une minute, et des nombres de l'ordre de 210 000 en un temps « raisonnable » – un mois – sur un Pentium-III à 450 MHz. Ce dernier algorithme, supposé polynomial, est néanmoins probabiliste ; un avantage est qu'il fournit en outre un certificat vérifiable polynomialement en O(log(n)4).
Il n'en faut pas moins oublier que, quoique la complexité temporelle de l'algorithme soit polynomiale, sa complexité spatiale n'est pas du tout optimisée. L'algorithme nécessite en effet beaucoup de mémoire lors de son utilisation et conduit à la manipulation de données volumineuses.
De plus, l'entier r qui est déterminé par l'algorithme AKS n'est pas le plus petit qui puisse convenir pour les tests de la cinquième étape. Pour n = 2512, l'entier r le plus optimiste est de l'ordre de 16 × 106, ce qui conduit à manipuler des polynômes denses de plus de 1 gigaoctet comportant plusieurs dizaines de milliers de termes, ce qui est peut-être envisageable.
Le test de la primarité du nombre n = 109+7 prend une semaine sur un PC à 700 MHz avec l'algorithme normal, en utilisant GMP 4.1 : chaque calcul intermédiaire dure 44 secondes à cause du degré élevé des polynômes manipulés. En fait, il est possible de trouver un entier r plus petit (r = 359 au lieu de 57 287) qui conduit à un temps de 6 minutes et 9 secondes, ce qui constitue un net progrès et rend l'algorithme utilisable en pratique.
Pour l'anecdote, on estime que 1025 opérations élémentaires ont été réalisées par l'ensemble des microprocesseurs d'ordinateur depuis qu'ils existent. En ne tenant pas compte des problèmes de mémoire spatiale, c'est le nombre d'opérations nécessaires à l'algorithme AKS pour déterminer la primarité d'un nombre à 100 000 chiffres. Or, sachant que les plus grands nombres premiers connus ont plus de quatre millions de chiffres, on se rend bien compte de l'inefficacité pratique de cet algorithme...
↑ Retour au haut de cette page