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:
Tạo ứng dụng Java RESTful Client không sử dụng 3rd party libraries
Java Program to do a Depth First Search/Traversal on a graph non-recursively
The Spring @Controller and @RestController Annotations
Lớp Properties trong java
How to Find an Element in a List with Java
Mệnh đề Switch-case trong java
Guide to ThreadLocalRandom in Java
Format ZonedDateTime to String
A Guide to TreeSet in Java
Hướng dẫn Java Design Pattern – Strategy
Java – Random Long, Float, Integer and Double
Removing all Nulls from a List in Java
JUnit5 @RunWith
Java Program to Implement Gauss Jordan Elimination
Spring Data JPA and Null Parameters
Java Program to Implement LinkedHashSet API
The Thread.join() Method in Java
Check If Two Lists are Equal in Java
Java Program to Implement Sieve Of Atkin
Java Program to Implement Binary Heap
Java Program to Implement Find all Forward Edges in a Graph
Guide to @JsonFormat in Jackson
Hướng dẫn Java Design Pattern – Flyweight
Java Program to Implement Double Order Traversal of a Binary Tree
Reactive Flow with MongoDB, Kotlin, and Spring WebFlux
String Joiner trong Java 8
Java Program to Implement Sorted Doubly Linked List
New Features in Java 12
Batch Processing with Spring Cloud Data Flow
Sử dụng Fork/Join Framework với ForkJoinPool trong Java
Hamcrest Collections Cookbook
Java Program to Check if a Directed Graph is a Tree or Not Using DFS