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)
	{
		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

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







© 2021, kalkicode.com, All rights reserved