Re: is it sufficient to solve factoring problem

laicko a écrit :
I test it with small primes's product. The results of gcd(X[i] +/- 1,
N) is 1, N, or the factors.

Yes, it can be 1 or N because the algo I gave is not correct. When
X[i+1] = 1, check whether X[i] = N-1 and if this is the case go back
to "take a random X".

> However, if phi(N) = a* 2^i with some big
i, maybe the solution will cost much, right?

No, in fact, it will cost a little less.
Count the number of squares and of multiplications you have
to do for both the exponentiation X^K and the sequence X[i].

mm
.