Skip to main content

Pollard's rho algorithm

Pollard's rho algorithm is a probabilistic algorithm for integer factorization, which was developed by mathematician John Pollard in 1975. The algorithm is based on the birthday paradox and uses random walks on the integer factorization lattice to find a non-trivial factor of a composite integer.

The basic idea of the algorithm is to generate a sequence of numbers using a recurrence relation, where the sequence forms a random walk on the factorization lattice. As the random walk progresses, it is likely to encounter a cycle, which corresponds to a non-trivial factor of the original number.

There are various versions of the algorithm, including the original "rho" version, as well as "p-1" and "p+1" variants. These variants employ different strategies to increase the likelihood of finding a non-trivial factor, such as using modular arithmetic and sieving.

While Pollard's rho algorithm is not guaranteed to find a non-trivial factor for all composite integers, it is generally efficient for integers with small factors. It has been used in practice to factor integers with hundreds of decimal digits, and is considered one of the most powerful algorithms for integer factorization.

Here given code implementation process.

// Java program for
// Pollard's rho algorithm
public class Factorization
{
	// Returns a GCD of given value
	public int gcd(int a, int b)
	{
		int remainder = 0;
		while (b != 0)
		{
			remainder = a % b;
			a = b;
			b = remainder;
		}
		return a;
	}
	public void findFactor(int num)
	{
		int result = -1;
		if (num <= 1)
		{
			result = 0;
		}
		else if (num % 2 == 0)
		{
			// When number is divisible by 2
			result = 2;
		}
		else
		{
			int auxiliary = 2, x = 2, size = 2, factor = 1, count;
			while (factor == 1)
			{
				count = size;
				while (count > 0 && factor == 1)
				{
					x = (x * x + 1) % num;
					factor = gcd(Math.abs(x - auxiliary), num);
					count--;
				}
				size *= 2;
				auxiliary = x;
			}
			result = factor;
		}
		System.out.println("Given num : " + num);
		if (result == 0)
		{
			System.out.println(" None ");
		}
		else
		{
			System.out.println(" One of factor is : " + result);
		}
	}
	public static void main(String[] args)
	{
		Factorization task = new Factorization();
		// Test
		task.findFactor(10403);
		task.findFactor(433);
		task.findFactor(57);
		task.findFactor(215);
	}
}

Output

Given num : 10403
 One of factor is : 101
Given num : 433
 One of factor is : 433
Given num : 57
 One of factor is : 3
Given num : 215
 One of factor is : 5
// Include header file
#include <iostream>
#include <math.h>
using namespace std;
// C++ program for
// Pollard's rho algorithm
class Factorization
{
	public:
		// Returns a GCD of given value
		int gcd(int a, int b)
		{
			int remainder = 0;
			while (b != 0)
			{
				remainder = a % b;
				a = b;
				b = remainder;
			}
			return a;
		}
	void findFactor(int num)
	{
		int result = -1;
		if (num <= 1)
		{
			result = 0;
		}
		else if (num % 2 == 0)
		{
			// When number is divisible by 2
			result = 2;
		}
		else
		{
			int auxiliary = 2;
			int x = 2;
			int size = 2;
			int factor = 1;
			int count;
			while (factor == 1)
			{
				count = size;
				while (count > 0 && factor == 1)
				{
					x = (x *x + 1) % num;
					factor = this->gcd(abs(x - auxiliary), num);
					count--;
				}
				size *= 2;
				auxiliary = x;
			}
			result = factor;
		}
		cout << "Given num : " 
             << num << endl;
		if (result == 0)
		{
			cout << " None " << endl;
		}
		else
		{
			cout << " One of factor is : " 
                 << result << endl;
		}
	}
};
int main()
{
	Factorization *task = new Factorization();
	// Test
	task->findFactor(10403);
	task->findFactor(433);
	task->findFactor(57);
	task->findFactor(215);
	return 0;
}

Output

Given num : 10403
 One of factor is : 101
Given num : 433
 One of factor is : 433
Given num : 57
 One of factor is : 3
Given num : 215
 One of factor is : 5
