galois.miller_rabin_primality_test

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
Last update: Apr 21, 2022