Résidus quadratiques.

[invite00899047]

Bonjour à tous.

J'ai vu sur internet qu'il etait possible de resoudre le probleme suivant calculer y dans :


y²=x mod M

Conaissant x et dans le cas ou M=p*q avec p et q des nombres premiers congrus a 3 modulo 4 (que l'on connait).

Donc je sais que ce problème a une solution mais je ne sais pas vraiment comment l'aborder même si il me fait penser aux restes chinois.

Serait t'il possible de m'expliquer la méthode sur un exemple simple comme:

y²=2860 mod 6077 sachant que 103*59= 6077

(je sais que 2860 est un résidu quadratique)

D'avance merci!
-----

[inviteb250fe1a]

Salut

Comment sais-tu que cette équation a une solution ? Je ne vois pas d'autre moyen qu'en déterminer une pour le voir, le symbole de Jacobi vaut 1 ici et ne permet donc pas d'affirmer quoi que ce soit. J'ai fait une petite procédure en python qui me permet de trouver 4 solutions, par exemple 2860 = 451² [6077], elle permet d'obtenir toutes les autres.