galois.miller_rabin_primality_test(n: int, a: int = 2, rounds: int = 1) → bool

Determines if \(n\) is composite using the Miller-Rabin primality test.

Parameters:
n: int

An odd integer \(n \ge 3\).

a: int = 2

An integer in \(2 \le a \le n - 2\). The default is 2.

rounds: int = 1

The number of iterations attempting to detect \(n\) as composite. Additional rounds will choose consecutive primes for \(a\). The default is 1.

Returns:

False if \(n\) is shown to be composite. True if \(n\) is probable prime.

See also

is_prime, fermat_primality_test

Notes

The Miller-Rabin primality test is based on the fact that for odd \(n\) with factorization \(n = 2^s r\) for odd \(r\) and integer \(a\) such that \(\textrm{gcd}(a, n) = 1\), then either \(a^r \equiv 1\ (\textrm{mod}\ n)\) or \(a^{2^j r} \equiv -1\ (\textrm{mod}\ n)\) for some \(j\) in \(0 \le j \le s - 1\).

In the Miller-Rabin primality test, if \(a^r \not\equiv 1\ (\textrm{mod}\ n)\) and \(a^{2^j r} \not\equiv -1\ (\textrm{mod}\ n)\) for all \(j\) in \(0 \le j \le s - 1\), then \(a\) is called a strong witness to the compositeness of \(n\). If not, namely \(a^r \equiv 1\ (\textrm{mod}\ n)\) or \(a^{2^j r} \equiv -1\ (\textrm{mod}\ n)\) for any \(j\) in \(0 \le j \le s - 1\), then \(a\) is called a strong liar to the primality of \(n\) and \(n\) is called a strong pseudoprime to the base a.

Since \(a = \{1, n-1\}\) are strong liars for all composite \(n\), it is common to reduce the range of possible \(a\) to \(2 \le a \le n - 2\).

For composite odd \(n\), the probability that the Miller-Rabin test declares it a probable prime is less than \((\frac{1}{4})^t\), where \(t\) is the number of rounds, and is often much lower.

References

Examples

The Miller-Rabin primality test will never mark a true prime as composite.

In [1]: primes = [257, 24841, 65497]

In [2]: [galois.is_prime(p) for p in primes]
Out[2]: [True, True, True]

In [3]: [galois.miller_rabin_primality_test(p) for p in primes]
Out[3]: [True, True, True]

However, a composite \(n\) may have strong liars. 91 has \(\{9,10,12,16,17,22,29,38,53,62,69,74,75,79,81,82\}\) as strong liars.

In [4]: strong_liars = [9,10,12,16,17,22,29,38,53,62,69,74,75,79,81,82]

In [5]: witnesses = [a for a in range(2, 90) if a not in strong_liars]

# All strong liars falsely assert that 91 is prime
In [6]: [galois.miller_rabin_primality_test(91, a=a) for a in strong_liars] == [True,]*len(strong_liars)
Out[6]: True

# All other a are witnesses to the compositeness of 91
In [7]: [galois.miller_rabin_primality_test(91, a=a) for a in witnesses] == [False,]*len(witnesses)
Out[7]: True