Finally it comes the weekend and you can go to the mountain, but as soon as you exit home and you reach the car you find a 2256+1 sleeping on the hood. You try to move it but it is too heavy. Oh no, again! you’ll have to factor it so you can move smaller pieces…
You try trial division at first, but it is not effective in this case. Fortunately you remember what you grand father used to say to you when you was a little kid*: if you find a F8 on you way, use the Pollard’s Rho method.
Pollard’s Rho uses clever observations to probabilistic speed up the factorization process. Let n = pq, and consider the polynomial f(x) = x2 + 1 modulo n. Let choose a value for x, let’s say x1, the algorithm uses the pseudo-random sequence s1 = f(x1), s2 = f(f(x1)), s3 = f(f(f(x1))), etc, that is related to the sequence modulo p, although it is unknown and we can not compute it directly.
The sequences modulo n and modulo p at some point will repeat their elements. Since these sequences are similar to random sequences, for the Birthday Paradox we expect a repetition after O(√ N) elements, that is smaller in the mod p sequence than in mod n sequence. If you find two numbers in this sequence mod n with xa ≠ xb, but xa ≡ xb mod p than |xa – xb| is a multiple of p, so gcd(n,|xa – xb|) will give n or p.
The interesting thing here is that while trial division has a (deterministic) time complexity O(2n/2) the Pollard’s Rho method has a (probabilistic) complexity O(2n/4).
You use the polynomial x2 + 1 mod n, starting from x=3 so within minutes you find out that 115792089237316195423570985008687907853269984665640564039457584007913129639937 has at two factors: 1238926361552897 * 93461639715357977769163558199606896584051237541638188580280321. They get scared and run away so you can finally leave.
You can find a working Java implementation to save your weekend here: https://github.com/zagonico86/my-snippets/blob/main/primes/PollardRho.java
For a faster algorithm check Quadratic Sieve post.
* In reality this was an assignment of the Algebra course in the far 2008’s Fall and it is also more or less what happened in 1980 when Brent and Pollard first factored the 8th Fermat number.
