View Single Post
Old 2020-09-15, 16:57   #3
Deuterium's Avatar
Sep 2020

22 Posts

Originally Posted by LaurV View Post
You compute a result "modulo something". So, there are only a limited number of possible outcomes. The result is the input of the new "iteration". After long enough time, values will start to repeat, as there are not an "infinite amount" of them. They are only m-1 values, where m is your module. Give it enough time, they will repeat. As the calculus is deterministic, once you get the same value, you will have the same result in the next iteration like you had last time. There, you have a "loop". Loops a good, your goal is to find one (not to avoid it!). Once you find the loop, its "size" gives you the factorization.

Thanks LaurV !
So, (OMG) , a loop is a positive thing in pollard rho !
What I cannot nderstand now is this: since a loop is somewhat of random (it can pop up after 5 cycles or after 301032103 cycles), can we say that pollard rho is a complete random alghorithm ? I can factor a number of 30 digits in 10 ms or in 10 seconds...

What if we can "force" a loop by some (if exist) mathematical tricks ?
Deuterium is offline   Reply With Quote