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

Ce problème est considéré comme étant calculatoirement difficile[réf. nécessaire]. 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[modifier | modifier le code]

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

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]

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[2],[3], ou pour le générateur de nombres pseudo-aléatoires de Blum Blum Shub.

Calcul avec factorisation de N connue[modifier | modifier le code]

Si la factorisation de 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 est un carré modulo .

  1. Calculer mod et mod .
  2. Si mod et mod , alors est un résidu quadratique modulo .

Ce qui aboutit, en utilisant l'exponentiation modulaire rapide par exemple, à un algorithme de complexité , ce qui est polynomial en la taille de l'entrée (ici ).

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,‎ , p. 365–377
  3. (en) S. Goldwasser et S. Micali, « Probabilistic encryption », Journal of Computer and System Sciences, vol. 28, no 2,‎ , 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)