Tous les test de primalité, ou presque, ont la même origine, le petit théorème de Fermat : Il est alors facile d'en déduire un test de non-primalité : si un nombre n est donné, on choisit un nombre a premier avec n, et on calcule a^n-1 : si on ne trouve pas 1 modulo n, c'est que n n'est pas premier. Ce test est très rapide, car on calcule a^n-1 en effectuant au plus 2log n opérations. On procède en effet par élévations au carré successives : si par exemple on veut calculer 3¹², on remarque que 12=2³+2², d'où 3¹²=((3²)²)²(3²)².

  Malheureusement, le petit théorème de Fermat n'est pas une condition nécessaire et suffisante, et il existe des entiers n non premiers pour lesquel a^n-1=1 mod n. De tels entiers sont dits pseudopremiers de base a. Par exemple,

• 341=11×31 est pseudo-premier en base 2.
• 91=7×13 est pseudo-premier en base 3.

Qu'à cela ne tienne, se dit-on. Si 341 est pseudo-premier en base 2, il ne l'est pas en base 3, et le test avec 3 dira que n est composé. Malheureusement, cela n'est pas encore suffisant, car il existe des entiers non premiers, mais pseudo-premiers pour toute base a. Ces nombres sont appelés nombres fortement pseudo-premiers, ou nombres de Carmichael.

  Un nombre de Carmichael résiste donc aux tests précédents. Les premiers nombres de Carmichael sont : 561, 1105, 1729, 2465, et on sait depuis 1994 qu'il en existe une infinité. Il faut donc raffiner le test de Fermat pour pouvoir juger de la primalité. Et pour cela, il est nécessaire d'avoir des raffinements mathématiques...   Par rapport au test de Fermat, nous n'allons plus regarder a^n-1, mais a^(n-1)/2 : Remarquons que, puisque , Le symbole de Legendre n'est défini que pour les nombres premiers. On va avoir besoin d'étendre sa définition aux autres entiers : Le test de primalité que nous allons présenter repose sur la comparaison, modulo n, du symbole de Jacobi et du nombre . Il va donc falloir pouvoir calculer efficacement le symbole de Jacobi (rappelons que si on cherche à tester la primalité de n, on ne dispose pas de sa décomposition en facteurs premiers, et on ne peut pas appliquer la définition). Pour cela, on dispose des 5 propriétés suivantes :

• 
• 
• 
• 
• , où m et n sont premiers entre eux 2 à 2.

La dernière propriété s'appelle loi de réciprocité quadratique, et permet de calculer le symbole de Jacobi par réductions successives, comme lorsqu'on cherche le pgcd par l'algorithme d'Euclide. Par exemple : On peut prouver que pour calculer le symbole de Jacobi , il faut de l'ordre de log n opérations.   Par définition du symbole de Legendre/Jacobi, on a vu que si n est premier, et a est premier avec n, Tous les nombres qui vérifient l'équation précédente ne sont malheureusement pas premiers. Un nombre composé qui la vérifie sera dit nombre pseudo-premier d'Euler en base a.

  Quel intérêt alors, par rapport au test de Fermat? Et bien, l'équivalent des nombres de Carmichael n'existe pas : si n est composé, il existe un a premier avec n pour lequel n n'est pas pseudo-premier d'Euler en base a. D'où le test de primalité suivant :

Pour a allant de 1 à n-1
  Calculer .
  Calculer a^(n-1)/2.
  Si ces deux nombres sont différents, afficher "n est composé".
Fin Pour.

Si le programme n'affiche pas "n est composé", c'est que le nombre testé est premier. Quelle est la rapidité de ce programme? A priori, il faut n exécutions de la boucle pour être sûr que n est premier, et chaque calcul de la boucle prend environ log n opérations. Il faut donc en tout de l'ordre de n log n opérations : c'est beaucoup plus que les C(log n)^k opérations voulues!

  Il y a plusieurs façons de contourner cet écueil. La première donne le test de primalité de Solovay et Strassen. Une analyse plus poussée des propriétés du symbole de Jacobi montre que : si n est composé, et a est premier avec n, il y a au moins une chance sur 2 que Si, pour r valeurs différentes de a, on a , alors il y a en particulier moins d'une chance sur 2^r pour que n soit premier.

  L'algorithme de Solovay et Strassen consiste alors à choisir aléatoirement, r fois de suite, un nombre a premier avec n, et de comparer et . Dès que l'on trouve un résultat différent, on est sûr que n est composé. Si à chaque fois, on trouve un résultat identique, alors on peut affirmer que n est premier avec une probabilité supérieure à 1-1/2^r. Et effectivement, dans de nombreuses applications, on utilise le test de Solovay-Strassen, avec r=100 par exemple. On sait que n est probablement premier, avec une probabilité si grande que cela convient. Bien sûr, à r fixé, l'algorithme de Solovay-Strassen prend de l'ordre de r(log n)^k opérations, ce qui est bien la borne désirée.

  L'autre façon de contourner l'écueil est due à Miller, puis à Bach. Ils ont "prouvé" que, si n est composé, il existe a plus petit que 2 log n tel que n n'est pas pseudo-premier d'Euler en base a. Dans l'algorithme présenté ci-dessus, il suffit de remplacer la boucle Pour a allant de 1 à n-1 par la boucle Pour a allant de 1 à 2log n. L'algorithme nécessite alors C(log n)^k opérations, ce qui est bien la borne désirée!

  Mais... le mot "prouvé" dans le paragraphe précédent est usurpateur. Ils ont prouvé ce résultat, mais en admettant une autre conjecture mathématique, l'hypothèse de Riemann. Il n'est pas le sujet de détailler ici ce qu'est exactement l'hypothèse de Riemann. Disons simplement qu'elle a été formulée vers 1860 par Bernhard Riemann et qu'elle est considérée comme la plus grande énigme mathématique. Citée dans la liste des 23 problèmes de David Hilbert en 1900, reprise dans la liste des 7 problèmes du millénaire, elle reste non résolue à ce jour. Le test de Miller ne peut donc pas être considéré comme un vrai test polynômial.   Il existe encore bien d'autres algorithmes "sur le marché". L'un des plus utilisés est ECPP (Elliptic Curve Primality Proving), qui est fondée sur les intrigantes courbes elliptiques. Il faudrait consacrer tout un dossier pour comprendre précisément comment fonctionne cet algorithme!

  Pour le comparer aux autres, disons simplement qu'on sait assez peu de choses sur sa complexité. On a de bonnes raisons de penser qu'il lui faut de l'ordre de (log n)^r opérations pour tester si un entier est premier, mais on ne sait pas le prouver. En revanche, on a constaté qu'en pratique, cet algorithme était très efficace! En outre, si l'entier est premier, il donne aussi un certificat de primalité, c'est-à-dire une méthode très rapide et très simple pour prouver que l'entier est premier.

Version imprimable