Fermat Factorization method in Java

Here we will see about Fermat Factorization Method in Java.

Fermat Factorization method is based on the evaluation of an odd integer value as it differs from two squares. This was named after Pierre de Fermat. Let’s consider an integer N considering a and b such as-

N = a2 – b2 =(a+b)(a-b)

where (a+b) and (a-b) are the factors.

 

ALGORITHM

  1. Start
  2. Consider an integer N with its factorized two positive integers. Like, N is odd so both of x and y are odd such as-
    1. N=x*y
  3. Assume p = ½*(x+y) and q= ½*(y-x)
  4. Here p and q are both integers, then x=p-q and y=p+q.
  5. Finally, N = a2 – b2 =(a+b)(a-b)
  6. If it’s prime number then it goes until b=1 in as one factor is 1 for prime number.
  7. Loop operation will ensure this functionality.
  8. End

firstly, we import the necessary package and define a public class as shown bellow-

import java.util.*;
public class Fermat_Factorization

Secondly, we take user input of odd numbers and assign them with Fermat function to perform other operations.

public static void main(String[] args) 
   {
       Scanner in = new Scanner(System.in);    
       System.out.println("Enter any odd number");
       long n = in.nextLong();
       Fermat(n);
   }

Thirdly, we find the required factors calling them root1 and root2.

public static void FermatFactor(long n)
  {
      long a = (long) Math.ceil(Math.sqrt(n));
      long b = a * a - n;
      while (!isSquare(b))
      {
          a++;
          b = a * a - n;
      }
      long root1 = a - (long)Math.sqrt(b);
      long root2 = n / root1;
  }

Fourthly, this operation finds the square of the given number.

public static  boolean isSquare(long n)
   {
       long s = (long) Math.sqrt(n);
       if (s * s == n || (s + 1) * (s + 1) == n)
           return true;
       return false;
   }

finally, we print the final roots of the given number.

System.out.println("\nRoots = "+ root1 +" , "+ root2);
Output

Enter any odd number
6557
Roots = 79 , 83

Leave a Reply

Your email address will not be published. Required fields are marked *