Test de primalité AKS

Infos
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é le 6 août 2002 par trois scientifiques indiens nommés Manindra Agrawal, Neeraj Kayal et Nitin SaxenaLes articles relatifs à ces trois chercheurs sont actuellement disponibles dans la version anglaise de Wikipédia. dans un article scientifique intitul
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é le 6 août 2002 par trois scientifiques indiens nommés Manindra Agrawal, Neeraj Kayal et Nitin SaxenaLes articles relatifs à ces trois chercheurs sont actuellement disponibles dans la version anglaise de Wikipédia. dans un article scientifique intitulé « PRIMES is in P » : article original, cité notamment par un de ses auteurs sur .. L'algorithme détermine si un nombre est premier ou composé (au sens de la factorisation). La complexité temporelle originale est en O((log n)12). L'algorithme AKS n'est pas le premier test de primalité général s'exécutant en un temps polynomial. 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. 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 : R. Crandall, Apple ACG, et J. Papadopoulos, 18 mars 2003..

Voir aussi

- Nombre premier.
- 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.

Notes

==
Sujets connexes
Algorithmique   Crible d'Ératosthène   Hypothèse   Hypothèse de Riemann   Hypothèse de Riemann généralisée   Inde   Manindra Agrawal   Nombre composé   Nombre premier   Nombre premier probable   Test de primalité   Test de primalité de Fermat   Test de primalité de Lucas-Lehmer   Test de primalité de Miller-Rabin   Test de primalité de Solovay-Strassen   Théorie de la complexité  
#
Accident de Beaune   Amélie Mauresmo   Anisocytose   C3H6O   CA Paris   Carole Richert   Catherinettes   Chaleur massique   Championnat de Tunisie de football D2   Classement mondial des entreprises leader par secteur   Col du Bonhomme (Vosges)   De viris illustribus (Lhomond)   Dolcett   EGP  
^