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:
Disable DNS caching
Java Program to Print the Kind of Rotation the AVL Tree is Undergoing
Java 8 Collectors toMap
Hướng dẫn Java Design Pattern – Abstract Factory
Java Program to Perform Naive String Matching
Java Program to Implement Sorted List
Remove the First Element from a List
Giới thiệu Design Patterns
Java Program to Generate All Subsets of a Given Set in the Lexico Graphic Order
Java Program to Use Above Below Primitive to Test Whether Two Lines Intersect
Java Program to Check if a Given Graph Contain Hamiltonian Cycle or Not
Java Program to Compute Discrete Fourier Transform Using the Fast Fourier Transform Approach
Java Program to Solve Travelling Salesman Problem for Unweighted Graph
Spring Boot With H2 Database
Spring Security OAuth Login with WebFlux
Quản lý bộ nhớ trong Java với Heap Space vs Stack
Java Program to Implement Gauss Jordan Elimination
Spring Security 5 for Reactive Applications
Java Program to Implement Cartesian Tree
Using Java Assertions
Biến trong java
The StackOverflowError in Java
Java – Reader to InputStream
Hướng dẫn Java Design Pattern – Facade
Intro to Spring Boot Starters
Java Program to Implement Sorted Array
LinkedHashSet trong java
Tạo ứng dụng Java RESTful Client với thư viện OkHttp
Java Program to Test Using DFS Whether a Directed Graph is Strongly Connected or Not
Call Methods at Runtime Using Java Reflection
Java 9 Stream API Improvements
How to Change the Default Port in Spring Boot