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 problème important en cryptologie.

Hypothèse d'intractabilité

L'hypothèse d'intractabilité associé au problème de la résiduosité quadratique est la suivante. Étant donné (x,N), où N est un nombre composé, il est difficile de déterminer si x est un résidu quadratique modulo N (i.e., x = y² mod N pour un y), lorsque le symbole de Jacobi pour x est +1.

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.

Dans le cas simple où N = pq avec $p \,$ et $q \,$, des nombres premiers, on peut conclure directement à l'aide du théorème des restes chinois. La procédure suivante détermine si x est un carré modulo N.

1. Calculer x_p = x mod p, x_q = 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.

Applications

• Cryptosystème de Goldwasser-Micali

Ce document provient de « Probl%C3%A8me de la r%C3%A9siduosit%C3%A9 quadratique ».