Test de primalité

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

Une composition du plus grand nombre de nombres premiers découvert à ce jour pour un article sur la primalité

Méthode naïve

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 à 39 000, il suffit de tester les nombres premiers inférieurs à 198 (car 1982 > 39 000), soit 45 nombres premiers.

Élargissement de la méthode naïve à une méthode ludique

Cette méthode se base sur l’écriture d’un entier, répondant à certains critères, en fonction de son reste de division euclidienne par 90. L’approche consiste en la détermination de sa primalité par des opérations arithmétiques simples, qui excluent l’utilisation d’outils non manuels tels que la calculatrice. Toutefois, elle ne considère pas le temps de résolution comme facteur essentiel.[1]

Les nombres en question ne doivent être ni pairs (divisibles par 2[2]), ni multiples de 3 (la somme des éléments d’un entier multiple de 3 est un multiple de 3) et ni multiples de 5 (pour un entier impair, le chiffre unité vaut 5 dans le système décimal).

Il en résulte un ensemble infini d’entiers impairs, excluants ceux sus-cités et dont les premières valeurs sont : 1,7,11,13,17,19,23,29,31,37… L’auteur nomme librement ces nombres impairs : nombres de 'classes[3]' I et II.

En résumé, les nombres impairs de ‘classe’ I sont ceux dont les restes de division euclidienne par 9 sont les entiers : 1, 4 et 7. Par opposition, les nombres impairs de ‘classe’ II ont pour restes de division par 9 : 2, 5 et 8 (les restes 0, 3 et 6 sont par construction, exclus)[4]

Cette méthode de résolution de la primalité d’un nombre, remplace les divisions successives sur des nombres impairs inférieurs (méthode naïve), par des opérations de multiplication, entre des nombres impairs adéquatement choisis (diviseurs candidats).


1- Restes de division euclidienne par 90[5]

Avant de procéder à ces opérations de multiplication, on écrit le nombre dont on cherche la primalité en fonction de son reste de division par 90.

Ce reste pour un entier de ‘classe’ I ou II, ne peut être que l’une des 24 valeurs suivantes :

(1,7,11,13,17,19,23,29,31,37,41,43,47,49,53,59,61,67,71,73,77,79,83,89)[6]

De façon générale, connaissant l’unité d’un entier E, dans le système décimal, ainsi que son reste de division euclidienne par 9, il est facile de déduire son reste de division euclidienne par 90.

Exemples

  • Le nombre pair  : (modulo) et son unité dans le système décimal est . Ces deux éléments et , permettent d’écrire : . Une simple division de par , donne :


  • Le nombre impair  : , son unité dans le système décimal est égal à .

(E est de ‘classe’ II), ce qui donne : . Il en résulte :


2- Étude de la primalité

  • Produits modulaires et d’unités.[7],[8]

Tout nombre composé (on suppose ici que ) peut s’écrire sous la forme : (*)[9].

Si est le reste de division euclidienne de par 90, le terme peut toujours s’écrire en fonction de .

Soit un entier relatif, tel que , alors . Le terme étant un multiple de , il est facile d’en extraire son quotient (les diviseurs de sont : ).

Choix des valeurs et [1]

Pour de ‘classe’ I ou II, les seuls restes de divisions possibles par 9, sont : 1, 2, 4, 5, 7 et 8. Quant aux unités possibles, elles se résument aux entiers suivants : 1, 3, 7 et 9.

Tableau de produits modulaires (modulo 9)
1 2 4 5 7 8
1 1 2 4 5 7 8
2 2 4 8 1 5 7
4 4 8 7 2 1 5
5 5 1 2 7 8 4
7 7 5 1 8 4 2
8 8 7 5 4 2 1
Tableau de produits d'unités (système décimal)
1 3 7 9
1 1 3 7 9
3 3 9 1 7
7 7 1 9 3
9 9 7 3 1


Afin de déterminer les diviseurs () on se doit avant tout, comme pour la méthode naïve, de déterminer la partie entière de la racine carrée du nombre . Son calcul, peut se faire par l’utilisation de sommes consécutives de nombres impairs.


Exemple d’application de la méthode ludique pour [11]:


En premier lieu, cet entier répond aux critères de ‘classes’ définies par l’auteur. En effet: (de ‘classe’ I).

