Test de primalité de Solovay-Strassen

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].

Si l'hypothèse de Riemann généralisée, non démontrée en 2020, 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].