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