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;
        
    }
};