//============================================================================
// Name : Miler-Rabin.cpp
// Author : A-L-P-H-A
// Version :
// Copyright :
// Description : Miler-Rabin primality test algorithm. A probabilistic algorithm
// which determines whether a given number is prime or not.
//============================================================================
#define PRIME 1
#define COMPOSITE 0
// Deterministic up to 2^64
const size_t Base[7] = {2, 325, 9375, 28178, 450775, 9780504, 1795265022};
// calculate a ^ n % m
size_t PowMod(size_t x, size_t e, size_t m){
size_t a = 1;
while (e) {
if (e & 1) {
a = a * x % m;
}
x = x * x % m;
e >>= 1;
}
return a;
}
// n−1 = 2^s * d with d odd by factoring powers of 2 from n−1
bool Witness(size_t n, size_t s, size_t d, size_t a)
{
size_t x = PowMod(a, d, n);
size_t y;
if (x == 1 || x == n - 1)
return PRIME;
while (s) {
x = x * x % n;
if (x == 1)
return COMPOSITE;
if (x == n - 1)
return PRIME;
--s;
}
return COMPOSITE;
}
bool Miller_Rabin(const size_t n, const size_t Bases[], const int l) {
if ((n & 1 ^ 1 && n != 2 ) || (n < 2) || (n % 3 == 0 && n != 3))
return COMPOSITE;
if (n <= 3)
return PRIME;
size_t d = n / 2, s = 1;
while (d & 1 ^ 1) {
++s;
d >>= 1;
}
for (int i = 0; i < l && Base[i] <= n - 2; ++i) {
if (Witness(n, s, d, Base[i]) == COMPOSITE) {
return COMPOSITE;
}
}
return PRIME;
}
#undef PRIME
#undef COMPOSITE