L’unité de est égale à , il s’en suit que , ce qui donne .


En deuxième lieu, la partie entière de la racine carrée de vaut (voir la méthode[12] utilisée pour son calcul).

Méthode de calcul (sommes successives de nombres impairs)
Le calcul de la partie entière de la racine carrée d’un entier, peut se faire en écrivant l’entier en fonction d’un carré facilement remarquable.

Par exemple : etc.

Si on prend la première écriture :

L’idée suivante est d’étendre la suite arithmétique, de façon à y inclure une partie ou la totalité (dans le cas où le nombre est un carré parfait) de la quantité 147.

On peut commencer par considérer la somme : 21+23+25+27+29, qui semble se rapprocher de 147.

Le calcul peut se faire de deux façons :

Calculer la somme directement : 21+23+25+27+29=125

Calculer le produit associé : 21+23+25+27+29=5×25=125[13],[14]

Donc :

Ce qui revient à écrire :

Ceci implique que si n’est pas premier, alors son ou ses diviseurs sont des éléments de l’ensemble {,,}.

Les tableaux des produits modulaires et d’unités, mentionnés plus haut, permettent de déduire les valeurs respectives, possibles :


  • Si , alors et l’unité de est égale à  : .

Les valeurs théoriquement possibles de sont alors : , , etc. Cependant, l’ordre de grandeur du produit suivant 7×60, par exemple, montre que dépasserait largement  : la déduction en est que n’est pas un diviseur de .


  • Si , alors et l’unité de est égale à  :

, ce qui suggère des valeurs , etc. Une vérification rapide 10×40 (valeur supérieure à ), montre que est bien supérieur à .


  • Il ne reste plus qu’à tester .

et l’unité de est égale à 9 : . On pourrait alors avoir , etc.

On constate facilement que 10×19=190, est assez proche de . Il serait alors pertinent de tester le produit adéquat, à savoir .

Il suffit pour cela, d’utiliser la formule mathématique (*) utilisée dans cette méthode, avec , .

La suite en est simplissime :

On introduit

La factorisation du terme entre parenthèses, permet de faire apparaitre le quotient de la division euclidienne de 13×19 par 90 :

[15],[16]

Tests probabilistes

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 (en). 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 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.
  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

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, Nitin Saxena et Neeraj Kayal ont décrit un test de primalité déterministe (le test de primalité AKS) 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

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é

En théorie de la complexité, le problème PRIMES est le problème de la décision de l'appartenance au langage formel qui contient les nombres premiers, écrits en binaire :

PRIMES = {10, 11, 101, 111, 1011, ...}

où 10, 11, 101, 111, 1011... sont les écritures binaires des nombres premiers 2, 3, 5, 7, 11, etc.

PRIMES est dans co-NP : en effet, son complémentaire COMPOSITES, c'est-à-dire la décision de l'appartenance à l'ensemble des nombres non premiers, est dans NP, car on peut décider COMPOSITES en temps polynomial en le nombre de chiffres du nombre à tester, sur une machine de Turing non déterministe, en devinant un facteur.

En 1975, Vaughan Pratt (en) a montré qu'il existe un certificat pour PRIMES vérifiable en temps polynomial[17]. Ainsi, PRIMES est aussi dans NP et donc dans NP  coNP.

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

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

Le test de primalité AKS[22] est un algorithme en temps polynomial et montre finalement que PRIMES est dans P. Mais il n'a pas été montré que PRIMES est P-complet. On ne sait pas si PRIMES est dans NC ou dans LOGSPACE par exemple. Mais on sait que PRIMES n'est pas dans AC0[23].

