Java Program to Implement Fermat Factorization Algorithm

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:

Java Program to Implement HashTable API
Convert String to int or Integer in Java
Java Program to Find Location of a Point Placed in Three Dimensions Using K-D Trees
Java Perform to a 2D FFT Inplace Given a Complex 2D Array
Java Program to Implement ArrayDeque API
Java Program to Solve TSP Using Minimum Spanning Trees
Java Program to Check if a Given Binary Tree is an AVL Tree or Not
StringBuilder vs StringBuffer in Java
Map Serialization and Deserialization with Jackson
Spring Boot - Cloud Configuration Client
ExecutorService – Waiting for Threads to Finish
Java Scanner hasNext() vs. hasNextLine()
Java Program to Implement Double Order Traversal of a Binary Tree
Lớp TreeMap trong Java
Quick Intro to Spring Cloud Configuration
Java Program to Represent Graph Using Linked List
Tránh lỗi NullPointerException trong Java như thế nào?
Java Program to Compute DFT Coefficients Directly
How to Get All Dates Between Two Dates?
A Guide to Iterator in Java
Java Program to Check if a Given Set of Three Points Lie on a Single Line or Not
Java Program to Use Boruvka’s Algorithm to Find the Minimum Spanning Tree
Spring REST with a Zuul Proxy
Default Password Encoder in Spring Security 5
Java Switch Statement
Spring Cloud AWS – Messaging Support
Một số tính năng mới về xử lý ngoại lệ trong Java 7
Static Content in Spring WebFlux
Java – Write an InputStream to a File
Java InputStream to Byte Array and ByteBuffer
Java Program to Implement Segment Tree
Hướng dẫn Java Design Pattern – Bridge