View Single Post
Old 2020-09-15, 16:47   #2
Romulan Interpreter
LaurV's Avatar
Jun 2011

100011101101012 Posts

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 are good, your goal is to find one (not to avoid it!). Once you find the loop, its "size" gives you the factorization.

Say, for a very simple example, you want to factor the number 259. You start with a random value, say 5, and every iteration you square the former result, mod 259. Then you get: 5, 25, 107, 53, 219, 46, 44, 123, 107, bingo. There are only 258 possible outcomes (generally, less then half, why?) so eventually, you will get a value which you already have got in the past. The trick Rho does is just to find when you got this loop and how large it is. Here the example is trivial, you can see that the loop has length 6, at a glance, and you just find out that 7 is a factor. You can either say that 5^4=5^256 and work that as a difference of squares, or you can also say that 25^2=123^2, and work that as a difference of squares (and find the factors as gcd(259, 123-25)=7, and gcd(259, 123+25)=37). But for very large factors, loops can be very large, and what Rho does, it goes to extents to help you detect when you have a loop, and how big it is.

So, circle is good, is what you want to find, and you need its "size" to get to the factor.

Last fiddled with by LaurV on 2020-09-15 at 17:17
LaurV is offline   Reply With Quote