Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur GraphSearch.
Concept
Test de primalité AKS
Résumé
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.
Source officielle
À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.