Miller-Rabin — Probabilistic Primality Test

Algorithm

boolean millerRabin(long n, long a) {
  if (n % a == 0) return n == a;
  long d = n - 1; int s = 0;
  while ((d & 1) == 0) { d >>= 1; s++; }
  long x = modPow(a, d, n);
  if (x == 1 || x == n - 1) return true;
  for (int r = 1; r < s; r++) {
    x = x * x % n;
    if (x == n - 1) return true;
  }
  return false;
}

Deterministic bounds

n < 3.3·10¹⁴: bases {2, 3, 5, 7, 11, 13, 17, 19, 23} deterministic. Full 64-bit: {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37}.

Probability

k rounds with random bases: false-positive ≤ 4^(-k). k = 20 → ~10^(-12).

Complexity

O(k · log³ n) with big-int. O(k · log n) for 64-bit n with fast modmul.