Un article de Wikipédia, l'encyclopédie libre.
En théorie des nombres calculatoire, 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.
[modifier] 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) il est difficile de déterminer si x est un résidu quadratique modulo N (i.e., x = y2 mod N pour un y), losrque le symbole de Jacobi pour x est +1.
[modifier] 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. Par exemple, considérons le cas simple où N = pq avec 
et 
, des nombres premiers. La procédure suivante détermine si x est une racine carrée modulo N.
- Calculer xp = x mod p, xq = x mod q.
- Si
mod p et 
mod q, alors x est un résidu quadratique modulo N.
Vous avez de 
