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 = a

^{2}– b^{2}. 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);

`}`

`}`

Fermat Factorization Test Enter odd number 5959 Roots = 59 , 101 Fermat Factorization Test Enter odd number 432633 Roots = 499 , 867

**Sanfoundry Global Education & Learning Series – 1000 Java Programs.**

If you wish to look at all Java Programming examples, go to Java Programs.