Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction 
2.
Modular Exponentiation
3.
Greatest Common Divisor
4.
The Pollard P-1 Algorithm
4.1.
Algorithm
4.2.
Code Implementation in C++
4.2.1.
Output
4.3.
Code Implementation in Java
4.3.1.
Output
4.4.
Code Implementation in Python
4.4.1.
Output
5.
Frequently Asked Questions
5.1.
What is the use case of the pollard p-1 algorithm?
5.2.
What are some prerequisites to understanding the pollard p-1 algorithm?
5.3.
What is the RSA algorithm in cryptography?
5.4.
What is the full form of RSA and AES?
6.
Conclusion
Last Updated: Mar 27, 2024
Medium

The Pollard P-1 Algorithm

Author Shiva
0 upvote

Introduction 

Let’s address the common misunderstanding first, its “pollard p-minus” not “pollard p-one” in the pollard p-1 algorithm (͡• ͜ʖ ͡•). 

introductory image

In this article, we will look into the pollard p-1 algorithm, and we’ll also cover some pre-requisite like understanding modular exponentiation and the greatest common divisor as we’ll be using it. You don’t need to know anything before reading this, so don’t worry and buckle up! We will go through everything. We got you covered.

Modular Exponentiation

Modular exponentiation basically means power in modular arithmetic.

Suppose you are given 3 variables a,b, and p, and you need to solve: a^b % p. Given that these are large numbers solving directly without optimization would mean saying goodbye to your CPU. 

So, we’ll look into some properties of modular exponentiation and will make some use of that: 

(a * b) % p = ((a % p) * (b % p)) % p

If b is even: 

(a ^ b) % c = ((a ^ b/2) * (a ^ b/2))%c 

If b is odd: 

(a ^ b) % c = (a * (a ^( b-1))%c 

Greatest Common Divisor

Two integers, A and B's greatest common divisor (GCD), are the greatest integer that divides both A and B. 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 two values, we get GCD.

Instead of subtracting, divide the smaller integer, and the algorithm will stop when the remainder is zero.

The Pollard P-1 Algorithm

The Pollard p-1 technique is a method for determining the prime factors of any integer. It is difficult to factorize a large odd number, n, into its corresponding prime factors. The Pollard P-1 Algorithm can quickly calculate all of the unique prime factors by combining Modular Exponentiation and GCD.

Algorithm

  • Enter the number(num)
  • Initialize base = 2, iterator(itr) = 2
  • Do while factor is not returned (loop)

    base = (base^i) mod num

    p = GCD(base-1, n) 

    if 1 < p < n then     

        return p 

    else     

        itr = itr+1

  •   Other factors, f = n/p
  •   If f is not prime     

      num = f     

      continue the loop 

  •   else     

      p and f are two prime factors.
 

Now, we will implement the pollard p-1 algorithm. 

Code Implementation in C++

Implementation of the pollard p-1 algorithm in C++: 

#include<bits/stdc++.h>

using namespace std;

int findGCD(int a, int b) {
  /* because, gcd(0, b) = b. */
  if (a == 0)
    return b;
  /* using the euclidean algorithm for finding GCD */
  return findGCD(b % a, a);
}

/* function for primality check */
bool checkPrime(int num) {
  /* 0 is not a prime number */
  if (num <= 1 || num % 2 == 0)
    return false;

  for (int itr = 3; itr * itr <= num; itr += 2)
    if (num % itr == 0)
      return false;
  return true;
}

/* Implementation of the pollard p-1 algorithm to find prime factors of the number*/
int pollardPMO(int n) {
  long long base = 2;
  int itr = 2;
  /* continue operation till a prime factor is obtained */
  while (true) {
    base = ((long long) pow(base, itr)) % n;
    base += n;
    base %= n;

    int d = findGCD(base - 1, n);
    /* check if the factor obtained */
    if (d > 1) {
      /* factor found, return it */
      return d;
      break;
    }
    /* exponent increment */
    itr += 1;
  }
}

int main() {
  int num;
  cout << "Enter number:";
  cin >> num;
  int temp = num;
  /* vector for storing prime factors of the number */
  vector < int > res;

  /* continue operation till the provided number is exhausted and factors are obtained */
  while (true) {
    int p = pollardPMO(temp);
    /* adding the prime number to the result array */
    res.push_back(p);

    /* exhausting the provided number*/
    int r = (temp / p);

    /* primality check */
    if (checkPrime(r)) {
      /*  inserting the prime factor */
      res.push_back(r);
      break;
    }
    /* continue the operation of the reduced number is not prime */
    else temp = r;
  }
  cout << "Prime factors of " << num << " are:" << endl;
  for (int x: res) cout << x << endl;

  return 0;
}

Output

output

Code Implementation in Java

Implementation of the pollard p-1 algorithm in java: 

import java.util.*;

class ClassName {
  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);
  }

  /* function for primality check */
  static boolean checkPrime(long n) {
    if (n <= 1)
      return false;
    if (n == 2 || n == 3)
      return true;
    if (n % 2 == 0)
      return false;
    for (long i = 3; i * i <= n; i += 2)
      if (n % i == 0)
        return false;
    return true;
  }

  /*function to generate prime factors*/
  static long pollardPMO(long n) {
    /*defining base*/
    long a = 2;

    /*defining exponent*/
    long i = 2;

    /*iterate till a prime factor is obtained*/
    while (true) {

      /*recomputing a as required*/
      a = ((long) Math.pow(a, i)) % n;
      a += n;
      a %= n;

      /*finding gcd of a-1 and n using math function*/
      long d = gcd(a - 1, n);

      /* check if the factor obtained */
      if (d > 1) {
        /* factor found, return it */
        return d;
      }

      /* exponent increment */
      i += 1;
    }
  }

  public static void main(String[] args) {

    Scanner scn = new Scanner(System.in);
    System.out.print("Enter the value: ");
    long num = scn.nextLong();

    long temp = num;

    /* vector for storing prime factors of the number */
    ArrayList < Long > res = new ArrayList < Long > ();

    /* continue operation till a prime factor is obtained */
    while (true) {
      long d = pollardPMO(temp);
      /* adding the prime number to the result array */
      res.add(d);

      /* exhausting the provided number*/
      long r = (temp / d);

      /* primality check */
      if (checkPrime(r)) {
        /*  inserting the prime factor */
        res.add(r);
        break;
      }
      /* continue the operation of the reduced number is not prime */
      else

        temp = r;
    }

    System.out.print("Factors of the " + num + " are ");
    for (long elem: res)
      System.out.print(elem + " ");
  }
}

