Une partie seulement de cet exposé est présent sur le site. La version complète, qui comprend la démonstration intégrale de la validité de l'algorithme AKS, n'est disponible que dans le fichier rédigé à l'aide d'AMS-LaTeX, téléchargeable dans une version PDF 
pour en faciliter la consultation et l'impression.« Le plus beau résultat mathématique des dix dernières années. » (Shafi Goldwasser)
En août 2002, le professeur Agrawal et deux de ses élèves, Kayal et Saxena, résolvent une ancienne conjecture en théorie de la complexité : le test en temps polynomial de la primarité d'un nombre donné.
Cet exposé sur l'algorithme AKS est réalisé par le webmaster du site TrigoFACILE, Julien Élie, dans le cadre d'un Travail d'Initiative Personnelle et Encadrée, autrement dit TIPE, rédigé en 2003 sous la direction de MM. Serge Francinou et Philippe Espéret, professeurs de mathématiques au Lycée Henri-IV de Paris.
« Problema, numeros primos a compositis dignoscendi, hosque in factores suos primos resoluendi, ad grauissima ac utilissima totius Arithmeticae pertinere, et geometrarum tum ueterum tum recentiorum industriam ac sagacitatem occupauisse, tam notum est, ut de hac re copiose loqui superfluum foret. [...]
« Prae tereaque scientiae dignitas requirere uidetur, ut omnia subsidia ad solutionem problematis tam elegantis ac celebris sedulo excolantur. »« Le problème où l'on se propose de distinguer les nombres premiers des nombres composés, et de résoudre ceux-ci en leurs facteurs premiers, est connu comme l'un des plus importants et des plus utiles de toute l'Arithmétique ; il a sollicité l'industrie et la sagacité des géomètres tant anciens que modernes, à un point tel qu'il serait superflu de discuter en détail à cet égard. [...]
« De surcroît, la dignité de la science même semble demander que tous les secours possibles soient explorés avec soin pour parvenir à la solution d'un problème si élégant et si célèbre. »Johann Carl Friedrich Gauß, Disquisitiones Arithmeticae, 329.
Dans cet exposé, je m'intéresse à la seconde version parue en mars 2003 de l'algorithme AKS et me propose de démontrer intégralement sa validité. La démonstration est entièrement accessible et ne repose sur aucune hypothèse.
Quant à l'un des meilleurs spécialistes en théorie des nombres, Carl Pomerance, travaillant pour les laboratoires Bell, à peine eut-il discuté durant le déjeuner avec ses collègues sur le nouvel algorithme qu'il organisa précipitamment un séminaire l'après-midi même sur le sujet ; le fait qu'il puisse réaliser si rapidement un tel symposium constitue « a measure of how wonderfully elegant this algorithm is », précisa-t-il : « This algorithm is beautiful ».
Neeraj Kayal et Nitin Saxena, Towards a deterministic polynomial-time test.
http://www.cse.iitk.ac.in/research/btp2002/primality.html, avril 2002.
Manindra Agrawal, Neeraj Kayal et Nitin Saxena, Primes is in P.
http://www.cse.iitk.ac.in/users/manindra/primality_original.pdf, 6 août 2002.
http://www.cse.iitk.ac.in/users/manindra/primality.pdf, 4 mars 2003.
↑ Retour au haut de cette page
