Factorisation d'un nombre composé

[johnashhh]

Bonsoir,

On dit qu'un entier composé n peut être factorisé en trouvant deux entiers x et y solutions de: x^2 = y^2 mod[n]. Et que n peut s'écrire comme le produit: pgcd(x-y,n).pgcd(x+y,n) avec une probabilité de 1/2.

Je ne comprends pas très bien ce principe!

Est-ce que quelqu'un pourrait m'éclairer svp? Notamment en me donnant la preuve de ce théorème...

Merci

[Ben314]

Salut,
Je connais pas ce théorème et je comprend pas trop (ça commence SUPER fort !!! :cry:)
Pour tout valeur de n (y compris un nombre premier), on a toujours x²=y² modulo n lorsque y=n-x.
Dans ce cas, pgcd(x+y,n)=n et pgcd(x-y,n)=pgcd(2x,n)=?...

Je vois pas trop non plus l'histoire de la proba=1/2 :
n est fixé et tu regarde parmi tout les (x,y) solutions lesquels donnent une décomposition de n ?
Si n n'est pas fixé, il faut préciser la façon dont on le prend "au hasard" : on ne peut pas tirer un entier au hasard de façon équiréparti...

[johnashhh]

Vous pouvez aller voir sur l'article: eprint.iacr.org/2010/006.pdf
dans la section Factoring RSA-768 (Morrison-Brillhart)

[Ben314]

Bon, O.K. :
On fixe un entier composé et on regarde toutes les solutions de l'équation . Le but est de montrer que plus de la moitié de ces solutions donnent une décomposition de (à mon avis il faut rajouter non triviale) sous la forme
(donc le seul truc pas complètement clair de ton énoncé se raportait a la proba 1/2)

Perso, je chercherais totalement bourrin (je sais vachement bien le faire) toutes les solutions de l'équation : elle s'écrit (x-y)(x+y)=0 mod N est ça me semble pas super dur de dresser la liste des solutions : dans Z/NZ, les diviseurs de 0 sont.....