Dossier mathématiques : Tests de primalité : l'algorithme AKS

Dossier mathématiques : Tests de primalité : l'algorithme AKSDossier mathématiques : Tests de primalité : l'algorithme AKSDossier mathématiques : Tests de primalité : l'algorithme AKSDossier mathématiques : Tests de primalité : l'algorithme AKS Résumons la situation avant août 2002, au niveau des test de primalité : on sait parfaitement fabriquer de très grands nombres premiers, mais ces nombres sont trop particuliers pour pouvoir être utilisés dans des applications sensibles. Pour tester si un nombre choisi au hasard est premier, on dispose :

d'un test en temps polynômial, mais au résultat probabiliste.
d'un test en temps polynômial, mais valable sous réserve de la validité d'une conjecture difficile.
d'un test très efficace en pratique, mais dont on sait dire peu de choses en théorie.

Il restait donc à trouver un vrai test en temps polynômial, sans réponse probabiliste, ni conjecture non prouvée.

L'algorithme

L'idée de départ est une modification du petit théorème de Fermat :

Théorème : Soit n un entier, et a premier avec n. Alors n est premier si et seulement si :

Preuve : Pour 0<i<n, le coefficient devant Xⁱ de (X-a)ⁿ-Xⁿ-a est :

Maintenant, si n est premier, et si 0<i<n,

Réciproquement, si n est composé, soit q un facteur premier de n, et q^k la plus grande puissance qui divise n. Alors, q^k ne divise pas

, et est premier avec a^n-q. Le coefficient de X^q n'est donc pas nul modulo n.

Bien sûr, il est hors de question d'appliquer directement le test précédent, car pour calculer (X-a)ⁿ, il faut obtenir n coefficients, et donc au moins réaliser n calculs, ce qui est beaucoup plus que les (log n)^k demandés. On va donc simplifier la condition. Si n est premier, et r est plus petit que n, le théorème précédent prouve aussi l'égalité :

Cette fois, le degré de (X-a)ⁿ mod (X^r-1,n) est plus petit que r, et il ne faut plus qu'environ r(log n)² calculs pour comparer les 2 polynômes. Il reste que l'égalité précédente n'est plus un vrai test de primalité. Si n est composé, il existe des valeurs de a et des valeurs de r pour lesquelles l'égalité est vérifiée.

Agrawal, Kayal et Saxena ont prouvé que, si n est composé, il existe un r, avec r plus petit que C(log n)⁶, et un a, avec a plus petit que

tel que :

L'algorithme suivant teste donc la primalité de n :

Si n=a^b, alors retourner Composé. Pour r=2 jusque C(log n)⁶ faire Pour a=1 jusque faire : Si alors Retourner Composé. Fin Pour. Fin Pour. Retourner Premier

Cet algorithme est polynômial en log n, puisqu'on effectue de l'ordre de (log n)^k fois chaque boucle, et que le calcul à l'intérieur de la boucle est lui-même polynômial en log n. Signalons qu'il s'agit ici d'une version simplifiée et naïve de l'algorithme, et qu'on peut l'améliorer en choisissant au préalable r (AKS donnent des conditions pour cela).

Version imprimable