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














































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:

Comments