Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction 
2.
Congruent Modulo
3.
Greatest Common Divisor
4.
Floyd’s Cycle Detection Algorithm
5.
The Pollard Rho Algorithm
5.1.
Algorithm
5.2.
Code Implementation
5.2.1.
Output
5.3.
Code Implementation in Java
5.3.1.
Output
5.4.
Code Implementation in Python
5.4.1.
Output
6.
Frequently Asked Questions
6.1.
What is the use case of the pollard rho algorithm?
6.2.
What are some prerequisites to understanding the pollard rho algorithm?
6.3.
What is the RSA algorithm in cryptography?
6.4.
What is the full form of RSA and AES?
7.
Conclusion
Last Updated: Mar 27, 2024
Medium

The Pollard Rho Algorithm

Author Shiva
0 upvote
Master Python: Predicting weather forecasts
Speaker
Ashwin Goyal
Product Manager @

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.

introductory image

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. 

rho image

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

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

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;
}

Output

output image

Code Implementation in Java

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

output image

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

output image

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 - 


You may refer to our Guided Path on Code Studios for enhancing your skill set on DSACompetitive ProgrammingSystem Design, etc. Check out essential interview questions, practice our available mock tests, look at the interview bundle for interview preparations, and so much more!

Happy Learning Ninjas!

Previous article
The Pollard P-1 Algorithm
Next article
Dixon’s Random Squares Algorithm
Live masterclass