Output

output

Code Implementation in Python

Implementation of the pollard p-1 algorithm in python: 

import math

def isprime(n):
    n = 9
    flag = 0
    if n > 1:
        for k in range(2, int(math.sqrt(n)) + 1):
            if n % k == 0:
                flag = 1
            break
        if flag == 0:
            return True
        else:
            return False
    else:
        return False


""" Implementation of the pollard p-1 algorithm to find prime factors of the number"""
def pollardPMO(n):
    a = 2
    i = 2
    """ continue operation till a prime factor is obtained """
    while True:
        a = (a**i) % n
        d = math.gcd((a - 1), n)
        """check if factor obtained"""
        if d > 1:
            """factor found, return it"""
            return d
            break
        """ exponent increment """
        i += 1

n = 1313
"""temporarily storing n"""
num = n
"""list for storing prime factors of the number"""
res = []
"""iterated till all prime factors are obtained"""
while True:
    d = pollardPMO(num)
    """ adding the prime number to the result array """
    res.append(d)
    """ exhausting the provided number """
    r = int(num / d)
    """ primality check """
    if isprime(r):
        """inserting the prime factor"""
        res.append(r)
        break
    else:
        num = r

print("Factors of the number:", n, "are", *res)

Output

output

Also Read - Kadanes Algorithm

Frequently Asked Questions

What is the use case of the pollard p-1 algorithm?

The Pollard p-1 algorithm is an excellent method for determining the prime factors of any integer.

What are some prerequisites to understanding the pollard p-1 algorithm?

Knowledge of GCD and modular exponentiation is helpful in understanding 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

In this article, we looked into the pollard p-1 algorithm, and we also covered some pre-requisite like the modular exponentiation and greatest common divisor.

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!

Live masterclass