# 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.

1. `/**`
2. ` ** Java Program to implement Fermat Factorization Algorithm`
3. ` **/`
4. ` `
5. `import java.util.Scanner;`
6. ` `
7. `public class FermatFactorization`
8. `{`
9. `    /** Fermat factor **/`
10. `    public void FermatFactor(long N)`
11. `    {`
12. `        long a = (long) Math.ceil(Math.sqrt(N));`
13. `        long b2 = a * a - N;`
14. `        while (!isSquare(b2))`
15. `        {`
16. `            a++;`
17. `            b2 = a * a - N;`
18. `        }`
19. `        long r1 = a - (long)Math.sqrt(b2);`
20. `        long r2 = N / r1;`
21. `        display(r1, r2);`
22. `    }`
23. `    /** function to display roots **/`
24. `    public void display(long r1, long r2)`
25. `    {`
26. `        System.out.println("\nRoots = "+ r1 +" , "+ r2);    `
27. `    }`
28. `    /** function to check if N is a perfect square or not **/`
29. `    public boolean isSquare(long N)`
30. `    {`
31. `        long sqr = (long) Math.sqrt(N);`
32. `        if (sqr * sqr == N || (sqr + 1) * (sqr + 1) == N)`
33. `            return true;`
34. `        return false;`
35. `    }`
36. `    /** main method **/`
37. `    public static void main(String[] args) `
38. `    {`
39. `        Scanner scan = new Scanner(System.in);`
40. `        System.out.println("Fermat Factorization Test\n");`
41. `        System.out.println("Enter odd number");`
42. `        long N = scan.nextLong();`
43. `        FermatFactorization ff = new FermatFactorization();`
44. `        ff.FermatFactor(N);`
45. `    }`
46. `}`

```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.

Note: Join free Sanfoundry classes at Telegram or Youtube 