Miller Robin Primality Test

// Miller Robin Primality Test

// mulMod(a, b, p) : returns (a*b)%p,
// When a, b and p are both long long int
// If we multiply a and b then it will overflow
ll mulMod(ll a, ll b, ll p)
{
    ll x = 0;
    ll y = a%p;
    while (b)
    {
        if (b & 1)
            x = (x+y)%p;
        y = (y*2)%p;
        b /= 2;
    }
    return x%p;
}

// Mod(a, b, p) : return (a^b)%p
// When a, b and p are both long long int
ll Mod(ll a, ll b, ll p)
{
    ll res = 1;
    ll x = a % p;
    while (b)
    {
        if (b & 1)
            res = mulMod(res, x, p);
        x = mulMod(x, x, p);
        b /= 2;
    }
    return res%p;
}

// This function is called for all k trials. It returns
// false if n is composite and returns true if n is
// probably prime.
// s is an odd number such that n-1 = 2^d * s, d >= 0
bool millerTest(ll d, ll s, ll n)
{
    // Pick a random number in [2..n-2]
    // Corner cases make sure that n > 4
    ll a = rand() % (n-4) + 2;

    // Compute a^s % n
    ll x = Mod(a, s, n);

    if (x == 1 || x == n-1)
        return true;
    // Keep squaring x while one of the following doesn't happen
    //   i. s doesn't reach n-1
    //  ii. (x^2)%n is not 1
    // iii. (x^2)%n is not n-1

    // i.e. check all r, where 0 < r < d
    //                   where n-1 = 2^d * s

    for (int r = 1; r < d; r++)
    {
        x = mulMod(x, x, n);
        if (x == 1)     return false;
        if (x == n-1)   return true;
    }
    // Return composite
    return false;
}

// It returns false if 'n' is composite and returns true
// if n is probably prime. 'k' is an input parameter that
// determines accuaracy level. Higher value of 'k' indicates
// more accuaracy.
bool isPrime(ll n, int k = 20)
{
    // Corner cases
    if (n <= 1 || n == 4)  return false;
    if (n <= 3)            return true;
    if (n%2 == 0)          return false;

    // find d and s such that, n-1 = 2^d * s, where s = odd, d >= 0
    ll s = n-1, d = 0;
    while (s%2 == 0)
    {
        s /= 2;
        d++;
    }
    // Iterative given number of 'k' times
    for (int i = 0; i < k; i++)
    {
        if (millerTest(d, s, n) == false)
            return false;
    }
    return true;
}

int main()
{
    ll n;
    cin >> n;
    if (isPrime(n))    cout << "Prime" << endl;
    else               cout << "Not Prime" << endl;
}