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"?
8
-
$\begingroup$ 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. $\endgroup$– joroCommented Apr 3, 2013 at 10:03
-
$\begingroup$ I mean trial division to some small bound. $\endgroup$– joroCommented Apr 3, 2013 at 10:04
-
3$\begingroup$ 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. $\endgroup$– Emil JeřábekCommented Apr 3, 2013 at 10:40
-
$\begingroup$ 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.) $\endgroup$– user9072Commented Apr 3, 2013 at 11:53
-
$\begingroup$ @Emil, how many primes in a handful? $\endgroup$– Gerry MyersonCommented Apr 3, 2013 at 12:15
|
Show 3 more comments
1 Answer
$\begingroup$
$\endgroup$
1
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.
answered Apr 3, 2013 at 13:26
-
$\begingroup$ The in-development version of
PARI(hencegp) goes this way up to a product of all primes up to 1,000,000. $\endgroup$ Commented May 12 at 12:09