Notes et références

  1. Jarz Laïde. Ordre et évolution des nombres impairs composés de ‘classes’ I et II. Première partie. ISBN 978-1-7780923-2-9. (http://nombrescomposesetpremiers.com/data/documents/Ordre-Evolution-Nombres-Impairs-Composes.pdf) (2022). (en) Order and evolution of composite odd numbers of ‘classes’ I and II. First part. ISBN 978-1-7780923-1-2. (http://nombrescomposesetpremiers.com/data/documents/Order-Evolution-Composite-Odd-Numbers.pdf) (2022).
  2. Le nombre 2 est une exception des nombres pairs puisqu'il est premier.
  3. Jean-Pierre Lamoitier. L’Arithmétique une introduction ludique. Tome III : L’arithmétique modulaire et ses applications. Exemples et exercices corrigés. pp. 1-7. ISBN 978 27056 6918 8. (2009) Hermann. Paris.
  4. Avec les entiers relatifs, les classes d’équivalence, pour une congruence modulo n donnée, sont définies dans l’anneau Z/nZ, par contre, les classes introduites par l’auteur, ne tiennent pas compte des valeurs négatives.
  5. Laïde, pp. 8–14.
  6. Il est à noter que les nombres 1, 49 et 77 sont les seuls nombres composés de la liste.
  7. Laïde, pp. 4, 7.
  8. Joseph Claudel. Introduction à la science de l’ingénieur (1865). Dunod. Paris. pp. 8. (https://books.google.fr/books?id=R8deXwtIkOwC&pg=PA8#v=onepage&q&f=false)
  9. Laïde, pp. 17–19, 29-34.
  10. Joseph Claudel. pp. 70-71, points 243-244.
  11. Cette méthode n'accorde pas d'intérêt aux critères de divisibilité des entiers (tel que de constater, par exemple, que 247 ne peut être un multiple de 7), puisqu’elle utilise le quotient de division par 90, comme unique outil servant à trouver les diviseurs d'un nombre composé.
  12. Laïde, pp. 17–24 et annexe A.
  13. 5 représente le nombre d’éléments de la somme et 25 est le nombre situé à son milieu
  14. Laïde, pp. 19–22.
  15. En théorie, n’importe quel entier impair, non multiple de 3 et de 5 et dont on cherche à déterminer la primalité, peut être traité par cette méthode. Le temps de résolution par contre, peut grandement en être affecté.
  16. Voir quelques exemples d’application. Laïde (pp. 39-74).
  17. Vaughan Pratt. "Every prime has a succinct certificate". SIAM Journal on Computing, vol. 4, pp. 214–220. 1975. Citations, Full-text.
  18. Michael O Rabin, « Probabilistic algorithm for testing primality », Journal of Number Theory, vol. 12, no 1, , p. 128–138 (ISSN 0022-314X, DOI 10.1016/0022-314X(80)90084-0, lire en ligne, consulté le ).
  19. Adelman et Huang 1992.
  20. Leonard M. Adleman, Carl Pomerance et Robert S. Rumely, « On Distinguishing Prime Numbers from Composite Numbers », Annals of Mathematics, vol. 117, no 1, , p. 173–206 (ISSN 0003-486X, DOI 10.2307/2006975, lire en ligne, consulté le ).
  21. « QP sur Complexity Zoo ».
  22. (en-US) « PRIMES is in P | Annals of Mathematics » (consulté le ).
  23. Allender, Saks et Shparlinski 2001.

Annexes

Bibliographie

  • [Adelman et Huang 1992] (en) Leonard M. Adelman et Ming-Deh Huang, Primality testing and Abelian varieties over finite field, Berlin, Springer-Verlag, coll. « Lecture notes in mathematics » (no 1512), , 142 p. (ISBN 3-540-55308-8, OCLC 25933224, BNF 37383187).
  • [Allender, Saks et Shparlinski 2001] (en) Eric Allender, Michael Saks et Igor Shparlinski, « A lower bound for primality », Journal of Computer and System Sciences, vol. 62 « Special issue on the fourteenth annual IEE conference on computational complexity », no 2, , p. 356–366 (DOI 10.1006/jcss.2000.1725).
  • [Demazure 1997] Michel Demazure, Cours d'algèbre. Primalité, divisibilité, codes, Cassini, .
    Ce livre contient de nombreux algorithmes écrits en Caml Light.
  • [Demazure 2008] Michel Demazure, Cours d'algèbre. Primalité, divisibilité, codes, Cassini, .
Ce livre contient de nombreux algorithmes écrits en Ruby. La présentation de cette édition est différente de la précédente et s'adresse à un plus large public.

Articles connexes

Liens externes

  • Portail des mathématiques
  • Portail de la cryptologie
  • Portail de l'informatique théorique
Cet article est issu de Wikipedia. Le texte est sous licence Creative Commons - Attribution - Partage dans les Mêmes. Des conditions supplémentaires peuvent s'appliquer aux fichiers multimédias.