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:
How to Get All Spring-Managed Beans?
REST Pagination in Spring
Configure a RestTemplate with RestTemplateBuilder
Giới thiệu HATEOAS
The Spring @Controller and @RestController Annotations
HTTP Authentification and CGI/Servlet
Hướng dẫn sử dụng Java String, StringBuffer và StringBuilder
Java Program to Implement Binomial Heap
Spring Security Registration – Resend Verification Email
Hướng dẫn Java Design Pattern – Interpreter
Jackson Annotation Examples
Java Program to Implement Sorted List
Java Program to Implement Graph Coloring Algorithm
Tổng quan về ngôn ngữ lập trình java
Quick Guide to Spring Controllers
Java Program to Implement Binomial Tree
How To Serialize and Deserialize Enums with Jackson
Migrating from JUnit 4 to JUnit 5
Adding Shutdown Hooks for JVM Applications
REST Web service: Tạo ứng dụng Java RESTful Client với Jersey Client 2.x
Java Program to Implement Quick sort
Anonymous Classes in Java
Java Program to Find Maximum Element in an Array using Binary Search
Properties with Spring and Spring Boot
Receive email using IMAP
Merging Streams in Java
Generating Random Dates in Java
Spring Boot - Enabling Swagger2
Optional trong Java 8
Java Program to Implement Stack using Linked List
New Features in Java 15
Wiring in Spring: @Autowired, @Resource and @Inject