Do you think IIT Guwahati certified course can help you in your career?
Introduction
This article will look into the pollard rho algorithm and cover some prerequisites like understanding the Congruent modulo, the Greatest common divisor, and the Floyd cycle detection algorithm. Before reading this, you don’t need to know anything, so don’t worry and buckle up! We will go through everything. We got you covered.
In case you are wondering about “rho” in the name, the “rho” in the pollard rho algorithm comes from the shape it makes when drawn in a graph :o.
Congruent Modulo
If m divides a-b, we can say that a≡ (is congruent to) b %(modulo) m. This can be written as
a ≡ b mod m, is same as m|(a-b).
a ≡ b mod m, simply means that when a and b are divided by m, they have the same remainder.
Eg. 4≡1 mod 3
Greatest Common Divisor
Two integers, X and Y's greatest common divisor (GCD), are the greatest integer that divides both X and Y. GCD is also known as Highest Common Factor or HCF.
We use the Euclidean Algorithm technique for quickly determining the GCD of two integers.
Eg. GCD(8, 12) = 4.
The euclidean algorithm works based on the 2 observations listed below.
When we subtract a smaller number from a larger one, GCD does not change (we reduce the larger number). So, if we continue to deduct the larger of two values, we get GCD.
Instead of subtracting, divide the smaller integer, and the algorithm will stop when the remainder is zero.
Floyd’s Cycle Detection Algorithm
Refer to this amazing article to understand Floyd's cycle detection algorithm.
The Pollard Rho Algorithm
The Pollard rho technique is a method for determining the prime factors of any integer. Pollard's Rho algorithm has a running time complexity proportional to the square root of the size of the smallest prime factor.
The reason why Pollard's Rho algorithm is preferred because here we don't have to test all potential numbers until a divisor is found, which reduces time complexity.
Algorithm
Step 1: Start off with x=2, y=x, g(x)=x^2+c
Step 2: if n is even return 2
Step 3: Loop until we find a divisor
Step 4: Set x = g(x)%N and update y = g(g(y))%N
Step 5: get GCD of (|x-y|, N).
If GCD(|x-y|, N) is not equal to N, then returned GCD is our answer
else go to step 3
Now, we will implement the pollard rho algorithm.
Code Implementation
Implementation of the pollard rho algorithm in C++:
/* implementation of Pollard's Rho algorithm in C++ to identify a prime factor of a composite. */
#include<bits/stdc++.h>
#define ll long long
using namespace std;
int getGCD(ll a, ll b) {
/*because, gcd(0, b) = b.*/
if (a == 0)
return b;
/* using the euclidean algorithm for finding GCD*/
return getGCD(b % a, a);
}
/* utility function to calculate a^b%m */
ll getModExpo(ll base, int expnt, ll mod) {
ll ans = 1;
/* continue loop till exp reduces to zero*/
while (expnt > 0) {
if (expnt % 2 != 0)
ans = (ans * base) % mod;
expnt = expnt / 2;
base = (base * base) % mod;
}
return ans;
}
/* implementation of rho Algorithm */
ll getPrimeRho(ll num) {
/* base cases */
if (num == 1) return num;
if (num % 2 == 0) return 2;
/* range from [2, num-1] */
ll l = (rand() % (num - 2)) + 2;
ll r = l;
/* If the constant in f(x) fails for a composite, it can be re-run with a different k. */
ll k = (rand() % (num - 1)) + 1;
/* Initialize candidate divisor (or result) */
ll p = 1;
/* until the prime factor isn't obtained.
If n is prime, return n */
while (p == 1) {
/* Tortoise Move: l(i+1) = f(l(i)) */
l = (getModExpo(l, 2, num) + k + num) % num;
/* Hare Move: r(i+1) = f(f(r(i))) */
r = (getModExpo(r, 2, num) + k + num) % num;
r = (getModExpo(r, 2, num) + k + num) % num;
/* check gcd of |x-y| and num */
p = getGCD(abs(l - r), num);
/* If the algorithm fails to identify a prime factor with the given l and c, retry. */
if (p == num) return getPrimeRho(num);
}
return p;
}
int main() {
ll n;
cout << "Enter a number:";
cin >> n;
cout << "Factor of the " << n << " is: " << getPrimeRho(n);
return 0;
}
You can also try this code with Online C++ Compiler
import java.util.*;
class ClassName {
/* Function to calculate (base^exponent)%modulus */
static long getModPow(long base, int exponent, long modulus) {
/* initialize result */
long ans = 1;
while (exponent > 0) {
/* if y is odd, multiply base with result */
if (exponent % 2 == 1)
ans = (ans * base) % modulus;
exponent = exponent / 2;
base = (base * base) % modulus;
}
return ans;
}
/* method to return prime divisor for n */
static long getPrimeRho(long n) {
/* initialize random seed */
Random r = new Random();
/* no prime divisor for 1 */
if (n == 1) return n;
/* even number means one of the divisors is 2 */
if (n % 2 == 0) return 2;
/* we will pick from the range [2, N-1] */
long x = (long)(r.nextLong() % (n - 2)) + 2;
long y = x;
/* the constant in f(x).
* Algorithm can be re-run with a different c
* if it throws failure for a composite. */
long c = (long)(r.nextLong()) % (n - 1) + 1;
/* Initialize candidate divisor (or result) */
long d = 1 L;
/* until the prime factor isn't obtained.
If n is prime, return n */
while (d == 1) {
/* Tortoise Move: x(i+1) = f(x(i)) */
x = (getModPow(x, 2, n) + c + n) % n;
/* Hare Move: y(i+1) = f(f(y(i))) */
y = (getModPow(y, 2, n) + c + n) % n;
y = (getModPow(y, 2, n) + c + n) % n;
/* check gcd of |x-y| and n */
d = gcd(Math.abs(x - y), n);
/* retry if the algorithm fails to find prime factor
* with chosen x and c */
if (d == n) return getPrimeRho(n);
}
return d;
}
static long gcd(long a, long b) {
/* because, gcd(0, b) = b. */
if (a == 0)
return b;
/* using the euclidean algorithm for finding GCD */
return gcd(b % a, a);
}
public static void main(String[] args) {
long num = 123456789 L;
System.out.printf("One of the divisors for " + num + " is " + getPrimeRho(num));
}
}
Output
Code Implementation in Python
import random
import math
""" utility function to calculate a^b%m """
def getModExpo(base, exp, mod):
res = 1
while exp > 0:
"""if y is odd, multiply base with result"""
if exp & 1:
res = (res * base) % mod
exp = exp >> 1
base = (base * base) % mod
return res
def getPrimeRho(n):
"""no prime divisor for 1"""
if n == 1:
return n
"""even number means one of the divisors is 2"""
if n % 2 == 0:
return 2
"""we will pick from the range [2, N-1]"""
x = random.randint(0, 2) % (n - 2)
y = x
"""If the constant in f(x) fails for a composite, it can be re-run with a different k."""
c = random.randint(0, 1) % (n - 1)
"""Initialize candidate divisor (or result)"""
d = 1
"""until the prime factor isn't obtained. If n is prime, return n"""
while d == 1:
"""Tortoise Move: x->next = f(x)"""
x = (getModExpo(x, 2, n) + c + n) % n
"""Hare Move: y->next = f(f(y))"""
y = (getModExpo(y, 2, n) + c + n) % n
y = (getModExpo(y, 2, n) + c + n) % n
d = math.gcd(abs(x - y), n)
"""retry if the algorithm fails to find prime factor with chosen x and c"""
if d == n:
return getPrimeRho(n)
return d
if __name__ == "__main__":
n = 1234567789
print("One of the divisors for", n, "is ", getPrimeRho(n))
Output
Frequently Asked Questions
What is the use case of the pollard rho algorithm?
The Pollard rho algorithm is an excellent method for determining the prime factors of any integer.
What are some prerequisites to understanding the pollard rho algorithm?
Knowledge of GCD, Congruent modulo, and Floyd's cycle detection algorithm helps understand the pollard p-1 algorithm.
What is the RSA algorithm in cryptography?
The RSA algorithm (Rivest-Shamir-Adleman) is the foundation of a cryptosystem, which is a collection of cryptographic algorithms used for certain security services or objectives.
What is the full form of RSA and AES?
AES stands for Advanced Encryption Standard, and RSA is for Rivest, Shamir, and Adleman.
Conclusion
This article looked into the pollard rho algorithm and covered prerequisites like GCD, Congruent modulo, and Floyd's cycle detection algorithm.
If you want to explore more, here are some related articles -
568+ registered 
