2
$\begingroup$

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

$\endgroup$
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$
    – joro
    Commented Apr 3, 2013 at 10:03
  • $\begingroup$ I mean trial division to some small bound. $\endgroup$
    – joro
    Commented 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$ Commented 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$
    – user9072
    Commented Apr 3, 2013 at 11:53
  • $\begingroup$ @Emil, how many primes in a handful? $\endgroup$ Commented Apr 3, 2013 at 12:15

1 Answer 1

2
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ The in-development version of 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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.