Re:Idle Thoughts About Pollard Rho
by vmilner on Tuesday September 11, 2018 @06:32PM
(#17963987)
The asymptotic means for tails and cycles of random functions are in Theorem 3 of
https://link.springer.com/content/pdf/10.1007/3-540-46885-4_...
[ Parent
| on HN ]
Re:Idle Thoughts About Pollard Rho
by ColinWright on Tuesday September 11, 2018 @07:12PM
(#17964249)
Great catch - thank you! Now to find some time to read it properly.
Antoine Joux's book:
https://books.google.co.uk/books?id=buQajqt-_iUC
precis-es this paper in its sections 7.2 and 7.3 and highlights the fact that looking at "Pollard rho style" random functions with in-degree 0 or 2, merely changes the multiplicative constants of the tail and cycle statistics without changing the order.
Re:Idle Thoughts About Pollard Rho
by ColinWright on Wednesday September 12, 2018 @05:43AM
(#17966888)
That's pretty much what I was expecting, and it's great to see that someone's done the work. I never expected my idle musings to be in any way new or insightful, so it's nice to be able to see that at least I'm not completely off-track.
I'm now wondering about constructing fast-to-compute functions with in-degree (0,0,3) or (0,0,0,4), which should change the characteristics, but I need to read a bit first.
Again, thanks.