Test de primalité AKS

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 Saxena[1] dans un article scientifique intitulé « PRIMES is in P »[2].

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 repose sur l'identité AKS, généralisation du petit théorème de Fermat : si n est un nombre entier et a un nombre premier avec n alors n\in \mathcal{P}\iff (X+a)^n\equiv X^n+a\mod n où \mathcal{P} est l'ensemble des nombres premiers.

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

Voir aussi

Notes

  1. ↑ Les articles relatifs à ces trois chercheurs sont actuellement disponibles dans la version anglaise de Wikipédia.
  2. ↑ PRIMES is in P [PDF] : article original, cité notamment par un de ses auteurs sur sa page.
  3. ↑ De l'implémentation des tests de primalité de classe AKS [PDF] : R. Crandall, Apple ACG, et J. Papadopoulos, 18 mars 2003.

Liens externes

  • TrigoFacile.com : présentation et démonstration complète et détaillée de l'algorithme. [PDF]
  • (en) MathWorld (Wolfram) : test de primalité AKS.
  • (en) American Mathematical Society (AMS) : article de Folkmar Bornemann sur la découverte publiée par les trois scientifiques indiens. [PDF]

Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Test de primalité AKS de Wikipédia en français (auteurs)

Игры ⚽ Поможем написать реферат

Regardez d'autres dictionnaires:

  • Test de primalite AKS — 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… …   Wikipédia en Français

  • 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… …   Wikipédia en Français

  • Aks — Cette page d’homonymie répertorie les différents sujets et articles partageant un même nom. {{{image}}}   Sigles d une seule lettre   Sigles de deux lettres > Sigles de trois lettres …   Wikipédia en Français

  • AKS — Cette page d’homonymie répertorie les différents sujets et articles partageant un même nom.   Sigles d’une seule lettre   Sigles de deux lettres > Sigles de trois lettres   Sigles de quatre lettres …   Wikipédia en Français

  • Projet:Mathématiques/Liste des articles de mathématiques — Cette page n est plus mise à jour depuis l arrêt de DumZiBoT. Pour demander sa remise en service, faire une requête sur WP:RBOT Cette page recense les articles relatifs aux mathématiques, qui sont liés aux portails de mathématiques, géométrie ou… …   Wikipédia en Français

  • Liste des articles de mathematiques — Projet:Mathématiques/Liste des articles de mathématiques Cette page recense les articles relatifs aux mathématiques, qui sont liés aux portails de mathématiques, géométrie ou probabilités et statistiques via l un des trois bandeaux suivants  …   Wikipédia en Français

  • Liste Des Matières De La Théorie Des Nombres — Article détaillé : cryptologie. . Sommaire 1 Facteur (mathématiques) 2 Fractions 3 Arithmétique modulaire 4 …   Wikipédia en Français

  • Liste des matieres de la theorie des nombres — Liste des matières de la théorie des nombres Article détaillé : cryptologie. . Sommaire 1 Facteur (mathématiques) 2 Fractions 3 Arithmétique modulaire 4 …   Wikipédia en Français

  • Liste des matières de la théorie des nombres — Article détaillé : cryptologie. . Sommaire 1 Facteur (mathématiques) 2 Fractions 3 Arithmétique modulaire 4 Test de primalité e …   Wikipédia en Français

  • Codage RSA — Rivest Shamir Adleman Pour les articles homonymes, voir RSA. Rivest Shamir Adleman ou RSA est un algorithme asymétrique de cryptographie à clé publique, très utilisé dans le commerce électronique, et plus généralement pour échanger des données… …   Wikipédia en Français

Share the article and excerpts

Direct link
… Do a right-click on the link above
and select “Copy Link”