# 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
• n (int) – An odd integer $$n \ge 3$$.

• a (int, optional) – An integer in $$2 \le a \le n - 2$$. The default is 2.

• rounds (int, optional) – The number of iterations attempting to detect $$n$$ as composite. Additional rounds will choose consecutive primes for $$a$$.

Returns

False if $$n$$ is shown to be composite. True if $$n$$ is probable prime.

Return type

bool

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 : primes = [257, 24841, 65497]

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

In : [galois.miller_rabin_primality_test(p) for p in primes]
Out: [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 : strong_liars = [9,10,12,16,17,22,29,38,53,62,69,74,75,79,81,82]

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

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

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