// Include namespace system
using System;
// Csharp program for
// Pollard's rho algorithm
public class Factorization
{
	// Returns a GCD of given value
	public int gcd(int a, int b)
	{
		int remainder = 0;
		while (b != 0)
		{
			remainder = a % b;
			a = b;
			b = remainder;
		}
		return a;
	}
	public void findFactor(int num)
	{
		int result = -1;
		if (num <= 1)
		{
			result = 0;
		}
		else if (num % 2 == 0)
		{
			// When number is divisible by 2
			result = 2;
		}
		else
		{
			int auxiliary = 2;
			int x = 2;
			int size = 2;
			int factor = 1;
			int count;
			while (factor == 1)
			{
				count = size;
				while (count > 0 && factor == 1)
				{
					x = (x * x + 1) % num;
					factor = this.gcd(Math.Abs(x - auxiliary), num);
					count--;
				}
				size *= 2;
				auxiliary = x;
			}
			result = factor;
		}
		Console.WriteLine("Given num : " + num);
		if (result == 0)
		{
			Console.WriteLine(" None ");
		}
		else
		{
			Console.WriteLine(" One of factor is : " + result);
		}
	}
	public static void Main(String[] args)
	{
		Factorization task = new Factorization();
		// Test
		task.findFactor(10403);
		task.findFactor(433);
		task.findFactor(57);
		task.findFactor(215);
	}
}

Output

Given num : 10403
 One of factor is : 101
Given num : 433
 One of factor is : 433
Given num : 57
 One of factor is : 3
Given num : 215
 One of factor is : 5
package main
import "math"
import "fmt"
// Go program for
// Pollard's rho algorithm
type Factorization struct {}
func getFactorization() * Factorization {
	var me *Factorization = &Factorization {}
	return me
}
// Returns a GCD of given value
func(this Factorization) gcd(a, b int) int {
	var remainder int = 0
	for (b != 0) {
		remainder = a % b
		a = b
		b = remainder
	}
	return a
}
func(this Factorization) findFactor(num int) {
	var result int = -1
	if num <= 1 {
		result = 0
	} else if num % 2 == 0 {
		// When number is divisible by 2
		result = 2
	} else {
		var auxiliary int = 2
		var x int = 2
		var size int = 2
		var factor int = 1
		var count int
		for (factor == 1) {
			count = size
			for (count > 0 && factor == 1) {
				x = (x * x + 1) % num
				factor = this.gcd(
					int(math.Abs(float64(x - auxiliary))), num)
				count--
			}
			size *= 2
			auxiliary = x
		}
		result = factor
	}
	fmt.Println("Given num : ", num)
	if result == 0 {
		fmt.Println(" None ")
	} else {
		fmt.Println(" One of factor is : ", result)
	}
}
func main() {
	var task * Factorization = getFactorization()
	// Test
	task.findFactor(10403)
	task.findFactor(433)
	task.findFactor(57)
	task.findFactor(215)
}

Output

Given num : 10403
 One of factor is : 101
Given num : 433
 One of factor is : 433
Given num : 57
 One of factor is : 3
Given num : 215
 One of factor is : 5
<?php
// Php program for
// Pollard's rho algorithm
class Factorization
{
	// Returns a GCD of given value
	public	function gcd($a, $b)
	{
		$remainder = 0;
		while ($b != 0)
		{
			$remainder = $a % $b;
			$a = $b;
			$b = $remainder;
		}
		return $a;
	}
	public	function findFactor($num)
	{
		$result = -1;
		if ($num <= 1)
		{
			$result = 0;
		}
		else if ($num % 2 == 0)
		{
			// When number is divisible by 2
			$result = 2;
		}
		else
		{
			$auxiliary = 2;
			$x = 2;
			$size = 2;
			$factor = 1;
			$count;
			while ($factor == 1)
			{
				$count = $size;
				while ($count > 0 && $factor == 1)
				{
					$x = ($x * $x + 1) % $num;
					$factor = $this->gcd(abs($x - $auxiliary), $num);
					$count--;
				}
				$size *= 2;
				$auxiliary = $x;
			}
			$result = $factor;
		}
		echo("Given num : ".$num."\n");
		if ($result == 0)
		{
			echo(" None \n");
		}
		else
		{
			echo(" One of factor is : ".$result."\n");
		}
	}
}

function main()
{
	$task = new Factorization();
	// Test
	$task->findFactor(10403);
	$task->findFactor(433);
	$task->findFactor(57);
	$task->findFactor(215);
}
main();

Output

Given num : 10403
 One of factor is : 101
Given num : 433
 One of factor is : 433
Given num : 57
 One of factor is : 3
Given num : 215
 One of factor is : 5
