I've read in various places (and know) that Miller-Rabin is a much faster primality test than trial division for large $N$, but is much slower than trial division for small $N$.
My question is: how large is "large" and how small is "small"?
I've read in various places (and know) that Miller-Rabin is a much faster primality test than trial division for large $N$, but is much slower than trial division for small $N$.
My question is: how large is "large" and how small is "small"?
Maple does the following:
Check a list of small primes directly
Check the gcd with the precomputed number N=2*3*...*97 if gcd is not 1 the number is composite. Otherwise if the number is under $101^2$ it is prime.
Repeat step 2 but with N the product of the 3 digit primes. By this stage two "trial divisions have checked all prime factors under 1000 and given a definitive answer for anything under $1018081=1009^2$
Go on to fancier methods.
I suppose that having 64 or so more precomputed constants and doing gcd with them could check all prime factors under 65536 if desired.
PARI
(hence gp
) goes this way up to a product of all primes up to 1,000,000.
$\endgroup$
Commented
May 12 at 12:09