 ### C++ Program to check prime using Miller Test (Probabilistic Version)

Discription:

`Using Miller-Rabin algorithm we can decide if a number is prime or not in O(k*(log2(n))3).`
`The running time of Miller-Rabin algorithm is far better than the naive solutions working in`
`O(n) or O(sqrt(n)).Main concepts involved are:`
`Fermat's Litte Theorem: a(n-1) == 1 (mod n) for any integer a and prime number n -- (1) Again suppose: x2 == 1 (mod n) x2-1 == 0 (mod n) (x-1)(x+1) == 0 (mod n) ---(2) from equation 2 we can say that n divides one of the factor either (x-1) or (x+1).`
` So if n divides (x-1) then x is congruent to 1 modulo n otherwise n divides (x+1) `
` and x is congruent to -1 modulo n x == 1 (mod n) or  x == -1 (mod n)`
` Now if we keep taking square roots of LHS of equation 1 then eventually we will get either -1 or 1 if n is probable prime  otherwise we can say that n is not prime. We call a as a witness for compositness of n. We will run this algorithm several times with different values of a and check if n is prime or not. If in any of the round  we find that n is not a prime then it's not prime otherwise it is probable prime. Maximum rounds in Miller-Rabin Algorithm insures maximum probablity for n to be prime.`

Program:
#include<iostream> #include<ctime> using namespace std; const int Rounds = 5; template<typename P> P powmod(P a, P e, P m) { P res = 1; while (e > 0) { if (e & 1) { res *= a; if (res >= m) res %= m; } e >>= 1; a *= a; if (a >= m) a %= m; } return res; } template<typename T> // templated to make sure long & int both works fine bool Miller_Rabin_Prime(T num) { // Handling base cases: if (num == 0) return false; if (num == 2) return true; if (num % 2 == 0) return false; // Now our num is odd number greater than 1 T d = num - 1; T r = 0; while (d % 2 == 0) { r++, d >>= 1; } // Now take a random integer between [2, n-2] as a for (int loop = 1; loop <= Rounds; loop++) { T a = 2 + rand() % (num - 3); T x = powmod(a, d, num); if (x == 1 || x == (num - 1)) continue; // check again using different a T i; for (i = 1; i < r; i++) { x = (x * x) % num; if (x == (num - 1))break; // Check again using different a } if(i == r)return false; // n is composite as no solution found for x using current a } return true; // n is probable prime } int main() { srand(time(NULL)); long long num = 97; if (Miller_Rabin_Prime(num)) cout << num << " is probable prime." << endl; else cout << num << " is a composite number." << endl; num = (long long)1e9 + 7; if (Miller_Rabin_Prime(num)) cout << num << " is probable prime." << endl; else cout << num << " is a composite number." << endl; num = 200; if (Miller_Rabin_Prime(num)) cout << num << " is probable prime." << endl; else cout << num << " is a composite number." << endl; return 0; }

Output:  