Idée et description de l'algorithme AKS

Document PDF à téléchargerUne 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 PDF pour en faciliter la consultation et l'impression.
Une version allégée de cet exposé est aussi parue dans le soixantième numéro du magazine de mathématiques pures et épicées Quadrature (avril–juin 2006, édité par EDP Sciences).
 

Identité remarquable

Le test de primarité AKS est fondé sur l'identité suivante, valable pour les nombres premiers, et qui est une généralisation du petit théorème de Fermat.

Soient un entier relatif a et un entier naturel n > 2 premiers entre eux. Alors n est premier si, et seulement si, (X + a)n ≡ Xn + a [n].

Cette identité fournit donc un critère très simple de primarité : étant donné un nombre n, il suffit de choisir un entier a premier avec n puis de vérifier si la congruence est satisfaite. Cependant, cela prend un temps en O(n) puisqu'il s'agit d'évaluer n coefficients dans le pire des cas. D'ailleurs, si les créateurs de l'algorithme AKS en étaient restés là, celui-ci n'aurait été qu'un post-scriptum dans l'histoire des tests de primarité.

Un moyen simple de réduire le nombre de coefficients est d'évaluer les deux membres de la congruence modulo un polynôme de la forme Xr - 1 pour un entier r plus petit que n bien choisi.

Mieux, si un tel r est choisi d'un ordre logarithmique en n, le polynôme résiduel peut être directement calculé en temps polynomial avec un algorithme approprié.

D'après la proposition précédente, il est immédiat de constater que tous les nombres n premiers satisfont cette équation pour tout a et pour tout r. Le problème est qu'il existe aussi des nombres composés qui vérifient l'équation pour quelques valeurs de a et de r. Par exemple, le troisième nombre de Carmichael , n = 1729 = 7 × 13 × 19, vérifie la congruence avec a = 5 et r = 3. De tels nombres, dont les deux premiers sont 561 et 1105, sont des entiers n non premiers tels que, pour tout a premier avec n, an-1 ≡ 1 [n]. En 1994, a été prouvée la conjecture qu'il existe une infinité de nombres de Carmichael.

> Powmod(X + 5, 1729, X^3 - 1, X) mod 1729;

X + 5

> Powmod(X, 1729, X^3 - 1, X) + 5 mod 1729;

X + 5

Or, comme Carl Pomerance le fit plus tard remarquer à juste titre – « it seems a shame to give up on it just because there are a few counter examples » –, il fallait quand même persister dans cette direction ; si bien qu'il est possible d'utiliser cette caractérisation en montrant que l'on peut trouver un nombre r tel que si l'équation est vérifiée pour plusieurs nombres a déterminés, alors n est premier.

Cette découverte fut réalisée le 10 juillet 2002 : en fixant un r judicieux et en faisant varier a, naît une caractérisation des nombres premiers.

Toujours avec le même exemple, la congruence n'est effectivement plus vérifiée avec r = 5.

> Powmod(X + 5, 1729, X^5 - 1, X) mod 1729;

1254 X^4 + 799 X^3 + 556 X^2 + 1064 X + 1520}

> Powmod(X, 1729, X^5 - 1, X) + 5 mod 1729;

X^4 + 5

La recherche de r et le nombre de vérifications à accomplir ensuite avec les a déterminés s'effectuent en un temps polynomial en log(n), si bien que l'on obtient effectivement un algorithme déterministe en temps polynomial pour des tests de primarité.

L'algorithme AKS

Nous sommes maintenant en mesure d'énoncer l'algorithme AKS en pseudo-code.

L'algorithme AKS

 

↑ Retour au haut de cette page

Pages connexes

← Retour au menu précédent