# At what point does Miller-Rabin become faster than trial division?

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"?

• When hunting for very large primes, trial division is the first thing to try. It doesn't imply primality, but may show N is composite, saving a lot of time.
– joro
Commented Apr 3, 2013 at 10:03
• I mean trial division to some small bound.
– joro
Commented Apr 3, 2013 at 10:04
• Surely this depends heavily on the implementation and on the desired accuracy (i.e., how many iterations of Miller–Rabin you run for the given $N$). I’d guess Miller–Rabin might become faster already for numbers of the order of millions, but any realistic implementation will start with trial division by a handful of small primes anyway. Commented Apr 3, 2013 at 10:40
• Is there a reason you insist to comparing to Miller--Rabin or does it stand for 'some better algorithm'. (AFAIK, in fact in practise other things are used.)
– user9072
Commented Apr 3, 2013 at 11:53
• @Emil, how many primes in a handful? Commented Apr 3, 2013 at 12:15

Maple does the following:

1. Check a list of small primes directly

2. 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.

3. 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$

4. 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.

• The in-development version of PARI (hence gp) goes this way up to a product of all primes up to 1,000,000. Commented May 12 at 12:09