C++ Program to Implement Miller Rabin Primality Test

This C++ Program demonstrates the implementation of Miller Rabin Primality Test.

Here is source code of the C++ Program to demonstrate the implementation of Miller Rabin 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 Miller Rabin Primality Test
  3.  */
  4. #include <iostream>
  5. #include <cstring>
  6. #include <cstdlib>
  7. #define ll long long
  8. using namespace std;
  9.  
  10. /* 
  11.  * calculates (a * b) % c taking into account that a * b might overflow 
  12.  */
  13. ll mulmod(ll a, ll b, ll mod)
  14. {
  15.     ll x = 0,y = a % mod;
  16.     while (b > 0)
  17.     {
  18.         if (b % 2 == 1)
  19.         {    
  20.             x = (x + y) % mod;
  21.         }
  22.         y = (y * 2) % mod;
  23.         b /= 2;
  24.     }
  25.     return x % mod;
  26. }
  27. /* 
  28.  * modular exponentiation
  29.  */
  30. ll modulo(ll base, ll exponent, ll mod)
  31. {
  32.     ll x = 1;
  33.     ll y = base;
  34.     while (exponent > 0)
  35.     {
  36.         if (exponent % 2 == 1)
  37.             x = (x * y) % mod;
  38.         y = (y * y) % mod;
  39.         exponent = exponent / 2;
  40.     }
  41.     return x % mod;
  42. }
  43.  
  44. /*
  45.  * Miller-Rabin primality test, iteration signifies the accuracy
  46.  */
  47. bool Miller(ll p,int iteration)
  48. {
  49.     if (p < 2)
  50.     {
  51.         return false;
  52.     }
  53.     if (p != 2 && p % 2==0)
  54.     {
  55.         return false;
  56.     }
  57.     ll s = p - 1;
  58.     while (s % 2 == 0)
  59.     {
  60.         s /= 2;
  61.     }
  62.     for (int i = 0; i < iteration; i++)
  63.     {
  64.         ll a = rand() % (p - 1) + 1, temp = s;
  65.         ll mod = modulo(a, temp, p);
  66.         while (temp != p - 1 && mod != 1 && mod != p - 1)
  67.         {
  68.             mod = mulmod(mod, mod, p);
  69.             temp *= 2;
  70.         }
  71.         if (mod != p - 1 && temp % 2 == 0)
  72.         {
  73.             return false;
  74.         }
  75.     }
  76.     return true;
  77. }
  78. //Main
  79. int main()
  80. {
  81.     int iteration = 5;
  82.     ll num;
  83.     cout<<"Enter integer to test primality: ";
  84.     cin>>num;
  85.     if (Miller(num, iteration))
  86.         cout<<num<<" is prime"<<endl;
  87.     else
  88.         cout<<num<<" is not prime"<<endl;
  89.     return 0;
  90. }

$ g++ miller_rabin.cpp
$ a.out
 
Enter integer to test primality: 127
127 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.