Problème de la résiduosité quadratique

Soit ${\displaystyle N}$ un nombre composé de la forme particulière ${\displaystyle N=pq}$, où ${\displaystyle p}$ et ${\displaystyle q}$ sont deux nombres premiers distincts. L'application d'élévation au carré,

${\displaystyle {\overline {a}}{\pmod {N}}\mapsto {\overline {a^{2}}}{\pmod {N}}}$

est un endomorphisme du groupe des inversibles de l'anneau ℤ/Nℤ, et son noyau est isomorphe au groupe de Klein, d'ordre 4. Par conséquent, l'image de cette application est un sous-groupe d'indice 4, donc d'ordre (p-1)(q-1)/4. Ce sous-groupe est donc d'indice 2 dans celui des éléments dont le symbole de Jacobi vaut 1. Le symbole de Jacobi permet ainsi d'éliminer la moitié des éléments du groupe (ceux dont le symbole vaut -1 et qui ne sont donc pas des carrés), et le problème reste de déterminer, pour un élément arbitraire de la moitié restante, si c'est un carré ou pas (il a une chance sur deux d'en être un).

Le problème de la résiduosité quadratique est utilisé comme hypothèse de complexité dans différents protocoles cryptographiques, comme le cryptosystème de Goldwasser-Micali, ou pour le générateur de nombres pseudo-aléatoires de Blum Blum Shub.

Si la factorisation de ${\displaystyle N}$ est connue, le problème devient alors calculatoirement facile, grâce à la loi de réciprocité quadratique et au théorème des restes chinois. La procédure suivante détermine si ${\displaystyle x}$ est un carré modulo ${\displaystyle N}$.

1. Calculer ${\displaystyle x_{p}:=x}$ mod ${\displaystyle p}$ et ${\displaystyle x_{q}:=x}$ mod ${\displaystyle q}$.
2. Si ${\displaystyle x_{p}^{(p-1)/2}=1}$ mod ${\displaystyle p}$ et ${\displaystyle x_{q}^{(q-1)/2}=1}$ mod ${\displaystyle q}$, alors ${\displaystyle x}$ est un résidu quadratique modulo ${\displaystyle N}$.

Ce qui aboutit, en utilisant l'exponentiation modulaire rapide par exemple, à un algorithme de complexité ${\displaystyle {\mathcal {O}}{\bigl (}(\log N)^{2}{\bigr )}}$, ce qui est polynomial en la taille de l'entrée (ici ${\displaystyle \approx \log N}$).

Problème de la résiduosité supérieure