X carré modulo n = a, x = ???

[Vinchou]

Bonjour à tous,

En plein dans l'écriture d'un programme informatique, je suis coincé sur la résolution du problème suivant dans un temps raisonnable :

trouver les x entiers tels que x carré modulo n = a

Je précise que les nombres n sur lesquels je travaille sont très grand (plusieurs milliers de chiffres) et que je ne peux me permettre de tester tous les nombres de 0 à n. J'ai beau avoir ressorti mes vieux cours de prépa et autres sur la théorie des nombres, parcouru un nombre incroyable de sites à la recherche d'une solution, je n'ai rien trouvé qui pourrait m'aider à résoudre ce problème.

Et vous?

Merci d'avance même si c'est pour me dire qu'il n'existe pas de solution simple connue à ce problème...

[abcd22]

Bonjour,
Le problème de l'extraction de racines carrées est en effet très difficile dans le cas général. J'ai trouvé dans un de mes cours un algorithme (probabiliste, en temps polynomial) de calcul dans les corps finis, et il y a aussi des algorithmes (probabilistes et en temps polynomial aussi) de factorisation de polynômes sur , q puissance d'un nombre premier impair, qu'on peut utiliser pour trouver les racines carrées modulo un nombre premier (c'est dans Modern Computer Algebra de von zur Gathen et Gerhard et certainement dans d'autres livres). Dans le cas général ben t'as la factorisation de n c'est faisable avec le théorème chinois, et sinon le problème de la recherche de racines carrées modulo n est équivalent à celui de la factorisation de n (si on sait trouver facilement une racine carrée (si n n'est pas premier 1 a au moins 4 racines carrées modulo n), on prend a au hasard et on cherche une racine carrée de a², b, donc a² = b² mod n, i.e n divise (a+b)(a-b), avec une proba 1/2, b ou -b est différent de a modulo n, et on a une factorisation de n en calculant pgcd(n, a-b) ou pgcd (n, a+b)), et il n'y a pas d'algorithme rapide pour trouver.

[serge75]

Il n'y a pas de solution simple à ton problème, et heureusement car sinon on saurait casser le code RSA.

Justification rapide :
supposons que a soit un carré, a=b², alors résoudre x²=a revient à résoudre (modulo n oeuf corse) x²=b², ou encore (x-b)(x+b)=0, ou en d'autre termes à factoriser n. Or le codage RSA tient sur le fait qu'il est trés difficile, voire impossible en temps fini, de factoriser un trés grand nombre.

Ceci dit, il peut y avoir des solutions dans certains cas particuliers, mais pas de solution générale.

[Vinchou]

Merci de vos réponses

Je me doutais un peu qu'il n'y avait pas de solution simple à mon problème, maintenant j'en ai la confirmation. Va falloir tout reprendre depuis le début :triste: