Java Program to Perform Fermat Primality Test

This is a Java Program to Implement Fermat Primality Test Algorithm. Fermat Primality Test is an algorithm which is used to determine if a given number is prime or not.

Here is the source code of the Java Program to Implement Fermat Primality Test 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 Primality Test Algorithm
  3.  **/
  4.  
  5. import java.util.Scanner;
  6. import java.util.Random;
  7.  
  8. /** Class FermatPrimality **/
  9. public class FermatPrimality
  10. {
  11.     /** Function to check if prime or not **/
  12.     public boolean isPrime(long n, int iteration)
  13.     {
  14.         /** base case **/
  15.         if (n == 0 || n == 1)
  16.             return false;
  17.         /** base case - 2 is prime **/
  18.         if (n == 2)
  19.             return true;
  20.         /** an even number other than 2 is composite **/
  21.         if (n % 2 == 0)
  22.             return false;
  23.  
  24.         Random rand = new Random();
  25.         for (int i = 0; i < iteration; i++)
  26.         {
  27.             long r = Math.abs(rand.nextLong());            
  28.             long a = r % (n - 1) + 1;
  29.             if (modPow(a, n - 1, n) != 1)
  30.                 return false;
  31.         }
  32.         return true;        
  33.     }
  34.     /** Function to calculate (a ^ b) % c **/
  35.     public long modPow(long a, long b, long c)
  36.     {
  37.         long res = 1;
  38.         for (int i = 0; i < b; i++)
  39.         {
  40.             res *= a;
  41.             res %= c; 
  42.         }
  43.         return res % c;
  44.     }    
  45.     /** Main function **/
  46.     public static void main (String[] args) 
  47.     {
  48.         Scanner scan = new Scanner(System.in);
  49.         System.out.println("Fermat Primality Algorithm Test\n");
  50.         /** Make an object of FermatPrimality class **/
  51.         FermatPrimality fp = new FermatPrimality();
  52.         /** Accept number **/
  53.         System.out.println("Enter number\n");
  54.         long num = scan.nextLong();
  55.         /** Accept number of iterations **/
  56.         System.out.println("\nEnter number of iterations");
  57.         int k = scan.nextInt();
  58.         /** check if prime **/
  59.         boolean prime = fp.isPrime(num, k);
  60.         if (prime)
  61.             System.out.println("\n"+ num +" is prime");
  62.         else
  63.             System.out.println("\n"+ num +" is composite");        
  64.     }
  65. }

Fermat Primality Algorithm Test
 
Enter number
 
999983
 
Enter number of iterations
2
 
999983 is prime

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.