Rabin-Miller’s Test for Primality

```struct RabinMiller
{
vector<int> base;

RabinMiller() {
base = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37};
}

ll mul_mod(ll x, ll y, ll MOD) {
ll res = 0, tmp = x%MOD;

while (y > 0) {
if (y&1)
res = (res + tmp) % MOD;

y >>= 1;
tmp = (tmp + tmp) % MOD;
}

return res;
}

ll pow_mod(ll x, ll exp, ll MOD) {
if (exp == 0)
return 1;

if (x > MOD)
x %= MOD;

if (exp & 1) {
ll half = pow_mod(x, exp >> 1, MOD);
return mul_mod(mul_mod(half, half, MOD), x, MOD);
}
else {
ll half = pow_mod(x, exp >> 1, MOD);
return mul_mod(half, half, MOD);
}
}

bool primalTest(int a, ll d, ll r, ll n) {

ll x = pow_mod(a, d, n);

if (x == 1 || x == n-1)
return true;

x = pow_mod(a, d*r, n);
if (x != 1)
return false;

r >>= 1;
while (r>1) {
ll m = pow_mod(a, d*r, n);

if (m != 1 && m != n-1)
return false;

if (m == n-1)
return true;

r >>= 1;
}

return false;
}

bool isPrime(ll n) {

if (n < 2) return false;
if (n < 4) return true;

ll d = n - 1;
ll r = d&-d;
d /= r;

for (int a : base)
if (a < n && !primalTest(a, d, r, n))
return false;

return true;

}
};
```