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 = a² – b². 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.

« Prev - Java Program to Implement Nth Root Algorithm

» Next - Java Program to Implement Stein GCD Algorithm

Related Posts:

Recommended Articles: