C++ Program to Perform Fermat Primality Test

This C++ Program demonstrates the implementation of Fermat Primality Test.

Here is source code of the C++ Program to demonstrate the implementation of Fermat Primality Test. The C++ program is successfully compiled and run on a Linux system. The program output is also shown below.

  1. /* 
  2.  * C++ Program to Implement Fermat Primality Test
  3.  */
  4. #include <cstring>
  5. #include <iostream>
  6. #include <cstdlib>
  7. #define ll long long
  8. using namespace std;
  9. /* 
  10.  * modular exponentiation
  11.  */
  12. ll modulo(ll base, ll exponent, ll mod)
  13. {
  14.     ll x = 1;
  15.     ll y = base;
  16.     while (exponent > 0)
  17.     {
  18.         if (exponent % 2 == 1)
  19.             x = (x * y) % mod;
  20.         y = (y * y) % mod;
  21.         exponent = exponent / 2;
  22.     }
  23.     return x % mod;
  24. }
  25.  
  26. /* 
  27.  * Fermat's test for checking primality 
  28.  */
  29. bool Fermat(ll p, int iterations)
  30. {
  31.     if (p == 1)
  32.     {
  33.         return false;
  34.     }
  35.     for (int i = 0; i < iterations; i++)
  36.     {
  37.         ll a = rand() % (p - 1) + 1; 
  38.         if (modulo(a, p - 1, p) != 1)
  39.         { 
  40.             return false;
  41.         }
  42.     }
  43.     return true;
  44. }
  45. /* 
  46.  * Main
  47.  */
  48. int main()
  49. {
  50.     int iteration = 50;
  51.     ll num;
  52.     cout<<"Enter integer to test primality: ";
  53.     cin>>num;
  54.     if (Fermat(num, iteration))
  55.         cout<<num<<" is prime"<<endl;
  56.     else
  57.         cout<<num<<" is not prime"<<endl;
  58.     return 0;
  59. }

$ g++ fermat_primality.cpp
$ a.out
 
Enter integer to test primality: 479001599
479001599 is prime
 
------------------
(program exited with code: 1)
Press return to continue

Sanfoundry Global Education & Learning Series – 1000 C++ Programs.

advertisement
advertisement
If you wish to look at all C++ Programming examples, go to C++ 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.