# 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)
{
// Test
}
}``````

#### 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()
{
// Test
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)
{
// Test
}
}``````

#### 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
}``````

#### 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()
{
// Test
}
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()
{
// Test
}
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() :
#  Test

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()
#  Test
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
}
}``````

#### 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()
{
// Test
}
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
{
// Test
}``````

#### 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``````

## 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.