Problème de la résiduosité quadratique

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

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[modifier | modifier le code]

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[modifier | modifier le code]

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[modifier | modifier le code]

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[modifier | modifier le code]

  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 », 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 », Journal of Computer and System Sciences, vol. 28, no 2,‎ 1984, p. 270–299 (DOI 10.1016/0022-0000(84)90070-9)

Article connexe[modifier | modifier le code]

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