Du symbole de Legendre au test de primalité de Solovay-Strassen
L'équation $y^2=x$, $x$ fixé, n'est pas toujours résoluble dans $\mathbb Z/n\mathbb Z$. Un peu comme on utilise le discriminant pour les équations du second degré sur $\mathbb R$, on cherche un outil qui permette de déterminer si cette équation a des solutions ou non!
Pour calculer, le symbole de Legendre, on dispose des 4 propriétés suivantes, valables pour $p$ et $q$ deux premiers impairs distincts :
- $\left(\frac{xy}p\right)=\left(\frac xp\right)\left(\frac yp\right).$
- $\left(\frac{-1}p\right)=(-1)^{\frac{p-1}2}.$
- $\left(\frac{2}p\right)=(-1)^{\frac{p^2-1}8}.$
- $\left(\frac pq\right)\left(\frac qp\right)=(-1)^{\frac{(p-1)(q-1)}{4}}$.
La dernière propriété s'appelle la loi de réciprocité quadratique. Elle fut longtemps un problème ouvert avant que Gauss ne la démontre, et en donne d'ailleurs plusieurs preuves différentes.
Exemple : $x^2=219$ admet-elle une solution modulo $383$? On calcule le symbole de Legendre grâce aux propriétés précédentes : \begin{eqnarray*} \left(\frac{219}{383}\right)&=&\left(\frac{3}{383}\right)\left(\frac{73}{383}\right)\\ &=&-\left(\frac{3}{383}\right)\left(\frac{383}{73}\right)\\ &=&-\left(\frac{-1}{3}\right)\left(\frac{18}{73}\right)\\ &=&\left(\frac{2}{73}\right)=1. \end{eqnarray*} Donc la réponse est : oui!
Le symbole de Jacobi est une extension du symbole de Legendre. On donne désormais un sens à $\left(\frac{x}{n}\right)$ même lorsque $n$ n'est pas premier. Pour cela, on pose, pour $n=p_1^{\alpha_1}\cdots p_r^{\alpha_r}$, $$\left(\frac{x}{n}\right)= \left\{ \begin{array}{ll} \Big(\frac{x}{p_1^{\alpha_1}}\Big)\cdots \Big(\frac{x}{p_r^{\alpha_r}}\Big)&\textrm{ si }x\wedge n=1\\ 0&\textrm{sinon.} \end{array} \right. $$ Le symbole de Jacobi ne permet plus de tester si $x$ est un résidu quadratique modulo $n$. En revanche, on peut toujours le calculer en utilisant la loi de réciprocité quadratique, valable pour tous les entiers impairs premiers entre eux. L'intérêt du symbole de Jacobi consiste essentiellement en le...
On choisit un entier premier avec $n$. On calcule $a^{(n-1)/2}\ [n]$, puis le symbole de Jacobi $\left(\frac an\right)$. L'entier $n$ satisfait au test si $$a^{(n-1)/2}\equiv \left(\frac an\right)\ [n].$$
D'après un théorème d'Euler, si $n$ est premier, il satisfait au test de Solovay-Strassen pour tout entier $a$. S'il n'est pas premier, on prouve qu'il existe au moins un entier premier avec $n$ sur deux pour lequel $n$ ne satisfait pas le test. Si on effectue $k$ tests successifs, avec des entiers $a$ différents chaque fois choisis au hasard, la probabilité pour que $n$ soit premier s'il satisfait à chacun des tests est de l'ordre de $1-1/2^k$. On utilise ce type de test pour fabriquer les grands nombres premiers nécessaires dans les algorithmes de cryptographie comme le RSA.