// Node JS program for
// Pollard's rho algorithm
class Factorization
{
	// Returns a GCD of given value
	gcd(a, b)
	{
		var remainder = 0;
		while (b != 0)
		{
			remainder = a % b;
			a = b;
			b = remainder;
		}
		return a;
	}
	findFactor(num)
	{
		var result = -1;
		if (num <= 1)
		{
			result = 0;
		}
		else if (num % 2 == 0)
		{
			// When number is divisible by 2
			result = 2;
		}
		else
		{
			var auxiliary = 2;
			var x = 2;
			var size = 2;
			var factor = 1;
			while (factor == 1)
			{
				var count = size;
				while (count > 0 && factor == 1)
				{
					x = (x * x + 1) % num;
					factor = this.gcd(Math.abs(x - auxiliary), num);
					count--;
				}
				size *= 2;
				auxiliary = x;
			}
			result = factor;
		}
		console.log("Given num : " + num);
		if (result == 0)
		{
			console.log(" None ");
		}
		else
		{
			console.log(" One of factor is : " + result);
		}
	}
}

function main()
{
	var task = new Factorization();
	// Test
	task.findFactor(10403);
	task.findFactor(433);
	task.findFactor(57);
	task.findFactor(215);
}
main();

Output

Given num : 10403
 One of factor is : 101
Given num : 433
 One of factor is : 433
Given num : 57
 One of factor is : 3
Given num : 215
 One of factor is : 5
import math
#  Python 3 program for
#  Pollard's rho algorithm
class Factorization :
	#  Returns a GCD of given value
	def gcd(self, a, b) :
		remainder = 0
		while (b != 0) :
			remainder = a % b
			a = b
			b = remainder
		
		return a
	
	def findFactor(self, num) :
		result = -1
		if (num <= 1) :
			result = 0
		elif (num % 2 == 0) :
			#  When number is divisible by 2
			result = 2
		else :
			auxiliary = 2
			x = 2
			size = 2
			factor = 1
			while (factor == 1) :
				count = size
				while (count > 0 and factor == 1) :
					x = (x * x + 1) % num
					factor = self.gcd(abs(x - auxiliary), num)
					count -= 1
				
				size *= 2
				auxiliary = x
			
			result = factor
		
		print("Given num : ", num)
		if (result == 0) :
			print(" None ")
		else :
			print(" One of factor is : ", result)
		
	

def main() :
	task = Factorization()
	#  Test
	task.findFactor(10403)
	task.findFactor(433)
	task.findFactor(57)
	task.findFactor(215)

if __name__ == "__main__": main()

Output

Given num :  10403
 One of factor is :  101
Given num :  433
 One of factor is :  433
Given num :  57
 One of factor is :  3
Given num :  215
 One of factor is :  5
#  Ruby program for
#  Pollard's rho algorithm
class Factorization 
	#  Returns a GCD of given value
	def gcd(a, b) 
		remainder = 0
		while (b != 0) 
			remainder = a % b
			a = b
			b = remainder
		end

		return a
	end

	def findFactor(num) 
		result = -1
		if (num <= 1) 
			result = 0
		elsif (num % 2 == 0) 
			#  When number is divisible by 2
			result = 2
		else
 
			auxiliary = 2
			x = 2
			size = 2
			factor = 1
			while (factor == 1) 
				count = size
				while (count > 0 && factor == 1) 
					x = (x * x + 1) % num
					factor = self.gcd((x - auxiliary).abs, num)
					count -= 1
				end

				size *= 2
				auxiliary = x
			end

			result = factor
		end

		print("Given num : ", num, "\n")
		if (result == 0) 
			print(" None ", "\n")
		else
 
			print(" One of factor is : ", result, "\n")
		end

	end

end

def main() 
	task = Factorization.new()
	#  Test
	task.findFactor(10403)
	task.findFactor(433)
	task.findFactor(57)
	task.findFactor(215)
end

main()

Output

Given num : 10403
 One of factor is : 101
Given num : 433
 One of factor is : 433
Given num : 57
 One of factor is : 3
Given num : 215
 One of factor is : 5

