Test de primalité

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher
Ce modèle est-il pertinent ? Cliquez pour en voir d'autres.
Cet article ne cite pas suffisamment ses sources (mars 2013).

Si vous disposez d'ouvrages ou d'articles de référence ou si vous connaissez des sites web de qualité traitant du thème abordé ici, merci de compléter l'article en donnant les références utiles à sa vérifiabilité et en les liant à la section « Notes et références » (modifier l'article, comment ajouter mes sources ?).

Un test de primalité est un algorithme permettant de savoir si un nombre entier est premier.

Méthode naïve[modifier | modifier le code]

Le test le plus simple est le suivant : 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 à 39 000, il suffit de tester les nombres premiers inférieurs à 198 (car 1982 > 39 000), soit 45 nombres premiers.

Tests probabilistes[modifier | modifier le code]

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 nombres premiers industriels[réf. nécessaire]. L’idée de base du test de la primalité d’un nombre N est la suivante :

  1. Tirer aléatoirement un nombre a.
  2. Vérifier une certaine identité qui fait intervenir a ainsi que le nombre donné N et qui 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.
  3. 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.

Étant donné un test, il peut exister certains nombres composés qui sont déclarés « probablement premier » quel que soit le témoin. De tels nombres résistant au test sont appelés nombres pseudopremiers pour ce test.

Le test de primalité probabiliste le plus simple est le test de primalité de Fermat. Le test de primalité de Miller-Rabin et le test de primalité de Solovay-Strassen sont des variantes plus sophistiquées qui détectent tous les composés. L’un ou l’autre de ces tests est utilisé quand un nombre premier est requis à l’issue d’un calcul aussi court que possible en acceptant une marge de doute infime, par exemple dans le chiffrement RSA ou dans protocole d’échange de clés de Diffie-Hellman.

Tests déterministes rapides[modifier | modifier le code]

Le test cyclotomique est un test de primalité déterministe ; on démontre que son temps d’exécution est O(nclog(log(n))), où n est le nombre de chiffres de N et c est une constante indépendante de n. Sa complexité est moindre que polynomiale.

On peut démontrer que le test de primalité de courbe elliptique est d’exécution O(n6), mais seulement en utilisant certaines conjectures de théorie analytique des nombres non encore démontrées mais largement acceptées comme vraies. Dans la pratique, ce test est plus lent que le test cyclotomique pour les nombres comportant plus de 10 000 chiffres.

L’implémentation de ces deux méthodes est plutôt difficile, et le risque d’erreur dues à la mise en œuvre est par conséquent plus élevée que celles des méthodes probabilistes mentionnées ci-dessus.

Si l’hypothèse de Riemann généralisée est vraie, le test de Miller-Rabin peut être converti en une version déterministe avec un temps d’exécution Õ(n4). Dans la pratique, cet algorithme est plus lent que les deux précédents.

En 2002, Manindra Agrawal, Neeraj Kayal et Nitin Saxena ont décrit un test de primalité déterministe qui s’exécute en Õ(n12). De plus, selon une conjecture (non démontrée, donc, mais largement reconnue comme vraie), il s’exécuterait en Õ(n6). C’est donc le premier test de primalité déterministe de temps d’exécution polynomial. Dans la pratique, cet algorithme est plus lent que les autres méthodes.

Méthodes basées sur la théorie des nombres[modifier | modifier le code]

La théorie des nombres fournit des méthodes ; un bon exemple est le test de Lucas-Lehmer pour tester si un nombre est premier. Ce test est relié au fait que l’ordre multiplicatif d’un certain nombre a modulo n est n-1 pour un nombre premier n quand a est une racine primitive. Si nous pouvons montrer que a est une racine primitive pour n, nous pouvons montrer que n est premier.

Théorie de la complexité[modifier | modifier le code]

En théorie de la complexité, le problème PRIMES est le langage formel qui contient les nombres premiers. PRIMES est dans co-NP ː en effet, son complémentaire COMPOSITES est dans NP car on peut décider COMPOSITES en temps polynômial sur une machine non déterministe en devinant un facteur.

In 1975, Vaughan Pratt a montré qu'il existait un certificat pour PRIMES vérifiable en temps polynômial. Ainsi, PRIMES est aussi dans NP et donc dans NP ∩ coNP.

Les algorithmes de Solovay–Strassen et de Miller–Rabin montre que PRIMES est dans coRP. En 1992, l'algorithme de Adleman–Huang[1] montre que PRIMES est dans ZPP = RP ∩ coRP.

Le test de primalité de Adleman–Pomerance–Rumely de 1983 montre que PRIMES est dans QP, classe qui n'a pas été montré (jusqu'en 2015), comme comparable à une des classes mentionnées ci-dessus.


L'existence du test de primalité AKS montre finalement que PRIMES est dans P. Mais il n'a pas été montré (jusqu'en 2015) que PRIMES est P-complet. On ne sait pas si PRIMES est NC ou L par exemple. Mais on sait que PRIMES n'est pas dans AC0.[2]

Notes et références[modifier | modifier le code]

  1. Adleman, Leonard M.; Huang, Ming-Deh (1992). Primality testing and Abelian varieties over finite field. Lecture notes in mathematics 1512. Springer-Verlag. ISBN 3-540-55308-8.
  2. E. Allender, M. Saks, and I.E. Shparlinski, A lower bound for primality, J. Comp. Syst. Sci. 62 (2001), pp. 356–366.

Voir aussi[modifier | modifier le code]

Articles connexes[modifier | modifier le code]

Liens externes[modifier | modifier le code]