View Single Post
Old 2007-06-24, 13:07   #3
xilman
Bamboozled!
 
xilman's Avatar
 
"π’‰Ίπ’ŒŒπ’‡·π’†·π’€­"
May 2003
Down not across

295E16 Posts
Default

Quote:
Originally Posted by mgb View Post
I am experimenting with an algorithm for integer factorization described in this thread.

http://www.artofproblemsolving.com/F...=858406#858406

Any comments?
It appears to be a variant on Pollard rho and you should analyze the map f(x) -> x^x for its cycle behaviour.

It's possible that it it behaves better than a random mapping, in which the cycle length is usefully less than sqrt(N) --- the observed behaviour for the classical Pollard rho mapping f(x) -> ax^2+c --- but without the analysis I'm not convinced that it's even as good as Pollard's mapping in this regard.

What does seem clear is that each iteration is much more computationally demanding than rho's single multiplication and addition in Z_N.

I urge you to examine the cycle behaviour in more depth. Numerical experiments could well give you insight in how to approach the problem.

Good luck! You may be on to something but don't get your hopes too high.

Paul
xilman is offline   Reply With Quote