Java Program to Implement Pollard Rho Algorithm

This is a Java Program to Implement Pollard Rho Algorithm. Pollard Rho algorithm is a general purpose factorization algorithm. It is particularly effective at splitting composite numbers with small factors.

Here is the source code of the Java Program to Implement Pollard Rho Algorithm. The Java program is successfully compiled and run on a Windows system. The program output is also shown below.

/**
 ** Java Program to implement Pollard Rho Algorithm
 **/
 
import java.util.Scanner;
 
/** Class PollardRho **/
public class PollardRho    
{
    private static final long C = 1; 
    /** function X * X + C, change value of C as required **/
    private long f(long X)    
    {
        return X * X + C;
    }
    /** get divisor **/
    private long rho(long N) 
    {
        long x1 = 2, x2 = 2, divisor;        
        if (N % 2 == 0) 
            return 2;
        do 
        {
            x1 = f(x1) % N;
            x2 = f(f(x2)) % N;
            divisor = gcd(Math.abs(x1 - x2), N);
        } while (divisor == 1);
        /** return divisor **/
        return divisor;
    }
    /** GCD of two numbers **/
    public  long gcd(long p, long q)
    {
        if (p % q == 0)
            return q;
        return gcd(q, p % q);
    }
    /** Check if num is prime **/
    public boolean isPrime(long N)
    {
        for (int i = 2; i <= Math.sqrt(N); i++)
            if (N % i == 0)
                return false;
        return true;
    }
    /** get all factors **/
    public void factor(long N) 
    {
        if (N == 1)
            return;
        if (isPrime(N)) 
        {
            System.out.println(N); 
            return; 
        }
           long divisor = rho(N);
        factor(divisor);
        factor(N / divisor);
    }
    /** Main function **/
    public static void main(String[] args)
    {
        Scanner scan = new Scanner(System.in);
        System.out.println("Pollard Rho Algorithm\n");                
        System.out.println("Enter a number");
        long N = scan.nextLong();
        System.out.println("\nFactors are : ");
        PollardRho pr = new PollardRho();
        pr.factor (N);        
    }
}

Output:

Pollard Rho Algorithm
 
Enter a number
2406
 
Factors are :
2
3
401

Related posts:

Guide to Spring Cloud Kubernetes
Java Program to Implement Sorted Circularly Singly Linked List
Java Program to Implement Insertion Sort
Java Program to Implement the RSA Algorithm
Quick Guide on Loading Initial Data with Spring Boot
Base64 encoding và decoding trong Java 8
How to Manually Authenticate User with Spring Security
Java Program to Describe the Representation of Graph using Adjacency Matrix
Assertions in JUnit 4 and JUnit 5
Java Program to Check if an UnDirected Graph is a Tree or Not Using DFS
Java Program to Represent Graph Using 2D Arrays
Java Program to Describe the Representation of Graph using Incidence List
Spring Boot - Application Properties
Java Program to Implement Hash Tables Chaining with Binary Trees
Java Program to Implement ArrayBlockingQueue API
Introduction to the Java NIO Selector
Exploring the Spring Boot TestRestTemplate
Java Program to Implement the Alexander Bogomolny’s UnOrdered Permutation Algorithm for Elements Fro...
Server-Sent Events in Spring
Spring Data Reactive Repositories with MongoDB
Refactoring Design Pattern với tính năng mới trong Java 8
Spring NoSuchBeanDefinitionException
Spring REST API + OAuth2 + Angular
Java Program to Construct an Expression Tree for an Infix Expression
Tổng quan về ngôn ngữ lập trình java
Creating a Web Application with Spring 5
Guide to Guava Table
Guide to UUID in Java
Java Program to Check Whether a Weak Link i.e. Articulation Vertex Exists in a Graph
Notify User of Login From New Device or Location
Hướng dẫn Java Design Pattern – Command
Java Program to implement Bit Set