Test de primalité de Solovay-Strassen

Le test de primalité de Solovay-Strassen, dû à Robert Solovay et Volker Strassen, est un test de primalité, c'est-à-dire un procédé qui détermine si un nombre impair est composé ou premier. C'est un test probabiliste, ne garantissant la primalité du nombre testé qu'avec une certaine probabilité (qu'on peut rendre aussi proche de 1 que l'on veut).

Le test de Soloway-Strassen repose sur quelques bases de théorie des nombres, rappelées ci-dessous.

Le symbole de Legendre ${\displaystyle \left({\frac {a}{p}}\right)}$ est défini pour p premier par 0 si ${\displaystyle a}$ est multiple de p, 1 si ${\displaystyle a}$ est un carré modulo p et –1 sinon.

Soit n un entier impair supérieur à 2 et n = ${\displaystyle p_{1}^{\alpha _{1}}p_{2}^{\alpha _{2}}\cdots p_{k}^{\alpha _{k}}}$ sa décomposition en facteurs premiers. Alors, pour tout entier ${\displaystyle a}$, le symbole de Jacobi ${\displaystyle \left({\frac {a}{n}}\right)}$ est une généralisation du symbole de Legendre qui vaut : ${\displaystyle \left({\frac {a}{p_{1}}}\right)^{\alpha _{1}}\left({\frac {a}{p_{2}}}\right)^{\alpha _{2}}\cdots \left({\frac {a}{p_{k}}}\right)^{\alpha _{k}}}$, où les ${\displaystyle \left({\frac {a}{p_{i}}}\right)}$ sont des symboles de Legendre.

Pour le symbole de Legendre, c'est-à-dire pour tout nombre premier p impair, le critère d'Euler dit que ${\displaystyle \left({\frac {a}{p}}\right)\equiv a^{p-1 \over 2}\mod p}$. C'est a fortiori vrai si on remplace le symbole de Legendre par le symbole de Jacobi. Or le symbole de Jacobi peut être calculé pour tout entier de manière rapide (à l'aide d'une généralisation simple de la loi de réciprocité quadratique)^[1].

Pour déterminer si un entier impair ${\displaystyle n}$ donné est premier, on peut tester, pour un grand nombre de valeurs aléatoires de ${\displaystyle a}$, si la congruence

${\displaystyle \left({\frac {a}{n}}\right)\equiv a^{n-1 \over 2}\mod n}$

est satisfaite. Si elle est fausse pour un certain entier ${\displaystyle a}$, alors on sait que ${\displaystyle n}$ n’est pas premier^[2].

Cependant, tout comme avec le test de primalité de Fermat, il y a des « menteurs ». Une valeur ${\displaystyle a}$ est appelée menteur d’Euler si l’égalité est satisfaite bien que n soit composé. Un témoin d’Euler est une valeur de ${\displaystyle a}$ pour laquelle l’égalité n'est pas satisfaite, et donc ${\displaystyle a}$ est un témoin du fait que n est composé.

À la différence du test de primalité de Fermat, pour chaque entier composé n, au moins la moitié de tous les ${\displaystyle a}$ de ${\displaystyle (\mathbb {Z} /n\mathbb {Z} )^{\times }}$ sont des témoins d’Euler. Par conséquent, il n’y a aucune valeur de n pour laquelle tous les ${\displaystyle a}$ sont des menteurs, alors que c'est le cas pour les nombres de Carmichael dans le test de Fermat^[2].

L’algorithme peut être écrit comme suit :

Entrées : n : un entier impair dont on veut connaître la primalité ; k : le nombre maximum de fois où le symbole de Jacobi va être calculé.

Sortie : composé si n est composé, sinon probablement premier

répéter k fois :

choisir ${\displaystyle a}$ au hasard entre 2 et n – 1

${\displaystyle x\leftarrow \left({\frac {a}{n}}\right)}$

si x = 0 ou ${\displaystyle x\not \equiv a^{\frac {n-1}{2}}\mod n}$ alors retourne composé

retourne probablement premier

En utilisant des algorithmes rapides d’exponentiation modulaire, la complexité en temps dans le pire cas de cet algorithme est un ${\displaystyle O(k\times \log ^{3}n)}$, où ${\displaystyle k}$ est le nombre maximum de fois où l'on tire aléatoirement un entier ${\displaystyle a}$ pour calculer un symbole de Jacobi avec lui, et n est la valeur dont on veut examiner la primalité. La probabilité pour que l’algorithme échoue, c'est-à-dire la probabilité que n soit composé sachant que l'algorithme dit qu'il est premier, est inférieure à ${\displaystyle 2^{-m}{\frac {1-a}{a}}}$, avec ${\displaystyle a={\frac {2}{\ln n}}}$ (et non pas 2^-m comme on le trouve chez certains auteurs, ce qui est en fait la probabilité que l'algorithme réponde que n est premier alors qu'il ne l'est pas. Il y a deux ordres de grandeurs entre ces deux probabilités pour des valeurs typiques de n !)

Dans les applications en cryptographie, si l'on choisit une valeur suffisamment grande de k, par exemple 100, la probabilité pour que l’algorithme se trompe est si petite que l'on peut considérer le nombre qui a résisté au test comme premier et l'utiliser dans des applications cryptographiques sans inquiétude.

À partir de 1980, le test de Solovay-Strassen a été remplacé en pratique par le test de primalité de Miller-Rabin, plus efficace, car reposant sur un critère analogue, mais ne donnant de faux positif qu'au plus une fois sur quatre lorsque n n'est pas premier^[2].

Si l'hypothèse de Riemann généralisée, non démontrée en 2024, est vraie alors tout nombre composé ${\displaystyle n}$ admet un témoin d'Euler inférieur à ${\displaystyle 2(\log n)^{2}}$. Le test de primalité Solovay-Strassen peut dans ce cas être adapté en un test déterministe de complexité ${\displaystyle {\mathcal {O}}(\log ^{4}n)}$^[2], donc polynomial en le nombre de chiffres de ${\displaystyle n}$^{[note 1]}.

• Chiffrement RSA
• Échange de clés Diffie-Hellman

• Arithmétique et théorie des nombres
• Portail de l'informatique théorique