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.On utilisera la notation Ω(t(n)) pour O(t(n) × P(log(t(n))) où P est une fonction polynomiale. Par exemple, Ω(log(n)k) = O(log(n)k × P(log(log(n))) = O(log(n)k+ε) pour tout ε > 0, qui est donc aussi un temps polynomial.
On considérera dans les calculs de complexité temporelle que l'addition, la multiplication et la division de deux nombres de m bits peuvent être réalisées en un temps Ω(m).
La première étape de l'algorithme requiert un temps asymptotique en Ω(log(n)3).
Durant la deuxième étape, on cherche un naturel r tel que ωr(n) > 4log(n)2. On peut y parvenir en essayant successivement les valeurs de r et en regardant si nk n'est pas congru à 1 modulo r pour tout k < 4log(n)2. Pour un r fixé, cela demande O(log(n)2) multiplications modulo r, d'où un temps en Ω(log(n)2log(r)). Or, seuls O(log(n)5) différents r ont besoin au maximum d'être testés, ce qui donne une complexité en Ω(log(n)7).
La troisième étape consiste en le calcul du plus grand commun diviseur de r nombres. Chacun de ces calculs, réalisés à l'aide de l'algorithme d'Euclide, requiert un temps en O(log(n)), donc la complexité est O(rlog(n)) = O(log(n)6). Gabriel Lamé montra en effet ce résultat en 1845 par le truchement de la suite de Fibonacci. Édouard Lucas prouva ensuite que cela constitue le résultat optimal.
La quatrième étape s'exécute en seulement O(log(n)) puisque c'est une comparaison dont la complexité ne dépend que de la longueur de n.
Lors de la cinquième étape, chaque congruence requiert O(log(n)) multiplications de polynômes de degré r dont les coefficients sont de taille O(log(n)), donc peut être vérifiée en Ω(rlog(n)2). Aussi la complexité de cette étape est-elle en Ω(log(n)10.5).
Ce temps domine tous les autres : c'est donc la complexité cherchée de l'algorithme.
Il n'en faut pas moins noter que la complexité temporelle de l'algorithme peut être améliorée en trouvant un majorant plus fin de r. Bien entendu, le meilleur scénario serait pour r de l'ordre de O(log(n)2) puisque la complexité de l'algorithme serait alors en Ω(log(n)6).
En fait, deux conjectures laissent penser qu'un tel naturel r existe, ce qui est d'ailleurs vérifié heuristiquement dans la pratique.
Si elle est vraie, l'algorithme a une complexité en O(log(n)6).
Notons que cette conjecture fut néanmoins démontrée par Hooley en 1967 à l'aide de l'hypothèse de Riemann généralisée (1859) relative aux fonctions ζ. Non prouvée aujourd'hui, cette hypothèse est considérée comme l'un des problèmes majeurs actuels ; elle est étroitement liée à la distribution des nombres premiers prouvée par Hadamard et de La Vallée-Poussin en 1896, et fit l'objet du huitième problème de Hilbert énoncé en 1900. Sa résolution a d'ailleurs été mise à prix en mai 2000 par le Clay Mathematics Institute pour un million de dollars.
Quelques avancées ont néanmoins été faites, notamment par André Weil. Gram prouva en 1903 que les quinze premiers zéros sont bien d'abscisse 0.5 puis Hardy prouva l'existence d'une infinité de tels zéros en 1914. Ceux-ci sont denses sur l'axe critique. Des zones d'exclusion des zéros non triviaux ont par la suite été trouvées et l'on a pu calculer numériquement des millions de zéros, sans jamais trouver de contre-exemples. C'est pourquoi la communauté mathématique tend à considérer la conjecture de Riemann comme vraie.
Si elle est vraie, on en déduit que r est de l'ordre de Ω(log(n)2). Avec un tel r, l'algorithme possède alors une complexité en Ω(log(n)6).
Notons que des progrès ont aussi été réalisés dans l'établissement de cette conjecture.
Une étude empirique permet d'ailleurs de trouver que l'algorithme possède une complexité de l'ordre de 1000log(n)6, ce qui est en accord parfait avec les deux conjectures précédentes.
On peut alors même améliorer la complexité de l'algorithme jusqu'à Ω(log(n)3) à l'aide d'une autre conjecture vérifiée pour r < 100 et n < 1010 par Kayal et Saxena. Si elle est vraie, l'algorithme pourrait alors être modifié de sorte à d'abord chercher un entier r qui ne divise pas n2-1 ; un tel r peut alors être trouvé de telle sorte qu'il soit inférieur à 4log(n), en utilisant le lemme que le produit de tous les nombres premiers inférieurs à n est asymptotiquement supérieur à en. Ensuite, la congruence de la cinquième étape est à vérifier pour l'entier r ainsi déterminé, ce qui requiert un temps en Ω(rlog(n)2).
Avec ce test différent pour la cinquième étape, l'algorithme aurait alors une complexité en Ω(log(n)3), ce qui le rendrait très compétitif et utilisable en pratique.
↑ Retour au haut de cette page