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














































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



Discription:

This article is in continuation of my previous article where we had to determine whether the 
given number is prime or not using Miller-Rabin Algorithm. As this is a Probability based Algorithm,
So it may fail for some cases although it is very rare. 
In this article we will talk about how we can determine if a number is prime or not using Miller-
Rabin Algorithm.Recall that in my last article for a number to composite we were checking it against 
base a. So, If some how we can decide how many bases we need to check for a number. Miller proved 
that for a number n upper bound of bases is a <= O((log2(n))2) , However this bound was loose and 
later Bach, gave a concrete upper bound as  a <= O(2*log2(n)2). So for numbers upto 64 bit It is fine
to check for first 12 primes  as base a to determine if n is prime or not.The idea of the algorithm 
is same as previous but instead of taking random value as a we will take a from first 12 primes.

Program:

#include<iostream>
#include<vector>
using namespace std;

template<typename Q>
Q mulmod(Q a, Q b, Q m) { // function to multiply two large number in moular arithmetic
Q res =
0;
while (b > 0) {
if (b & 1) {
res += a;
if (res >= m) res %= m;
}
b >>=
1;
a += a;
if (a >= m) a %= m;
}
return res;
}
template<typename P>
P powmod(P a, P e, P m) {
P res =
1;
while (e > 0) {
if (e & 1) {
res = mulmod(res, a, m);
}
e >>=
1;
a = mulmod(a, a, m);
}
return res;
}
template<typename T> // templated to make sure long long & int both works fine
bool Miller_Rabin_Prime(T num) {
//base cases:
if (num < 2) 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;
}
// for numbers upto 64 bit we need to check for these bases only
vector<T> base = { 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31 , 37 };
for (T a: base) {
T x = powmod(a, d, num);
if (x == 1 || x == (num - 1)) continue; // check again for next a
T i;
for (i = 1; i < r; i++) {
x = mulmod(x, x, num);
if (x == (num - 1))break; // Check again for next a
}
if (i == r)return false; // n is composite as no solution found for x using current a
}
return true; // n is prime
}
int main() {
long long num = 17630334936649;
if (Miller_Rabin_Prime(num)) cout << num << " is prime." << endl;
else cout << num << " is a composite number." << endl;
num =
32361122672259149;
if (Miller_Rabin_Prime(num)) cout << num << " is prime." << endl;
else cout << num << " is a composite number." << endl;
num =
123412344556543;
if (Miller_Rabin_Prime(num)) cout << num << " is probable prime." << endl;
else cout << num << " is a composite number." << endl;
return 0;
}

Output:

Comments