Miller-Rabin primality test

Overview

Primality testing is a significant problem in mathematics and computer science, playing a crucial role in fields like cryptography. Determining whether a large number is prime is computationally expensive with traditional methods, making efficient algorithms essential.

The Miller-Rabin Primality Test is a probabilistic algorithm that can quickly test the primality of large numbers. For certain ranges, it can even be used in a deterministic manner. This algorithm has a time complexity of $\mathcal{O}(k\cdot {\log }^{3}N)$ and is considered important both theoretically and practically.

---

Background: Fermat’s Little Theorem and Its Limitations

The Miller-Rabin algorithm builds upon Fermat’s Little Theorem.

Fermat's Little Theorem

For a prime number $p$ and an integer $a$ that is coprime to $p$, $a^{p-1}\equiv 1(\mathrm{mod}p)$

Using Fermat’s Little Theorem, we can infer the following:

If $a^{p-1}\not\equiv 1(\mathrm{mod}p)$, then $p$ is not prime.

However, there exist composite numbers that satisfy Fermat’s Little Theorem. These are called Carmichael numbers, such as $561$. This means that Fermat’s primality test alone cannot filter out all composite numbers, highlighting its limitations.

---

Miller-Rabin Primality Test

The Miller-Rabin test addresses the weaknesses of Fermat’s test by identifying strong probable primes.

Algorithm Steps

1. Factorize $n-1$
   • For an odd integer $n>2$, write $n-1=2^s\cdot d$, where $d$ is odd and $s$ is the greatest power of $2$ dividing $n-1$.
2. Choose a base
   • Select a random integer $a$ such that $2\le a\le n-2$.
3. Check primality conditions
   • If $n$ satisfies one of the following conditions, it is considered a probable prime for the chosen base $a$:
     • $a^d\equiv 1(\mathrm{mod}n)$
     • $a^{2^r\cdot d}\equiv -1(\mathrm{mod}n)$ for some $0\le r<s$
4. Composite determination
   • If none of the conditions are satisfied, $n$ is definitively composite.

This algorithm is probabilistic, and repeating the test $k$ times can reduce the error probability to $4^{-k}$. In practice, most composite numbers fail the test, making the error probability even lower.

Probabilistic Nature

The Miller-Rabin test is probabilistic, with an error probability of $4^{-k}$ after $k$ iterations.

• Increasing the number of iterations ($k$) reduces the error probability exponentially.
• In practice, most composite numbers fail the test, resulting in a lower error rate than the theoretical calculation.

---

Deterministic Testing: Specific Base Combinations

The Miller-Rabin test can be used deterministically by selecting specific base combinations for certain ranges.

RANGE ($N<X$)	REQUIRED BASE COMBINATION	REFERENCE
1,373,653	2, 3	Pomerance et al. (1980)
9,080,191	31, 73	Pomerance et al. (1980)
25,326,001	2, 3, 5	Pomerance et al. (1980)
3,215,031,751	2, 3, 5, 7
4,759,123,141	2, 7, 61
2,152,302,898,747	2, 3, 5, 7, 11	Jaeschke (1993)
3,474,749,660,383	2, 3, 5, 7, 11, 13	Jaeschke (1993)
341,550,071,728,321	2, 3, 5, 7, 11, 13, 17	Jaeschke (1993)

These base combinations ensure that all composite numbers within the specified range are detected. This deterministic approach is often used in cryptography.

---

Implementation Example (C++)

The Miller-Rabin algorithm can be implemented in various programming languages. Below is a simple implementation in C++:

inline long long mulmod(__int128 a, __int128 b, __int128 mod) {
  return a * b % mod;
}
 
long long power(long long base, long long exp, long long mod) {
  long long ret = 1;
  while (exp) {
    if (exp & 1) ret = mulmod(ret, base, mod);
    base = mulmod(base, base, mod);
    exp >>= 1;
  }
  return ret;
}
 
bool miller_rabin(long long n, long long a) {
  int r = 0;
  long long d = n-1;
  while (!(d & 1)) {
    r++;
    d >>= 1;
  }
 
  long long x = power(a, d, n);
  if (x == 1 || x == n-1) return true;
  for (int i=0; i<r-1; i++) {
    x = mulmod(x, x, n);
    if (x == n-1) return true;
  }
  return false;
}
 
bool prime(long long n) {
  long long a[] = {2, 3, 5, 7, 11, 13, 17, 19, 23};
  if (n <= 1) return false;
  if (n == 2 || n == 3) return true;
  if (!(n & 1)) return false;
 
  for (int i=0; i<9; i++) {
    if (n == a[i]) return true;
    if (!miller_rabin(n, a[i])) return false;
  }
  return true;
}

---

Additional Resources

• The PrimePages - Strong probable-primality and a practical test
• Wikipedia - Miller–Rabin primality test
• Lecture Notes: Miller–Rabin Test - Purdue University
• Improving the Speed and Accuracy of the Miller-Rabin Primality Test

---

References

Pomerance1980

Carl Pomerance, J. L. Selfridge and Samuel S. Wagstaff, Jr. “The Pseudoprimes to 25 · 10^9.” Mathematics of Computation, 35(151), pp. 1003-1026, 1980. American Mathematical Society.

Jaeschke1993

Gerhard Jaeschke. “On strong pseudoprimes to several bases.” Mathematics of Computation, 61(204), pp. 915-926, 1993. American Mathematical Society.