factor(n)

[invite0972ca96]

Bjr,

Pourquoi pour la factorisation des entiers, ne pas utiliser l'algo suivant;

Construir la suite As+1=As^2 (mod n) : A0=2.
puis , en utilisant l'algo de Floyd, detecter lorsque As+k=As, (càd lorsque la suite devient cyclique).
puis en deduir que (As-1)^2=(As+k-1)^2 (mod n).
Donc,GCD[((As-1)+(As+k-1));n]|n. Puis appliquer l'algo par recurence jusque à la factorisation complete de n.

Ainsi, la difficulté de facto dépends seulement de la recherche de collisions de la suite, et je croi, que pour cela, la methode de Floyd est plutot efficace?! Non?

Merci
-----

[invitebe0cd90e]

C'est exactement l'algorithme rho de Pollard : http://fr.wikipedia.org/wiki/Algorithme_rho_de_pollard

C'est un algo probabiliste (dans le sens ou effectivement GCD[((As-1)+(As+k-1));n] divise n, mais ca ne veut pas dire qu'on a alors trouvé un facteur non trivial de n).

Il est plutot performant mais si ma memoire est bonne c'est en gros de complexité polynomiale en p, ou p est le plus petit diviseur de n, donc ca marche bien pour un nombre qui a de petits facteurs. Mais pour un nombre RSA, par exemple, ou les facteurs sont en gros de taille |n|/2, ca reste largement exponentiel en |n|.

[invite0972ca96]

Re,

Merci, ms justement, de 2 choses l'une, pourquoi l'algo Rho ajoute un coeff supplementaire (c) à f(x)?? Puis, il cherche As=As+k [p], contrairement à celui de dessus?!Bref je trouve l'explication un peu flou, auriez vous l'amabilité de m'expliquer?

[acx01b]

juste un petit détail dans RSA :
où les facteurs sont en gros de taille 2^(q/2), où q est le nombre de bits (RSA 256 bits par exemple) ca reste largement exponentiel en q.

[A voir en vidéo sur Futura]

[invite0972ca96]

Oui,

Merci pour la precision, mais pourrait-on m'expliquer la methode Rho svp, entre autre, pourquoi f(x)=x^2 +c mod n et pas simplement x^2 mod n. De plus, pourquoi lorsque le cycle est detecter, As-As+k est un multiple de p ?

Par avance (pas trop j'espere : )) merci.

[invite0972ca96]

Personne pour répondre??