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.
/**
** 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.
advertisement
advertisement
If you wish to look at all Java Programming examples, go to Java Programs.
Next Steps:
- Get Free Certificate of Merit in Java Programming
- Participate in Java Programming Certification Contest
- Become a Top Ranker in Java Programming
- Take Java Programming Tests
- Chapterwise Practice Tests: Chapter 1, 2, 3, 4, 5, 6, 7, 8, 9, 10
- Chapterwise Mock Tests: Chapter 1, 2, 3, 4, 5, 6, 7, 8, 9, 10
Related Posts:
- Apply for Information Technology Internship
- Practice Information Technology MCQs
- Apply for Java Internship
- Buy Java Books
- Buy Programming Books