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.

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 $\text{gcd}(a,n)=1$, then either $a^r\equiv 1(\text{mod}n)$ or $a^{2^{j}r}\equiv -1(\text{mod}n)$ for some $j$ in $0\le j\le s-1$.

In the Miller-Rabin primality test, if $a^r\not\equiv 1(\text{mod}n)$ and $a^{2^{j}r}\not\equiv -1(\text{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(\text{mod}n)$ or $a^{2^{j}r}\equiv -1(\text{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

• https://math.dartmouth.edu/~carlp/PDF/paper25.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