Problème de la résiduosité quadratique
Un article de Wikipédia, l'encyclopédie libre.
Cet article est une ébauche concernant les mathématiques.
Vous pouvez partager vos connaissances en l’améliorant. (Comment ?).
|
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.
[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), où N est un nombre composé, il est difficile de déterminer si x est un résidu quadratique modulo N (i.e., x = y2 mod N pour un y), lorsque 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.
Dans le cas simple où N = pq avec et , 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.
- Calculer xp = x mod p, xq = x mod q.
- Si mod p et mod q, alors x est un résidu quadratique modulo N.