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:

Quick Intro to Spring Cloud Configuration
Java Program to Implement Range Tree
Java Program to Find Minimum Element in an Array using Linear Search
A Guide to Java HashMap
Các chương trình minh họa sử dụng Cấu trúc điều khiển trong Java
Java Program to Perform Left Rotation on a Binary Search Tree
Java Program to Implement K Way Merge Algorithm
Jackson – Change Name of Field
Sao chép các phần tử của một mảng sang mảng khác như thế nào?
Giới thiệu Java Service Provider Interface (SPI) – Tạo các ứng dụng Java dễ mở rộng
Java Program to Implement Sorted Vector
Java Program to Implement String Matching Using Vectors
Constructor Dependency Injection in Spring
Spring Security OAuth Login with WebFlux
Changing Annotation Parameters At Runtime
Java Web Services – JAX-WS – SOAP
Hướng dẫn sử dụng luồng vào ra ký tự trong Java
Spring Boot - Bootstrapping
How to Round a Number to N Decimal Places in Java
Guide to the Fork/Join Framework in Java
Hướng dẫn Java Design Pattern – Composite
Form Validation with AngularJS and Spring MVC
Java Program to Give an Implementation of the Traditional Chinese Postman Problem
Checking for Empty or Blank Strings in Java
Introduction to Project Reactor Bus
Java Program to Implement Bucket Sort
Java 8 Stream API Analogies in Kotlin
Returning Custom Status Codes from Spring Controllers
Extra Login Fields with Spring Security
Java Program to Implement Uniform-Cost Search
Guide To CompletableFuture
Java Program to Describe the Representation of Graph using Adjacency List