Les nombres premiers sont partout en mathématiques. De l’arithmétique du collège jusqu’à ses liens importants avec la conjecture de Riemann, on ne cesse d’étudier ces nombres particuliers.
Je vous propose de vous présenter quelques méthodes afin de savoir si un nombre est premier ou pas. On va commencer doucement et aller vers des choses de plus en plus complexe dans l’étude des tests de primalités. Le niveau mathématique requis est, au début, un bon niveau terminal, puis ira jusqu’à un niveau seconde année de prépa.
Pré-requis
- Savoir ce qu’est un nombre premier.
- Arithmétique modulaire.
- Avoir des bases sur \mathbb{Z}/n \mathbb{Z} sera utile pour la fin.
Critères de primalité
On veut pouvoir, à partir d’un entier quelconque, savoir si oui ou non il est premier en un nombre (raisonnable) d’étapes. Soit donc n \in \mathbb{N} un entier dont on veut déterminer la primalité. Un critère de primalité est algorithme qui nous retourne si un entier donné est premier ou non.
La méthode naïve
Soit n \in \mathbb{N} un entier dont on veut déterminer la primalité. Une première méthode, que l’on appellera la méthode naïve, et de vérifier si tout entier p \leq n est un diviseur de n . Il nous faut (en gros) au plus n divisions euclidiennes pour vérifier si un entier est premier ou non avec n . Ce critère est extrêmement chronophage : les entiers dont on veut vérifier la primalité sont de l’ordre de plusieurs milliers de millions de chiffres.
Une première méthode d’amélioration est de remarquer que si n , il en possède un inférieur à \sqrt{n} . Ainsi, notre algorithme se finira en au plus \sqrt{n} divisions euclidiennes. C’est une bonne amélioration déjà, et cela va nous servir de borne de comparaison. Si l’on trouve un algorithme qui nous dit un un nombre est premier ou non en au plus \sqrt{n} divisions euclidiennes, on peut le mettre à la poubelle… Bon, j’exagère, la complexité informatique ce n’est pas aussi simple, mais on va rester sur cette idée durant l’article.
Le critère de Fermat
On rappelle le petit théorème de Fermat, à savoir que si n est un nombre premier, alors pour tout entier a on a a^n = a [n] . Par contraposée, on en déduit que s’il existe un entier a tel que a^n \neq a [n] , alors n n’est pas premier.
On obtient donc un nouveau critère. Il suffit de prendre tout les nombres inférieurs à n et de faire un passage à la puissance n . Et puis on teste ce critère sur le nombre 561, qui n’est pas premier, et on se rend compte que tout entier inférieur à 561 vérifie a^{561} = a [561] et on ne sait plus quoi faire…
Qu’est-ce qui s’est passé ? C’est très simple : rien ne nous dit qu’un nombre vérifiant le petit théorème de Fermat est premier, c’est d’ailleurs faux ! Les nombres non-premiers qui vérifient le théorème de Fermat ont un nom, ce sont les nombres de Carmichaël. On ne sait pas grand chose sur ces entiers. Depuis 1994 on sait qu’il y en a une infinité, qu’ils se raréfient quand on approche de l’infini et… C’est à peu près tout.
Est-ce que donc notre critère est à jeter ? Pas entièrement non, mais il faudra se séparer du fait que notre algorithme renverra “ n est premier” ou “ n n’est pas premier”. Il renverra à la place “ n n’est pas premier” ou “ n est sûrement premier“. Dans cette optique là, rien ne sert donc d’aller jusqu’au bout et d’essayer tout les entiers. On peut en effet juste en essayer certains au hasard entre 1 et n et, s’ils vérifient tous a^n = a [n] , on peut renvoyer que “ n est sûrement premier”. Il faudrait calculer l’erreur que l’on fait à chaque fois, ce que l’on ne fera pas ici. On peut en tout cas, en moins d’étapes que la méthode naïve, arriver à des résultats concluants.
En pratique, il suffit de vérifier la propriété de Fermat sur de petits entiers (disons 2, 3, 5 et 7) afin de vérifier que les entiers ne sont pas premiers. Un entier a qui permet de contredire le fait que n est appelé un témoin de Fermat. On peut montrer que ou bien n n’en possède pas, ou bien il en possède au moins \frac{n}{2} . Le test sert donc à vérifier qu’un nombre n’est pas premier si l’on a un doute plutôt que de vérifier si ce dernier l’est. Cependant, on préférera le critère suivant qui est plus efficace et ne comporte pas de faux positifs.
Le critère de Miller-Rabin
Avant de continuer, on a besoin de quelques petits résultats sur l’anneau \mathbb{Z}/n \mathbb{Z} . Supposons que n \neq 2 soit un nombre premier (on sait que 2 en est un de toute façon…). Alors n-1 est pair. De l’intégrité de l’anneau \mathbb{Z}/n \mathbb{Z} , on en déduit que si a^{n-1} = 1 [n] on a a^{\frac{n-1}{2}} = \pm 1 [p] . Si \frac{n-1}{2} est pair et que a^{\frac{n-1}{2}} = 1 [p] , on peut encore recommencer. Cette petite observation va nous permettre d’énoncer un nouveau critère de primalité.
On va énoncer cela sous forme de propriété : si n > 2 est un nombre premier tel que n-1 = 2^s t avec t impair, alors pour tout entier a premier avec n , ou bien on a a^t = 1 [n] , ou bien il existe 0 \leq i < s tel que a^{2^i t} = -1 [n] . En considérant la contraposé de ce résultat, on obtient que s’il existe 1 < a < n tel que a^t \neq 1 [n] et que pour tout 0 \leq i < s on a a^{2^i t} \neq -1 [n] , alors n n’est pas composé.
Il suffit donc d’appliquer l’algorithme à quelques entiers, que nous appellerons témoins de Miller-Rabin (ou juste témoins), pour savoir si un nombre n’est pas premier ou s’il y a une bonne chance qu’il le soit. On a en général pas besoin de beaucoup de témoins pour savoir qu’un entier est composé. Par exemple, le premier entier composé pour lequel on a besoin d’un autre témoin que 2, 3 et 5 est 25.326.001. Aussi, on voit que si d est un diviseur de n , alors d est un témoin. Il n’y a donc pas de phénomènes similaires à ce qu’on avait avec les nombres de Carmichaël.
Ainsi, il existe toujours des témoins de Miller-Rabin si n est composé. Est-ce qu’il y en a beaucoup ? On peut montrer que si n est composé, au moins les trois quarts des entiers inférieurs à n sont des témoins de Miller-Rabin. Il existe aussi un lien entre l’hypothèse de Riemann généralisée et ce test de primalité : si cette hypothèse est vraie, alors il existe toujours un témoins strictement inférieur à 2 (\log n )^2 .
Il faut savoir que ce test est utilisé en pratique en cryptographie pour produire de grands nombres premiers. Avec par exemple 25 itérations du test sur des entiers pris aux hasards, on peut déterminer avec une précision d’environs 10^{-15} si un entier est premier ou non. Et le test est efficace : il suffit de calculer n = 2^t s et pour nos entiers a pris aux hasards de calculer a^t [n] et a^{2^i t} [p] . Un tel test est appelé un test de primalité probabiliste.
En conclusion
On parlait en début d’article du fait qu’un test de primalité devait nous dire à la fin si un nombre est premier ou non de manière exacte. Or, tout ce qu’on a présenté ne pouvait nous le dire qu’avec une certaine probabilité. Est-ce qu’on aurait pu faire mieux ?
La fin de la partie du test de Miller-Rabin nous donne un algorithme complètement déterministe si l’on admet l’hypothèse de Riemann généralisée : il suffit d’appliquer l’algorithme sur tout les entiers inférieurs à 2 (\log n)^2 , ce qui fait bien moins d’entiers à tester que pour la méthode naïve. En pratique cependant, on préfère travailler avec des algorithmes probabilistes : ils demandent bien moins de ressources qu’un algorithme déterministe.
Les algorithmes présentés ont tous un point commun : ils peuvent nous dire si un entier est premier ou non. Cependant, ils ne permettent pas de déterminer, si l’entier n’est pas premier, un diviseur de ce dernier (sauf la méthode naïve). Le problème de trouver de manière efficace la factorisation d’un entier est un grand problème des mathématiques appliquées et toute la cryptographie moderne se base dessus. Et on arrive alors sur des techniques très complexes d’algèbre à base de crible de corps de nombres, de courbes elliptiques… Bref, ce sera pour une autre fois !
Et pour découvrir plusieurs nombres premiers d’un coup, on a utilisé par le passé le crible d’Eratosthène !
