Page d'accueil	encyclopedie-enligne.com en page d'accueil
Liste Articles: [0-A] [A-C] [C-F] [F-J] [J-M] [M-P] [P-S] [S-Z] | Liste Catégories | Une page au hasard | Pages liées

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 algorithme déterministe de preuve de primalité découvert et publié par trois scientifiques indiens nommés Manindra Agrawal, Neeraj Kayal et Nitin Saxena le 6 août 2002 dans un article scientifique intitulé « PRIMES is in P ».

L'algorithme, qui fut amélioré par d'autres plus tard, détermine si un nombre est un nombre premier ou un nombre composé et s'exécute en temps polynômial.

L'algorithme AKS n'est pas le premier test de primalité général s'exécutant en un temps polynômial, cepandant il posséde 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 polynômial démontrable pour toutes ses entrées. C'est de plus un algorithme déterministe : il permet de déterminer de façon certaine qu'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 donc une certaine probabilité d'erreur sur la réponse donnée lorsqu'elle est affirmative.

Le temps asymptotique de complexité de l'algorithme original est O(log¹²n).

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) qui ont amélioré la vitesse de AKS selon des ordres d'ampleur. En raison des multiples variantes, Crandall et Papadopoulos se réfèrent aux algorithmes de « classe AKS » dans leur article scientifique « De l'implémentation des tests de primalité de classe AKS » publié en mars 2003.

Voir aussi

• Nombre premier
• Test de primalité de Fermat (test probabiliste simple)
• Test de primalité de Solovay-Strassen (test probabiliste inconditionel)
• Test de primalité de Miller-Rabin (test probabiliste inconditionel, 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 nombre particuliers)
• Théorie des nombres
• Mathématiques

Liens externes

• MathWorld: test de primalité AKS (en anglais)
• PRIMES is in P: l'article scientifique original décrivant le test de primalité AKS (en anglais) (PDF)
• R. Crandall, Apple ACG, et J. Papadopoulos (18 mars 2003) : De l'implémentation des tests de primalité de classe AKS (en anglais) (PDF)
• Article par Borneman, contenant les photos et informations à propos des trois scientifiques indiens (en anglais) (PDF)