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 de preuve de primalité déterministe et généraliste (fonctionne pour tous les nombres) publié le par trois scientifiques indiens nommés Manindra Agrawal, Neeraj Kayal et Nitin Saxena (A.K.S). Ce test est le premier en mesure de déterminer la primalité d'un nombre dans un temps polynomial. Ce test a été publié dans un article scientifique intitulé « PRIMES is in P ». Cet article leur a valu le prestigieux prix Gödel 2006. L'algorithme détermine si un nombre est premier ou composé (au sens de la factorisation). L'algorithme repose sur la généralisation suivante du petit théorème de Fermat : pour tout entier n ≥ 2 et tout entier a premier avec n, n est un nombre premier si et seulement si qui résulte d'une propriété des coefficients binomiaux : n est un nombre premier si et seulement si L'objet d'AKS est d'exploiter efficacement cette propriété. L'algorithme est globalement le suivant: procédure AKS(): Si avec et alors renvoyer non-premier (étape 1) Construire le plus petit entier tel que l'ordre de modulo soit supérieur à (étape 2) Si pgcd() != 1 et pgcd()!= n pour un certain alors renvoyer non-premier (étape 3) Si alors renvoyer premier (étape 4) Pour compris entre 1 et faire: Si alors renvoyer non-premier (étape 5) Renvoyer premier (étape 6) On cherche à démontrer que l'algorithme renvoie premier si, et seulement si son argument est un nombre premier. La preuve repose sur des résultats sur les corps finis et de diverses inégalités dont la plupart sont démontrées par récurrence. On note tout au long de la démonstration l'ordre (théorie des groupes) de dans le groupe des inversibles de l'anneau et l'Indicatrice d'Euler. On suppose tout d'abord que est premier, l'algorithme peut renvoyer une valeur (premier ou non-premier) à cinq différentes étapes: Il est clair que l'algorithme ne peut pas renvoyer non-premier aux étapes 1 et 3. D'après le Théorème de Lagrange sur les groupes, l'ordre de tout élément divise l'ordre du groupe.