Pollard’s Rho Algorithm for Prime Factorization
This algorithm allows you to find prime factors for a composite number, particularly fast for large numbers with small prime factors.
The Rho algorithm’s most remarkable success was the factorization of eighth Fermat number(i.e 22n+1): 115,792,089,237,316,195,423,570,985,008,687,907,853, 269,984,665,640,564,039,457,584,007,913,129, 639,937 (78 digits)
Example:
Input: n = 10;
Output: 2 [OR 5]
Input: n = 187;
Output: 11 [OR 17]
Algorithm
1.Start with random x and c. Take y equal to x and f(x) = x2 + c.
2.While a divisor isn’t obtained
a.Update x to f(x) (modulo n) [Tortoise Move]
b.Update y to f(f(y)) (modulo n) [Hare Move]
c.Calculate GCD of |x-y| and n
d.If GCD is not unity
i)If GCD is n, repeat from step 2 with another set of x, y and c
ii)Else GCD is our answer
Illustration:
Let us suppose n = 187 and consider different cases for different random values.
1) An Example of random values such that algorithm finds result:
y = x = 2 and c = 1, Hence, our f(x) = x2 + 1.
| xi+1 = f(xi) | yi+1 = f(f(yi)) | c | d = GCD(|x-y|,n) |
|---|---|---|---|
| 5 | 26 | 1 | 1 |
| 26 | 180 | 1 | 11 |
2) An Example of random values such that algorithm finds result faster:
y = x = 110 and ‘c’ = 183. Hence, our f(x) = x2 + 183.
| xi+1 = f(xi) | yi+1 = f(f(yi)) | c | d = GCD(|x-y|,n) |
|---|---|---|---|
| 128 | 111 | 183 | 17 |
3) An Example of random values such that algorithm doesn’t find result:
x = y = 147 and c = 67. Hence, our f(x) = x2 + 67.
| xi+1 = f(xi) | yi+1 = f(f(yi)) | c | d = GCD(|x-y|,n) |
|---|---|---|---|
| 32 | 156 | 67 | 1 |
| 156 | 114 | 67 | 1 |
| 93 | 48 | 67 | 1 |
| 114 | 114 | 67 | 187 |
Time Complexity Analysis:
The algorithm offers a trade-off between its running time and the probability that it finds a factor. A prime divisor can be achieved with a probability around 0.5, in O(√d) <= O(n1/4) iterations. This is a heuristic claim, and rigorous analysis of the algorithm remains open.
