Forme quadratique pour factoriser n=pq

[invite0972ca96]

Bonjour,

Pourquoi cherchez x^2=y^2 ( mod n)

Alors qu'on peut chercher x^2-y^2 = n qui nous assure , si on trouve, le resultat a 100%



Merci
-----

[invite0972ca96]

Alors? Personne?

[invité576543]

64 - 49 = 0 modulo 5

Comment le fait que 9 - 4 = 5 permet de donner toutes les autres solutions, dont celle qui précède?

Je pense n'avoir pas compris la question, donc.

Cordialement,

[invite2b662c2b]

Simplement parce que c'est plus "facile" de trouver x et y dans le premier cas que dans le 2eme.
Si on connaissait un algorithme efficace pour trouver un couple (x,y) tel que x²-y²=n on ne s'embeterait pas à chercher des couples (x,y) ts x²=y² mod n

[A voir en vidéo sur Futura]

[invitebe0cd90e]

Ou autrement dit, quand tu tires des entiers x,y au hasard, si tu tombes sur des entiers tels que x^2-y^2 = 0 mod n, mais x^2-y^2 different de n, tu ne vas pas les jeter au pretexte que ca n'est pas assez bien Tant qu'a faire tu essaies quand meme de voir si ca ne te donne pas un facteur de n. Et comme tu as beaucoup plus de chances de tomber sur ce cas que sur l'autre...

jettes un oeil la dessus, par exemple : http://fr.wikipedia.org/wiki/Algorithme_rho_de_Pollard

[invite2b662c2b]

Ou autrement dit, quand tu tires des entiers x,y au hasard

Rien ne nous impose de tirer des entiers au hasard et de voir si ça marche.

Par exemple, si on cherche un entier x tel que x + 17 = n, on va pas s'amuser à tirer x au hasard et voir si ça colle. Ni d'ailleurs commencer par chercher un x tel que x=n mod 17 et espérer que ça marche. On va le calculer directement.

Ici précisement, même si x²=y² mod n ne nous donne pas tout le temps le résultat, on aboutira quand même plus vite qu'en cherchant directement x²-y²=n parce que dans le premier cas on a un algorithme qui nous permet de fournir "rapidement" plusieurs couples (x,y), et dans le 2eme cas, on n'en connait pas encore de rapide.

[invitebe0cd90e]

Je suis d'accord, mais dans le contexte de la factorisation des grands entiers (qui est bien le contexte de cette question), il s'agit bien de tirer des entiers au hasard et d'augmenter la probabilité de tomber sur un facteur de n. C'etait de cette manière qu'il fallait comprendre ma réponse.

[invite0972ca96]

Re,

Merci, est-ce juste si je dit que c'est plus rapide dans le 2eme cas car modulo n est un groupe fermé contenant [sqrt(n)]-1 possibilités? Sinon comment le formuler?

Ps: ce n'est pas un exo