galois.miller_rabin_primality_test¶
- galois.miller_rabin_primality_test(n, a=2, rounds=1)¶
Determines if \(n\) is composite using the Miller-Rabin primality test.
- Parameters
- Returns
False
if \(n\) is shown to be composite.True
if \(n\) is probable prime.- Return type
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
Section 4.2.3 from https://cacr.uwaterloo.ca/hac/about/chap4.pdf
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