Problème de la résiduosité quadratique

En théorie algorithmique des nombres, le problème de la résiduosité^{[note 1]} quadratique est celui de distinguer, à l'aide de calculs, les résidus quadratiques modulo un nombre composé N fixé.

Ce problème est considéré comme étant calculatoirement difficile dans le cas général et sans information supplémentaire^[1]. Par conséquent, il s'agit d'un problème important en cryptographie où il est utilisé comme hypothèse calculatoire comme indiqué dans la section Application.

Formulation

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

Application

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.

Calcul avec factorisation de N connue

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}$).