Problème de la résiduosité quadratique

En théorie algorithmique des nombres, le problème de la résiduosité^[1] quadratique est celui de distinguer, à l'aide de calculs, les résidus quadratiques modulo un nombre composé N fixé. C'est un problème important en cryptographie, en particulier si N est le produit de deux nombres premiers impairs distincts.

Formulation

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

$\overline a~({\rm mod} N)\mapsto \overline a^2=\overline{a^2}~({\rm mod} N),$

est un endomorphisme du groupe des inversibles de l'anneau Z/NZ, 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

L'hypothèse d'intractabilité (en) est que ce problème est « difficile », i.e. coûteux^{[précision nécessaire]} en nombre d'opérations, par rapport à la taille de N. C'est cette hypothèse qui fonde le cryptosystème de Goldwasser-Micali^[2],[3].

Calcul avec factorisation de N connue

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

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

Notes et références

1. ↑ Une substantivation plus correcte serait résidualité. Le néologisme résiduosité a été adopté par la plupart des cryptographes.^{[réf. nécessaire]}
2. ↑ (en) S. Goldwasser et S. Micali, « Probabilistic encryption and how to play mental poker keeping secret all partial information », dans STOC '82 Proceedings of the 14th annual ACM symposium on Theory of computing, 1982, p. 365–377 
3. ↑ (en) S. Goldwasser et S. Micali, « Probabilistic encryption », dans Journal of Computer and System Sciences, vol. 28, n^o 2, 1984, p. 270–299 [lien DOI] 

• (en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Quadratic residuosity problem » (voir la liste des auteurs)

Article connexe

Problème de résiduosité d'ordre supérieur (en)