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:
Control Structures in Java
Fixing 401s with CORS Preflights and Spring Security
Mệnh đề if-else trong java
Java Program to Implement Find all Cross Edges in a Graph
Giới thiệu luồng vào ra (I/O) trong Java
Java Program to Check Whether Graph is DAG
Java Program to Generate All Pairs of Subsets Whose Union Make the Set
String Operations with Java Streams
Tính đa hình (Polymorphism) trong Java
How to Get a Name of a Method Being Executed?
Java Program to Implement the String Search Algorithm for Short Text Sizes
New Stream Collectors in Java 9
Java Program to Implement RoleList API
Mockito and JUnit 5 – Using ExtendWith
Java Program to Construct K-D Tree for 2 Dimensional Data
The Dining Philosophers Problem in Java
Spring REST with a Zuul Proxy
Java Program to Generate a Graph for a Given Fixed Degree Sequence
String Processing with Apache Commons Lang 3
Java Program to Decode a Message Encoded Using Playfair Cipher
Guide to ThreadLocalRandom in Java
Java TreeMap vs HashMap
Constructor Injection in Spring with Lombok
Spring Boot Annotations
Java Program to Implement Hash Tables with Linear Probing
Java Program to Implement Shell Sort
Java Program to Implement the MD5 Algorithm
Java Program to Construct an Expression Tree for an Infix Expression
Removing all duplicates from a List in Java
Guide to java.util.concurrent.BlockingQueue
Spring WebClient Requests with Parameters
Java Program to Implement Caesar Cypher