Problème de la résiduosité quadratique

Cet article est une ébauche concernant les mathématiques.

Vous pouvez partager vos connaissances en l’améliorant (comment ?) selon les recommandations des projets correspondants.

Consultez la liste des tâches à accomplir en page de discussion.

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

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

{\overline {a}}{\pmod {N}}\mapsto {\overline {a^{2}}}{\pmod {N}}

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

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

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

Calculer $x_{p}:=x$ mod $p$ et $x_{q}:=x$ mod $q$ .
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$ .

Ce qui aboutit, en utilisant l'exponentiation modulaire rapide par exemple, à un algorithme de complexité ${\mathcal {O}}{\bigl (}(\log N)^{2}{\bigr )}$ , ce qui est polynomial en la taille de l'entrée (ici $\approx \log N$ ).

Notes et références modifier

(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).

Notes modifier

↑ 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

↑ (en) Victor Shoup, A computational introduction to number theory and algebra, Cambridge University Press, 2009, 2^e é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.

Article connexe modifier

Problème de la résiduosité supérieure

[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]}

[shoup-2] (en) Victor Shoup, A computational introduction to number theory and algebra, Cambridge University Press, 2009, 2^e é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.

[note 1]

[1]