In this program, we are going to share how to write a program to implement Miller Rabin Primality Test. If you are a beginner and want to start learning the C++ programming, then keep your close attention in this tutorial as I am going to share a program for How to Write a Program to Implement Miller Rabin Primality Test.
Copy the below C++ program and execute it with the help of GCC compiler. At the end of this program, We have shared the output of this program.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 | #include <iostream> #include <cstring> #include <cstdlib> #define ll long long using namespace std; ll mulmod(ll a, ll b, ll mod) { ll x = 0,y = a % mod; while (b > 0) { if (b % 2 == 1) { x = (x + y) % mod; } y = (y * 2) % mod; b /= 2; } return x % mod; } /* * modular exponentiation */ ll modulo(ll base, ll exponent, ll mod) { ll x = 1; ll y = base; while (exponent > 0) { if (exponent % 2 == 1) x = (x * y) % mod; y = (y * y) % mod; exponent = exponent / 2; } return x % mod; } /* * Miller-Rabin primality test, iteration signifies the accuracy */ bool Miller(ll p,int iteration) { if (p < 2) { return false; } if (p != 2 && p % 2==0) { return false; } ll s = p - 1; while (s % 2 == 0) { s /= 2; } for (int i = 0; i < iteration; i++) { ll a = rand() % (p - 1) + 1, temp = s; ll mod = modulo(a, temp, p); while (temp != p - 1 && mod != 1 && mod != p - 1) { mod = mulmod(mod, mod, p); temp *= 2; } if (mod != p - 1 && temp % 2 == 0) { return false; } } return true; } //Main int main() { int iteration = 5; ll num; cout<<"Enter integer to test primality: "; cin>>num; if (Miller(num, iteration)) cout<<num<<" is prime"<<endl; else cout<<num<<" is not prime"<<endl; return 0; } |
Enter integer to test primality: 127
127 is prime
