Test de primalité AKS

test de primalité déterministe, généraliste et polynomial

Le test de primalité AKS (aussi connu comme le test de primalité Agrawal-Kayal-Saxena et le test cyclotomique AKS) est un algorithme de preuve de primalité déterministe et généraliste (fonctionne pour tous les nombres) publié le par trois scientifiques 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 temps polynomial. Ce test a été publié dans un article scientifique intitulé « PRIMES is in P »[1],[2]. Cet article leur a valu le prestigieux prix Gödel 2006[3].

L'algorithmeModifier

PrincipeModifier

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  [4]

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

n est un nombre premier si et seulement si  

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

FonctionnementModifier

L'algorithme est globalement le suivant[4]:

procédure AKS( ):
   Si   avec   et   alors renvoyer non-premier
   Construire le plus petit entier   tel que l'ordre de   modulo   soit supérieur à  
   Si pgcd( ) != 1 pour un certain   alors renvoyer non-premier
   Si   alors renvoyer premier
   Pour   compris entre 1 et   faire[note 1]:
        Si   alors renvoyer non-premier
   Renvoyer premier

PreuveModifier

ComplexitéModifier

La complexité temporelle originale est en   . 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é  , 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.

Implications de diverses conjecturesModifier

Comparaison avec les autres tests de primalitéModifier

L'algorithme AKS n'est pas le premier test de primalité général s'exécutant en un temps polynomial en le nombre de chiffres du nombre à tester[note 2]. 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 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 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.

VariantesModifier

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[5].

Voir aussiModifier

Articles connexesModifier

Liens externesModifier

Notes et référencesModifier

(en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « AKS primality test » (voir la liste des auteurs).

NotesModifier

  1. La lettre   désigne la fonction indicatrice d'Euler.
  2. a et b Le nombre de chiffres d'un nombre   est de l'ordre de  .

RéférencesModifier

  1. PRIMES is in P [PDF] : article original, cité notamment par un de ses auteurs sur sa page.
  2. L'article « définitif », revu par les pairs, est paru en 2004 : Manindra Agrawal, Neeraj Kayal et Nitin Saxena, « PRIMES is in P », Annals of Mathematics. Second Series, vol. 160, no 2,‎ , p. 781-793 (DOI 10.4007/annals.2004.160.781, Math Reviews MR2123939, zbMATH 02157791, lire en ligne)
  3. Page du prix Gödel 2006
  4. a b c d et e Pascal Boyer, Petit compagnon des nombres et de leurs applications, Paris, Calvage et Mounet, , 648 p. (ISBN 978-2-916352-75-6), II. Nombres premiers, chap. 3.4. (« AKS »), p. 212-213.
  5. (en) On the implementation of AKS-class primality tests [PDF] : R. Crandall et J. Papadopoulos, 18 mars 2003