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.

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

If you find any mistake above, kindly email to [email protected]

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & discussions at Telegram SanfoundryClasses.