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[modifier | modifier le code]
Soit un nombre composé de la forme particulière , où et sont deux nombres premiers distincts. L'application d'élévation au carré,
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[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, 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 .
- Calculer mod et mod .
- 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]
Notes[modifier | modifier le code]
- Une substantivation plus correcte serait résidualité. Le néologisme résiduosité a été adopté par la plupart des cryptographes.[réf. nécessaire]
Références[modifier | modifier le code]
- (en) Victor Shoup, A computational introduction to number theory and algebra, Cambridge University Press, , 2e éd., 580 p. (ISBN 978-0-521-51644-0 et 0521516447, OCLC 277069279, lire en ligne), 12. Quadratic reciprocity and computing modular square roots, chap. 4 (« Testing quadratic residuosity »), p. 349.