# Pollard's rho algorithm

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.