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 ℤ/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 .

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

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

  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]

Article connexe[modifier | modifier le code]

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