Voir la source de Test de primalité AKS

Le '''test de primalité AKS''' (aussi connu comme le '''test de primalité Agrawal-Kayal-Saxena''' et le '''test cyclotomique AKS''') est un [[test de primalité|algorithme de preuve de primalité]] déterministe et généraliste (fonctionne pour tous les nombres) publié le {{date|6|août|2002|en informatique}} par trois scientifiques [[Inde|indiens]] nommés [[Manindra Agrawal]], [[Neeraj Kayal]] et [[Nitin Saxena]] (A.K.S). Ce test est le premier en mesure de déterminer la primalité d'un nombre dans un [[P (complexité)|temps polynomial]]. Ce test a été publié dans un article scientifique intitulé ''« PRIMES is in P »''<ref>[http://www.cse.iitk.ac.in/users/manindra/algebra/primality_original.pdf PRIMES is in P] {{pdf}} : article original, cité notamment par un de ses auteurs sur [http://www.cse.iitk.ac.in/users/manindra/publications.html sa page].</ref>{{,}}<ref>L'article « définitif », revu par les pairs, est paru en 2004 : {{article|prénom1=Manindra|nom1=Agrawal|prénom2=Neeraj|nom2=Kayal|prénom3=Nitin|nom3=Saxena
|titre=PRIMES is in P
|journal=[[Annals of Mathematics]]. Second Series|volume=160|numéro=2|pages=781-793
|année=2004|doi=10.4007/annals.2004.160.781|id=AKS
|math reviews=MR2123939
|zbl=02157791
|url=http://annals.math.princeton.edu/wp-content/uploads/annals-v160-n2-p12.pdf}}</ref>. Cet article leur a valu le prestigieux [[prix Gödel]] 2006<ref>[http://www.eatcs.org/index.php/component/content/article/502 Page du prix Gödel 2006]</ref>.

==L'algorithme==

===Principe===
L'algorithme détermine si un nombre est [[nombre premier|premier]] ou [[nombre composé|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 {{math|''n ''≥ 2}} et tout entier ''{{math|a}} ''[[Nombres premiers entre eux|premier avec]] {{math|''n''}},
<center>{{math|''n''}} est un [[nombre premier]] si et seulement si <math>(X+a)^n\equiv X^n+a\mod n,</math><ref name = "boyer"/></center>
qui résulte d'[[Coefficient binomial#Diviseurs et coefficients binomiaux|une propriété des coefficients binomiaux]] :
<center>{{math|''n''}} est un nombre premier si et seulement si <math>\forall k\in\{1,\ldots,n-1\}, {n\choose k}\equiv0\mod n.</math></center>
L'objet d'AKS est d'exploiter efficacement cette propriété.

=== Fonctionnement ===
L'algorithme est globalement le suivant<ref name = "boyer"/>:
 procédure AKS(<math>n</math>):
    Si <math>n = a^b</math> avec <math>a,b \in \N</math> et <math>b > 1</math> alors renvoyer '''non-premier'''  (étape 1)
    Construire le plus petit entier <math>r</math> tel que l'[[Ordre (théorie des groupes)|ordre]] de <math>n</math> modulo <math>r</math> soit supérieur à <math>4 \log^2 n</math>  (étape 2)
    Si [[Plus grand commun diviseur|pgcd]](<math>a,n</math>) != 1 et [[Plus grand commun diviseur|pgcd]](<math>a,n</math>)!= n pour un certain <math>a \leq r</math> alors renvoyer '''non-premier'''  (étape 3)
    Si <math>n \leq r</math> alors renvoyer '''premier'''  (étape 4)
    Pour <math>a</math> compris entre 1 et <math>\left \lfloor 2 \sqrt{\varphi(r)}\log n \right\rfloor</math> faire<ref group="note">La lettre <math>\varphi</math> désigne la fonction [[indicatrice d'Euler]].</ref>:
         Si <math>(X + a)^n \not\equiv X^n + a \mod (X^r - 1)\Z/n\Z[X]</math> alors renvoyer '''non-premier'''  (étape 5)
    Renvoyer '''premier'''  (étape 6)

=== Preuve ===
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 <math>\omega_r(n)</math> l'[[ordre (théorie des groupes)]] de <math>n</math> dans le groupe des inversibles de l'anneau <math>\dfrac{\mathbb{Z}}{n\mathbb{Z}}</math> et <math>\varphi(n)</math> [[Indicatrice d'Euler|l'Indicatrice d'Euler]].

On suppose tout d'abord que <math>n</math> 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 (théorie des groupes)|ordre]] de tout élément divise l'ordre du groupe. Ainsi, par définition de <math>r</math>, <math>4\log ^2(n) \leq \omega_r(n) \leq \varphi(r) \leq r</math>. L'étape 3 nous assure alors que tous les <math>a</math> considérés sont premiers avec <math>n</math>. 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 <math>n</math> est premier avec tous les entiers strictement inférieurs à lui-même ce qui assure la primalité de <math>n</math>.

Reste à démontrer que si l'algorithme renvoie '''premier''' à l'étape 6, alors <math>n</math> est bien premier.

=== Complexité ===
La [[complexité en temps|complexité temporelle]] originale est en [[notation O|<math>O</math>]]<math>(\log^{12} n)</math>, <math>n</math> 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é <math>O(\log^{10,5} n)</math>, c'est-à-dire une complexité polynomiale en la taille de l'entrée<ref name = "boyer">{{Ouvrage|langue=fr|auteur1=Pascal Boyer|titre=Petit compagnon des nombres et de leurs applications|lieu=Paris|éditeur=Calvage et Mounet|année=2019|pages totales=648|passage=212-213|isbn=978-2-916352-75-6|partie=II. Nombres premiers|numéro chapitre=3.4.|titre chapitre=AKS}}.</ref>{{,}}<ref group = "note" name = "log"/>. La complexité d'AKS est aussi affectée par le statut de diverses [[conjecture]]s.

==== Implications 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 <math>O(\log^{6} n)</math><ref name = "boyer"/>;
* Si la {{Lien|trad = Agrawal's conjecture|fr = Conjecture d'Agrawal|texte = conjecture d'Agrawal}} est vraie, alors la complexité d'AKS est de l'ordre de <math>O(\log^{3} n)</math><ref name = "boyer"/>.

==Comparaison avec les autres tests de primalité==

L'algorithme AKS n'est pas le premier test de primalité général s'exécutant en un [[Théorie de la complexité des algorithmes#Classes de complexité|temps polynomial]] en le nombre de chiffres du nombre à tester<ref group="note" name="log">Le nombre de chiffres d'un nombre <math>n</math> est de l'ordre de <math>\log n</math>.</ref>. Il possède cependant une différence clé par rapport à tous les algorithmes généraux de preuve de primalité précédents : il ne repose pas sur une [[hypothèse]] non démontrée (telle que l'[[hypothèse de Riemann]]) pour être vrai et pour avoir un temps polynomial démontrable pour toutes ses entrées.
De plus c'est un algorithme [[Test de primalité#Tests déterministes rapides|déterministe]] : il permet de déterminer de façon certaine si un nombre est premier (tout comme le [[crible d'Ératosthène]]) par opposition aux tests [[Test de primalité#Tests probabilistes|probabilistes]], qui permettent seulement de déterminer si un nombre est un [[nombre premier probable]] et qui comportent de fait une certaine probabilité d'erreur sur la réponse donnée lorsque celle-ci est affirmative.

==Variantes==

Quelques mois après la découverte, de nombreuses variantes sont apparues : ''Lenstra 2002, Pomerance 2002, Berrizbeitia 2003, Cheng 2003, Bernstein 2003a/b, Lenstra et Pomerance 2003''. Elles ont amélioré la vitesse d'exécution de l'algorithme AKS à différentes ampleurs. Ces multiples variantes de l'algorithme sont référencées sous la notion de « classe AKS », introduite par Crandall et Papadopoulos en 2003<ref>{{en}} [https://images.apple.com/acg/pdf/aks3.pdf On the implementation of AKS-class primality tests] {{pdf}} : R. Crandall et J. Papadopoulos, 18 mars 2003</ref>.

== Voir aussi ==

===Articles connexes===
* [[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. 
*{{Lien|trad=Agrawal's conjecture|Conjecture d'Agrawal}}

===Liens externes===
* [http://www.trigofacile.com/maths/curiosite/primarite/aks/pdf/algorithme-aks.pdf TrigoFacile.com] : Présentation et démonstration complète et détaillée de l'algorithme. {{pdf}} 
* {{MathWorld|nom_url=AKSPrimalityTest|titre=AKS Primality Test}}
* {{en}} [http://www.ams.org/notices/200305/fea-bornemann.pdf 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}}

==Notes et références==
{{Traduction/Référence|en|AKS primality test|8000113|type=note}}
=== Notes ===
{{Références|group = "note"}}

=== Références ===
<references /> 

{{portail|mathématiques|Cryptologie|informatique théorique}}

[[Catégorie:Test de primalité|AKS]]