// Scala program for
// Pollard's rho algorithm
class Factorization()
{
	// Returns a GCD of given value
	def gcd(n1: Int, n2: Int): Int = {
		var remainder: Int = 0;
      	var a = n1;
      	var b = n2;
		while (b != 0)
		{
			remainder = a % b;
			a = b;
			b = remainder;
		}
		return a;
	}
	def findFactor(num: Int): Unit = {
		var result: Int = -1;
		if (num <= 1)
		{
			result = 0;
		}
		else if (num % 2 == 0)
		{
			// When number is divisible by 2
			result = 2;
		}
		else
		{
			var auxiliary: Int = 2;
			var x: Int = 2;
			var size: Int = 2;
			var factor: Int = 1;
			var count: Int = 0;
			while (factor == 1)
			{
				count = size;
				while (count > 0 && factor == 1)
				{
					x = (x * x + 1) % num;
					factor = gcd(Math.abs(x - auxiliary), num);
					count -= 1;
				}
				size *= 2;
				auxiliary = x;
			}
			result = factor;
		}
		println("Given num : " + num);
		if (result == 0)
		{
			println(" None ");
		}
		else
		{
			println(" One of factor is : " + result);
		}
	}
}
object Main
{
	def main(args: Array[String]): Unit = {
		var task: Factorization = new Factorization();
		// Test
		task.findFactor(10403);
		task.findFactor(433);
		task.findFactor(57);
		task.findFactor(215);
	}
}

Output

Given num : 10403
 One of factor is : 101
Given num : 433
 One of factor is : 433
Given num : 57
 One of factor is : 3
Given num : 215
 One of factor is : 5
import Foundation;
// Swift 4 program for
// Pollard's rho algorithm
class Factorization
{
	// Returns a GCD of given value
	func gcd(_ n1: Int, _ n2: Int) -> Int
	{
		var remainder: Int = 0;
      	var a = n1;
      	var b = n2;
		while (b  != 0)
		{
			remainder = a % b;
			a = b;
			b = remainder;
		}
		return a;
	}
	func findFactor(_ num: Int)
	{
		var result: Int = -1;
		if (num <= 1)
		{
			result = 0;
		}
		else if (num % 2 == 0)
		{
			// When number is divisible by 2
			result = 2;
		}
		else
		{
			var auxiliary: Int = 2;
			var x: Int = 2;
			var size: Int = 2;
			var factor: Int = 1;
			var count: Int;
			while (factor == 1)
			{
				count = size;
				while (count > 0 && factor == 1)
				{
					x = (x * x + 1) % num;
					factor = self.gcd(abs(x - auxiliary), num);
					count -= 1;
				}
				size *= 2;
				auxiliary = x;
			}
			result = factor;
		}
		print("Given num : ", num);
		if (result == 0)
		{
			print(" None ");
		}
		else
		{
			print(" One of factor is : ", result);
		}
	}
}
func main()
{
	let task: Factorization = Factorization();
	// Test
	task.findFactor(10403);
	task.findFactor(433);
	task.findFactor(57);
	task.findFactor(215);
}
main();

Output

Given num :  10403
 One of factor is :  101
Given num :  433
 One of factor is :  433
Given num :  57
 One of factor is :  3
Given num :  215
 One of factor is :  5
// Kotlin program for
// Pollard's rho algorithm
class Factorization
{
	// Returns a GCD of given value
	fun gcd(n1: Int, n2: Int): Int
	{
		var remainder: Int ;
      	var a = n1;
        var b = n2;
		while (b != 0)
		{
			remainder = a % b;
			a = b;
			b = remainder;
		}
		return a;
	}
	fun findFactor(num: Int): Unit
	{
		var result: Int ;
		if (num <= 1)
		{
			result = 0;
		}
		else if (num % 2 == 0)
		{
			// When number is divisible by 2
			result = 2;
		}
		else
		{
			var auxiliary: Int = 2;
			var x: Int = 2;
			var size: Int = 2;
			var factor: Int = 1;
			var count: Int;
			while (factor == 1)
			{
				count = size;
				while (count > 0 && factor == 1)
				{
					x = (x * x + 1) % num;
					factor = this.gcd(Math.abs(x - auxiliary), num);
					count -= 1;
				}
				size *= 2;
				auxiliary = x;
			}
			result = factor;
		}
		println("Given num : " + num);
		if (result == 0)
		{
			println(" None ");
		}
		else
		{
			println(" One of factor is : " + result);
		}
	}
}
fun main(args: Array < String > ): Unit
{
	val task: Factorization = Factorization();
	// Test
	task.findFactor(10403);
	task.findFactor(433);
	task.findFactor(57);
	task.findFactor(215);
}

Output

Given num : 10403
 One of factor is : 101
Given num : 433
 One of factor is : 433
Given num : 57
 One of factor is : 3
Given num : 215
 One of factor is : 5
Last updated on by Kalkicode




Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

New Comment