Pollard’s Rho algorithm is one of the most-used integer factorization algorithms. This is because its running time complexity is proportional to the square root of the size of the smallest prime factor and the amount of space used to execute the algorithm is much less than others.
There are other methods for prime factorization but we prefer Pollard’s Rho because we don’t have to test all possible integers until a divisor is found, which means it will improve the time complexity. This algorithm is more efficient than Fermat’s and wheel factorizations when comparing time and space complexity.
Suppose we have an integer, N, which is not a prime and p is the smallest prime factor of a number N. So we need to find the divisor of this number.
Example
Input: N=18
Output: 2 [can be 3, 6]
And
Input: N= 341
Output: [11]
To find the factors of N we will keep checking the numbers until N-1. At the end of one iteration we will get the factors for N.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
import java.util.*;
import java.lang.*;
import java.io.*;
public class Solution {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
System.out.print("Enter Num:");
int N = sc.nextInt();
System.out.print("Factor:");
if (N % 2 == 0) {
System.out.println("2");
return;
} else {
for (int k = 3; k < N; k++)
if (N % k == 0) {
System.out.println(k);
return;
}
}
System.out.println("No Factor");
}
}
Code Snippet
According to Pollard’s algorithm we will check all the integers lesser than the root of N.
Call method pollRho() and accept N as an integer which is to be factored.
According to the Pollard Rho algorithm, the polynomial method g(x)=(x2-1)mod N but currently we are using g(x)=(x2+1)mod N. It will give output as a trivial factor or no factor will be returned.
Step 1: Start with x=2 and take y=x
Step 2: Check if it is divisible by 2 then return 2, otherwise go to step 3
Step 3: Loop until you get a divisor
Step 4: Update x with g(x)|N|and
update y with g(g(y))|N| (where |N| is modulo of N)
Step 5: Calculate GCD for modulo of (x-y) and N.
If GCD of both number is not N then GCD is our factor
otherwise
go to step 3
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
import java.util.*;
import java.util.*;
import java.lang.*;
class Solution {
//method to calculate GCD of two numbers
static long GCD(long x, long y) {
return y == 0 ? x : GCD(y, x % y);
}
static long pollRho(long n) {
//to generate random numbers
Random randObj = new Random();
if (n == 1) return n;
//if number is even then 2
if (n % 2 == 0) return 2;
long x = (long)(randObj.nextLong() % (n - 2)) + 2;
long y = x;
long c = (long)(randObj.nextLong()) % (n - 1) + 1;
long d = 1 L;
while (d == 1) {
x = (modPollardRho(x, 2, n) + c + n) % n;
y = (modPollardRho(y, 2, n) + c + n) % n;
y = (modPollardRho(y, 2, n) + c + n) % n;
d = GCD(Math.abs(x - y), n);
if (d == n) return pollRho(n);
}
return d;
} // pollRho method ends here
static long modPollardRho(long base, int exp,
long mod) {
long res = 1;
while (exp > 0) {
if (exp % 2 == 1)
res = (res * base) % mod;
exp = exp >> 1;
base = (base * base) % mod;
}
return res;
} // modPollardRho method ends
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
System.out.print("Enter Num:");
long N = sc.nextLong();
System.out.print("Divisor of " + N + " is " +
pollRho(N));
} //main method ends
} //solution class ends
Code Snippet
Among all factorization algorithms, Pollard’s is preferred for finding small non-trivial factors of an integer.
Can use this algorithm for finding Floyd’s cycle as it can find duplicates in a sequence of integers from x1, x2, x3 … where x belongs to integer where sequence is defined by x1=2, x(i+1)=f(xi)= (Square of (xi) + 1).
The elliptic curve discrete logarithmic problem can be resolved using Pollard’s Rho algorithm. Pollard’s Rho and its modification are the most efficient general algorithms as from the proofs of Oorschot and Wiener it can be deduced that the algorithm can be parallelized with the linear speedup.
Finding Floyd’s cycle can be made efficient by implementing improvements which were made by Brent and Pollard based on calculations for the greatest common divisor. Basic Pollard’s algorithm is not enough to get an efficient result. As the improvements specify, if GCD(x,k) > 1 then gcd(xy,k) > 1, where y is an integer. We need not to calculate gcd(|x-y|,n), but it can be simplified by calculating GCD(i,n), where i is the product of |x -y|. There are some disadvantages as this may cause the algorithm to fail as there will be repeated factors which can come if N has some value. For example, if N is squared, the algorithm may fall into a repetitive cycle and go back to the last calculated GCD and do the formulation again
There are other algorithms like Pollard’s Rho which may decrease the time complexity, but a drawback is that they increase memory usage as they store the calculated sequence values.
Comparing trial division, quadratic sieve, Dixon’s algorithm, etc. with the time complexity of Pollard’s Rho algorithm shows that Pollard’s Rho algorithm is more efficient to use than those algorithms mentioned.
https://research.ijcaonline.org/volume121/number18/pxc3904969.pdf
https://en.wikipedia.org/wiki/Lenstra_elliptic-curve_factorization
https://maths-people.anu.edu.au/~brent/pd/rpb231.pdf