Test de primalité AKS

L'algorithme détermine si un nombre est premier ou composé (au sens de la factorisation).

L'algorithme repose sur la généralisation suivante du petit théorème de Fermat : pour tout entier n ≥ 2 et tout entier a premier avec n,

n est un nombre premier si et seulement si ${\displaystyle (X+a)^{n}\equiv X^{n}+a\mod n,}$[4]

qui résulte d'une propriété des coefficients binomiaux :

n est un nombre premier si et seulement si ${\displaystyle \forall k\in \{1,\ldots ,n-1\},{n \choose k}\equiv 0\mod n.}$

L'objet d'AKS est d'exploiter efficacement cette propriété.

L'algorithme est globalement le suivant[4]:

procédure AKS(${\displaystyle n}$):
   Si ${\displaystyle n=a^{b}}$ avec ${\displaystyle a,b\in \mathbb {N} }$ et ${\displaystyle b>1}$ alors renvoyer non-premier  (étape 1)
   Construire le plus petit entier ${\displaystyle r}$ tel que l'ordre de ${\displaystyle n}$ modulo ${\displaystyle r}$ soit supérieur à ${\displaystyle 4\log ^{2}n}$  (étape 2)
   Si pgcd(${\displaystyle a,n}$) != 1 et pgcd(${\displaystyle a,n}$)!= n pour un certain ${\displaystyle a\leq r}$ alors renvoyer non-premier  (étape 3)
   Si ${\displaystyle n\leq r}$ alors renvoyer premier  (étape 4)
   Pour ${\displaystyle a}$ compris entre 1 et ${\displaystyle \left\lfloor 2{\sqrt {\varphi (r)}}\log n\right\rfloor }$ faire[note 1]:
        Si ${\displaystyle (X+a)^{n}\not \equiv X^{n}+a\mod (X^{r}-1)\mathbb {Z} /n\mathbb {Z} [X]}$ alors renvoyer non-premier  (étape 5)
   Renvoyer premier  (étape 6)

On cherche à démontrer que l'algorithme renvoie premier si, et seulement si son argument est un nombre premier. La preuve repose sur des résultats sur les corps finis et de diverses inégalités dont la plupart sont démontrées par récurrence.

On note tout au long de la démonstration ${\displaystyle \omega _{r}(n)}$ l'ordre (théorie des groupes) de ${\displaystyle n}$ dans le groupe des inversibles de l'anneau ${\displaystyle {\dfrac {\mathbb {Z} }{n\mathbb {Z} }}}$ et ${\displaystyle \varphi (n)}$ l'Indicatrice d'Euler.

On suppose tout d'abord que ${\displaystyle n}$ est premier, l'algorithme peut renvoyer une valeur (premier ou non-premier) à cinq différentes étapes:

• Il est clair que l'algorithme ne peut pas renvoyer non-premier aux étapes 1 et 3.
• D'après le Théorème de Lagrange sur les groupes, l'ordre de tout élément divise l'ordre du groupe. Ainsi, par définition de ${\displaystyle r}$, ${\displaystyle 4\log ^{2}(n)\leq \omega _{r}(n)\leq \varphi (r)\leq r}$. L'étape 3 nous assure alors que tous les ${\displaystyle a}$ considérés sont premiers avec ${\displaystyle n}$. Dès lors, de la relation donnée par la généralisation du petit théorème de Fermat, nous pouvons en déduire que l'algorithme ne peut pas renvoyer non-premier à l'étape 5.

Réciproquement, on suppose que l'algorithme renvoie premier. Si l'algorithme a renvoyé premier à l'étape 4, alors ${\displaystyle n}$ est premier avec tous les entiers strictement inférieurs à lui-même ce qui assure la primalité de ${\displaystyle n}$.

Reste à démontrer que si l'algorithme renvoie premier à l'étape 6, alors ${\displaystyle n}$ est bien premier.

La complexité temporelle originale est en ${\displaystyle O}$${\displaystyle (\log ^{12}n)}$, ${\displaystyle n}$ désignant le nombre testé. Il existe plusieurs variantes et raffinements de l'algorithme qui en affectent la complexité. La version décrite dans la section précédente a une complexité ${\displaystyle O(\log ^{10,5}n)}$, c'est-à-dire une complexité polynomiale en la taille de l'entrée[4] - [note 2]. La complexité d'AKS est aussi affectée par le statut de diverses conjectures.

• Si la conjecture d'Artin sur les racines primitives est vraie, alors l'algorithme AKS a une complexité de l'ordre de ${\displaystyle O(\log ^{6}n)}$[4];
• Si la conjecture d'Agrawal (en) est vraie, alors la complexité d'AKS est de l'ordre de ${\displaystyle O(\log ^{3}n)}$[4].

• Crible d'Ératosthène : Test de primalité du IIIe siècle av. J.-C.
• Test de primalité de Fermat : Test probabiliste simple.
• Test de primalité de Solovay-Strassen : Test probabiliste inconditionnel.
• Test de primalité de Miller-Rabin : Test probabiliste inconditionnel, basé sur le test déterministe de G.L. Miller supposant l'hypothèse de Riemann généralisée.
• Test de primalité de Lucas-Lehmer : Non généraliste, il permet de tester la primalité de nombres particuliers.
• Conjecture d'Agrawal (en)

• TrigoFacile.com : Présentation et démonstration complète et détaillée de l'algorithme. [PDF]
• (en) Eric W. Weisstein, « AKS Primality Test », sur MathWorld
• (en) PRIMES Is in P: A Breakthrough for “Everyman” : Article de Folkmar Bornemann dans les Notices of the American Mathematical Society, sur la découverte publiée par les trois scientifiques indiens. [PDF]