More Musing On Pollard Rho 


My latest posts can be found here: Previous blog posts:
Additionally, some earlier writings: 
More thoughts about Pollard Rho
The role of the function ...Pollard Rho works by iterating a function $f:Z_n > Z_n$ and we look for a cycle modulo $p,$ where $p$ is a factor of $n$. The usual function is $f(x)=x^2+c$ for some $c$, and I was wondering about using another function that "hops about" pseudorandomly, and whether that would work. But my first attempt didn't seem to work, and I speculated that the quadratic nature might actually matter. The quadratic form means that nodes in the transition graph all have out degree 1, but in degree either 0 or 2. Maybe that matters. So I decided to experiment with random graphs of different indegrees. Having indegree $k$ ...
So we pick a value of $n$  say $n=10000153$  and then for each $k$ in the range $1$ to $4$ we generate the graph. Having done so, we then run the Pollard Rho algorithm. What happens when we factor?
The hope is that with larger indegrees the graph will be more "squat" and we'll home into a cycle more quickly. That would mean that we take fewer steps, so it will run more quickly. We're still not looking at a huge improvement, but who knows. So let's run this, and give several different possible starting nodes to try to see if we get some sort of spread.
Well, that's disappointing. There doesn't actually seem to be any real change, even though you'd hope that with an indegree of 4, or 8, perhaps you'd zoom in on the cycle more quickly. But these experiments appear not to support that. Of course I'm still using relatively small numbers, about $10^7$, so maybe that matters. But even so ... I guess I really don't understand this.
Send us a comment ...

Quotation from Tim BernersLee 