Primality testing algorithm

Question

Say, I would like to check a hypothesis concerning primes. Something like "there exists a prime between $n$ and $2n$ for every choice of $n$". I would like to run a code in MATLAB for choices of $n$ upto $2^{32}$ and then use that data and publish the conjecture in a journal.

The question is, what should I use to check primality. Obviously, AKS is an option but it is really really slow. I can use the in-built MATLAB function $isprime()$ which I think uses $10$ instances of Miller-Rabin. This will be way faster but the journal might reject this saying that Miller Rabin is probabilistic and that I should instead use a deterministicalgorithm since one exists.

What should I do? Use AKS? Go with MATLAB's inbuilt Miller-Rabin? Or look at other deterministic algorithms?

I don't think this is the best place to ask this. However I could not find where else to ask. Any suggestions?

Answer 1

A pragmatic answer: Use the Miller-Rabin test with 50 iterations. The probability that a composite number will be wrongly declared prime by this test is at most $2^{-100}$ (see, e.g., here). This is smaller than the chance of a cosmic ray causing a bitflip error that causes your program to output an erroneous result. So, if you're not worried about cosmic rays, you shouldn't be worried about probabilistic algorithms.

An alternative: use any probabilistic algorithm to rule out composite numbers. If the probabilistic algorithm claims the number is prime, use a deterministic primality test, or use a test that produces a primality certificate. There are many such algorithms, and you can study the literature and find one which leads the best tradeoff between complexity of implementation vs speed on numbers of the size you care about.

Answer 2

"There is a prime between $n$ and $2 n$" is known as Bertrand's postulate, proven by Chebyshev.

Answer 3

You don't need many primality checks.

The conjecture is obviously false for n = 1. Now you let n = 2 and find the largest prime p in the range n < p < 2n. If no p is found, the conjecture is false. Otherwise, the conjecture is true for all n < p. We set n = p, again find the largest prime p in the range n < p < 2n, which proves the conjecture for all n < p, and so on. So the primes we need to find are:

n = 2 -> p = 3. 
n = 3 -> p = 5.
n = 5 -> p = 7.
n = 7 -> p = 13.
n = 13 -> p = 23. 
n = 23 -> p = 43.
n = 43 -> p = 83.
n = 83 -> p = 163.
n = 163 -> p = 317.
n = 317 -> ...

The range of integers n for which the conjecture is proven almost doubles with each step, so to cover n ≤ 2^32 we will only have to find 24 or 25 more primes, to cover n ≤ 2^64 we need to find 32 more primes,