Test de primalité

vignette|Le 39e nombre premier de Mersenne découvert à ce jour pour un article sur la primalité Un test de primalité est un algorithme permettant de savoir si un nombre entier est premier. Le test le plus simple est celui des divisions successives : pour tester N, on vérifie s’il est divisible par l’un des entiers compris au sens large entre 2 et N-1. Si la réponse est négative, alors N est premier, sinon il est composé. Plusieurs changements permettent d’améliorer les performances de cet algorithme : il suffit de tester tous les nombres de 2 à seulement, puisque si alors soit soit , on peut encore diviser par deux le travail en ne testant que les nombres impairs, une fois que la divisibilité par deux a échoué, de façon générale, on peut calculer à l’avance une liste des nombres premiers inférieurs à une limite (avec un crible d'Ératosthène), pour ne tester que ceux-ci. Par exemple, pour tester les nombres inférieurs à , il suffit de tester les nombres premiers inférieurs à 198 (car 1982 > ), soit 45 nombres premiers. Les tests probabilistes ne sont pas des tests de primalité au sens strict (ils font partie des méthodes de Monte-Carlo) : ils ne permettent pas de garantir de façon certaine qu’un nombre est premier, mais leur faible coût en temps de calcul en font d’excellents candidats pour les applications en cryptologie qui souvent dépend de façon critique de grands nombres premiers et accepte un taux d’erreur pourvu qu’il soit très faible: on les appelle des . L’idée de base du test de la primalité d’un nombre N est la suivante : Tirer aléatoirement un nombre a. Vérifier une certaine identité qui fait intervenir a ainsi que le nombre donné N et qui est vraie si le nombre N est premier. Si l’identité n’est pas satisfaite, alors N est nécessairement composé et le test s’arrête ; dans ce cas, a est appelé un témoin du test. Répéter l’étape 1 jusqu’à ce que la marge d’incertitude souhaitée soit atteinte. Après plusieurs itérations, si N n’est pas reconnu comme un nombre composé, il est déclaré probablement premier.