# Is a probabilistic primality test implemented in Mathematica?

Imagine that I need to verify that a specific integer, like $n = 10^{1347}+3049$ is prime.

ProvablePrimeQ takes a lot of time, and, even if it will eventually work for this integer, it will work forever for somewhat larger integers.

PrimeQ works in 0.156 seconds, but, according to specification, it uses "the multiple Rabin-Miller test in bases 2 and 3 combined with a Lucas pseudoprime test". As far as I understand, its answer for every specific number is deterministic - either correct or false (no probabilities involved). It may happen that it returns false answer for $n=10^{1347}+3049$, and, in this case, it will still return false answer even if I call PrimeQ[n] a million times.

I do not understand why use Rabin-Miller test in bases 2 and 3 only? The theory says that if we select bases AT RANDOM, we get the correct answer with probability $3/4$. We can then repeat the test $N$ times to reduce the probability of error down to $(1/4)^N$. This way I can control the error probability.

The question is: Is there a randomised primality test implemented in Mathematica, where I can control the error probability as a parameter? Or where the error probability is given in the specification and I can reduce it by repeating the test?

• Where in the documentation did you find the claim, that PrimeQ might return incorrect answers? – Henrik Schumacher Jun 13 '18 at 15:38
• There is no randomized primality test built in as a system function. The reason to use bases 2 and 3, then go to the Lucas test, is that there is no compelling reason to believe alternatives offer any improvement. (1) A randomized set of Miller-Rabin tests would mean any incorrect outcome would be effectively unrepeatable. (2) A bunch of runs with probability 1-(1/4)^n incorrect is not really a great substitute for a faster tandem that has no known failure cases. – Daniel Lichtblau Jun 13 '18 at 15:50

PrimeQ is using Miller-Rabin tests with bases 2 and 3 to ensure that n is not a square, which is a necessary test, as otherwise the choice for Q in the Lucas test will not succeed. Other similar implementations use only the Miller-Rabin test with base 2 and check if n is square afterwards. See the wiki page on Baillie-PSW primality test.