This is a Java Program to Implement Fermat Factorization Algorithm. Fermat’s factorization method, named after Pierre de Fermat, is based on the representation of an odd integer as the difference of two squares: N = a2 – b2. That difference is algebraically factorable as (a + b)(a – b); if neither factor equals one, it is a proper factorization of N.
Here is the source code of the Java Program to Implement Fermat Factorization Algorithm. The Java program is successfully compiled and run on a Windows system. The program output is also shown below.
/** ** Java Program to implement Fermat Factorization Algorithm **/ import java.util.Scanner; public class FermatFactorization { /** Fermat factor **/ public void FermatFactor(long N) { long a = (long) Math.ceil(Math.sqrt(N)); long b2 = a * a - N; while (!isSquare(b2)) { a++; b2 = a * a - N; } long r1 = a - (long)Math.sqrt(b2); long r2 = N / r1; display(r1, r2); } /** function to display roots **/ public void display(long r1, long r2) { System.out.println("\nRoots = "+ r1 +" , "+ r2); } /** function to check if N is a perfect square or not **/ public boolean isSquare(long N) { long sqr = (long) Math.sqrt(N); if (sqr * sqr == N || (sqr + 1) * (sqr + 1) == N) return true; return false; } /** main method **/ public static void main(String[] args) { Scanner scan = new Scanner(System.in); System.out.println("Fermat Factorization Test\n"); System.out.println("Enter odd number"); long N = scan.nextLong(); FermatFactorization ff = new FermatFactorization(); ff.FermatFactor(N); } }
Output:
Fermat Factorization Test Enter odd number 5959 Roots = 59 , 101 Fermat Factorization Test Enter odd number 432633 Roots = 499 , 867
Related posts:
Spring Boot - Application Properties
Spring Boot - Service Components
Java Timer
Reactive WebSockets with Spring 5
Spring Boot - Admin Client
How To Serialize and Deserialize Enums with Jackson
Spring REST API + OAuth2 + Angular (using the Spring Security OAuth legacy stack)
Java Program to Implement the Vigenere Cypher
Java Program for Topological Sorting in Graphs
Wrapper Classes in Java
A Quick Guide to Spring Cloud Consul
Java Program to Implement Treap
Introduction to Spring Cloud OpenFeign
Java Program to Implement the Schonhage-Strassen Algorithm for Multiplication of Two Numbers
Java Program to Implement Sieve Of Sundaram
Introduction to Netflix Archaius with Spring Cloud
Converting Between Byte Arrays and Hexadecimal Strings in Java
Java Program to Implement Bucket Sort
Adding Parameters to HttpClient Requests
Handling URL Encoded Form Data in Spring REST
CyclicBarrier in Java
Java Program to Find Hamiltonian Cycle in an UnWeighted Graph
Get the workstation name or IP
Java Program to find the maximum subarray sum using Binary Search approach
Map Interface trong java
Java Program to Implement a Binary Search Tree using Linked Lists
Java Program to Compute DFT Coefficients Directly
Transactions with Spring and JPA
Java Program to Implement IdentityHashMap API
Java Program to Perform Searching in a 2-Dimension K-D Tree
Getting Started with Forms in Spring MVC
Java Program to Perform Stooge Sort