Problème de la résiduosité quadratique
{{#invoke:Bandeau|ébauche}} En théorie algorithmique des nombres, le problème de la résiduosité<ref group = "note">Modèle:Refnec</ref> 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<ref name = "shoup">Modèle:Ouvrage.</ref>. 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 <math>N</math> un nombre composé de la forme particulière <math>N=pq</math>, où <math>p</math> et <math>q</math> sont deux nombres premiers distincts. L'application d'élévation au carré,
- <math>\overline a\pmod N\mapsto\overline{a^2}\pmod N</math>
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 <math>N</math> 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 <math>x</math> est un carré modulo <math>N</math>.
- Calculer <math>x_p := x</math> mod <math>p</math> et <math>x_q := x</math> mod <math>q</math>.
- Si <math>x_p^{(p-1)/2} = 1</math> mod <math>p</math> et <math>x_q^{(q-1)/2} = 1</math> mod <math>q</math>, alors <math>x</math> est un résidu quadratique modulo <math>N</math>.
Ce qui aboutit, en utilisant l'exponentiation modulaire rapide par exemple, à un algorithme de complexité <math>\mathcal O \bigl((\log N)^2 \bigr)</math>, ce qui est polynomial en la taille de l'entrée (ici <math>\approx \log N</math>).
