next up previous contents
Next: Le symbole de Jacobi Up: Épisode second : un peu Previous: Épisode second : un peu

Le symbole de Legendre

On définit $\left(\frac{a}{p}\right)$ pour p premier comme égal à 1 si a est un carré dans ${\mathbb Z}/p{\mathbb Z}$, à -1 sinon. Ce symbole est multiplicatif :

\begin{displaymath}
\left(\frac{ab}{p}\right)=\left(\frac{a}{p}\right) \left(\frac{b}{p}\right).\end{displaymath}

Ceci est dû au fait que le produit de deux carrés est un carré, (ceci est toujours vrai dans un groupe cyclique ${\mathbb Z}/n{\mathbb Z}$) et que, si nous sommes dans ${\mathbb Z}/p{\mathbb Z}$, p premier, alors le produit d'un carré par un non carré est un non carré et le produit de deux non carrés est un carré.

On peut aussi énoncer le fait suivant :
g est un générateur du groupe cyclique ${\mathbb G}\Longrightarrow g$ est un non carré. La réciproque est vraie si $ \char93  {\mathbb G}-1=2^k$.

La loi de réciprocité pour le symbole de Legendre affirme

\begin{displaymath}
\left(\frac{p}{q}\right)=(-1)^\frac{(p-1)(q-1)}{4} \left(\frac{q}{p}\right).\end{displaymath}

Ainsi, de même que dans l'algorithme d'Euclide pour le calcul du PGCD ou que dans le test de primalité par descente-remontée (voir §), on est ramené, de proche en proche, à traiter des nombres de plus en plus petits.

L'intérêt d'une stratégie de ``rapetissement progressif du problème'' transparaît dans l'algorithme de calcul du pgcd de (a,b)= :(r,s), dont voici l'algorithme :


DEBUT
tant que $s \not = 0$ faire $(r,s)~:=(s, r \ {\bmod} \ s)$ ;
(* on crunche et squeeze avec allégresse *)
retourner r ;
FIN


next up previous contents
Next: Le symbole de Jacobi Up: Épisode second : un peu Previous: Épisode second : un peu
Cyril Banderier
7/23/1997