Problème de la résiduosité quadratique

Problème de la résiduosité quadratique

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é. C'est un problème important en cryptographie, en particulier si N est le produit de deux nombres premiers impairs distincts.

Sommaire

Formulation

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

\overline a~({\rm mod} N)\mapsto \overline a^2=\overline{a^2}~({\rm mod} N),

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

L'hypothèse d'intractabilité (en) est que ce problème est « difficile », i.e. coûteux[précision nécessaire] en nombre d'opérations, par rapport à la taille de N. C'est cette hypothèse qui fonde le cryptosystème de Goldwasser-Micali[2],[3].

Calcul avec factorisation de N connue

Si la factorisation de N est connue, alors le problème devient facile, calculatoirement, 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.

  1. Calculer xp: = x mod p et xq: = x mod q.
  2. 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.

Notes et références

  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 », dans STOC '82 Proceedings of the 14th annual ACM symposium on Theory of computing, 1982, p. 365–377 
  3. ↑ (en) S. Goldwasser et S. Micali, « Probabilistic encryption », dans Journal of Computer and System Sciences, vol. 28, no 2, 1984, p. 270–299 [lien DOI] 

Article connexe

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


Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Problème de la résiduosité quadratique de Wikipédia en français (auteurs)

Игры ⚽ Поможем решить контрольную работу

Regardez d'autres dictionnaires:

  • Probleme de la residuosite quadratique — Problème de la résiduosité quadratique En théorie algorithmique des nombres, le problème de la résiduosité quadratique est celui de distinguer, à l aide de calculs, les résidus quadratiques modulo N, où celui ci est un nombre composé. C est un… …   Wikipédia en Français

  • Residu quadratique — Résidu quadratique En Arithmétique modulaire, on dit qu un entier naturel q est un résidu quadratique modulo p s il existe un entier x tel que : (dans le cas contraire, on dit que q est un non résidu quadratique modulo p). En effet, un… …   Wikipédia en Français

  • Résidu quadratique — En arithmétique modulaire, on dit qu un entier naturel q est un résidu quadratique modulo p s il existe un entier x tel que : (dans le cas contraire, on dit que q est un non résidu quadratique modulo p). En effet, un résidu quadratique… …   Wikipédia en Français

  • Projet:Mathématiques/Liste des articles de mathématiques — Cette page n est plus mise à jour depuis l arrêt de DumZiBoT. Pour demander sa remise en service, faire une requête sur WP:RBOT Cette page recense les articles relatifs aux mathématiques, qui sont liés aux portails de mathématiques, géométrie ou… …   Wikipédia en Français

  • Liste des articles de mathematiques — Projet:Mathématiques/Liste des articles de mathématiques Cette page recense les articles relatifs aux mathématiques, qui sont liés aux portails de mathématiques, géométrie ou probabilités et statistiques via l un des trois bandeaux suivants  …   Wikipédia en Français

  • Cryptosysteme de Goldwasser-Micali — Cryptosystème de Goldwasser Micali En cryptographie, le cryptosystème de Goldwasser Micali (GM) est un algorithme asymétrique de cryptographie à clé publique, développé par Shafi Goldwasser et Silvio Micali en 1982. Fait notoire, GM est le… …   Wikipédia en Français

  • Cryptosystème De Goldwasser-Micali — En cryptographie, le cryptosystème de Goldwasser Micali (GM) est un algorithme asymétrique de cryptographie à clé publique, développé par Shafi Goldwasser et Silvio Micali en 1982. Fait notoire, GM est le premier cryptosystème à chiffrement… …   Wikipédia en Français

  • Cryptosystème de Goldwasser-Micali — En cryptographie, le cryptosystème de Goldwasser Micali (GM) est un algorithme asymétrique de cryptographie à clé publique, développé par Shafi Goldwasser et Silvio Micali en 1982. Fait notoire, GM est le premier cryptosystème à chiffrement… …   Wikipédia en Français

  • Cryptosystème de goldwasser-micali — En cryptographie, le cryptosystème de Goldwasser Micali (GM) est un algorithme asymétrique de cryptographie à clé publique, développé par Shafi Goldwasser et Silvio Micali en 1982. Fait notoire, GM est le premier cryptosystème à chiffrement… …   Wikipédia en Français

  • Goldwasser-Micali — Cryptosystème de Goldwasser Micali En cryptographie, le cryptosystème de Goldwasser Micali (GM) est un algorithme asymétrique de cryptographie à clé publique, développé par Shafi Goldwasser et Silvio Micali en 1982. Fait notoire, GM est le… …   Wikipédia en Français

Share the article and excerpts

Direct link
… Do a right-click on the link above
and select “Copy Link”