# Why using primes as base in the Rabin-Miller test?

I have done some computer tests with the Rabin-Miller primality test:

To test an odd number $n$, write $n=2^r\cdot s + 1$, where $s$ is odd. Given a number $a$ such that $1<a<n-1$,
if
$\:\:\:\:1$. $a^s\equiv 1\pmod n$
$\:\:\:\:\:\:\:\:\:\:\:\:$or
$\:\:\:\:2$. it exists an integer $j: 0\le j<r$ with $a^{2^j\cdot s}\equiv -1\pmod n$
then $n$ is pseudo prime.

It seems to be popular to chose $a$ to be a prime number, and my question is if there are rational reasons for that?

I have computed the number of primality tests until $10$ errors appears for randomly selected b-digit $n$ and for $a=2$, for random $a$ in the intervall $1<a<n-1$ and finally for random primes in the same intervall and the result differs very little regarding the equation for the line. Below the test for random primes as $a$: The x-axis is the number of bits for $n$ and the y-axis is the logarithm of the average number of tests until an error occurred.

• It doesn't really matter. The significance of this test is that the proportion of all Miller--Rabin witnesses for an odd composite $n > 1$ is at least 75\% (and if you assume the Generalized Riemann Hypothesis then there must be a Miller--Rabin witness for $n$ that is at most $2(\log n)^2$). This doesn't involve any kind of restriction to prime numbers as MR witnesses. In practice the test works very quickly on composite $n$ (i.e., a witness is revealed without trying too many $a$) and it's natural to start out with small $a$: the first first choices $a = 2$ and $a = 3$ are prime. – KCd Jun 8 '16 at 20:09
• I tested 10 single RM all gave no prime using a random base not necessary prime. I'll read your link. – Lehs Jun 8 '16 at 21:36
• @KCd: Can't you please copy your comment into an answer that I can accept? – Lehs Jun 9 '16 at 5:40
• I suspect it has to do with the density of prime powers in small numbers. If it is SPRP-2 then base 4, 8, 16, 64, etc. will be also. If it passes base 3 then it will pass base 9. So when looking at small bases, restricting to primes makes some sense in that you won't hit these. This shouldn't be an issue for large inputs and random bases. I also recommend looking at BPSW, and thinking about fixed vs. random bases when input is supplied by an adversary. Arnault and others show that any efficient fixed base method is vulnerable to counterexample generation. – DanaJ Jun 9 '16 at 16:00
• @DanaJ: I tried Arnault's number 5000 times with randomly selected prime numbers < 1000000 as base and the test reported prime 5000 times. But on the other side, due to the diagram above the probability of randomly finding a false 1120-bit prime is less than finding a specific unique particle in universe. – Lehs Jun 9 '16 at 22:49

## 1 Answer

As far as I know, Miller-Rabin is probabilistic when you use arbitrary (random) witnesses, with probability of false positives decaying as the number of test rounds goes up.

For $$k=2\log^2n$$ the probability of a composite number passing all the $$k$$ tests is $$n^{-\log n}$$ (see this paper) which for most purposes is a failure frequency much lower than hardware failures, so it's considered a safe bet.

Now, to answer your question: if you choose your witnesses to be the first $$P$$ primes, Miller-Rabin becomes deterministic up to a certain limit. Moreover, if GRH is true this means Miller-Rabin is deterministic for all integers, provided you use enough prime witnesses. In particular, for $$n<2^{64}$$, Miller-Rabin is deterministic when you check the following witnesses [2], [3]: $$a = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41}$$