Re: Miller-Rabin primality testing question

From: Tom St Denis (tomstdenis_at_gmail.com)
Date: 07/20/05 

Date: 20 Jul 2005 05:07:17 -0700

Scott "Poncho" Fluhrer wrote:
> "Nathan Gilbert" <ngilbert@acm.org> wrote in message
> news:dbkgcp0gur@news2.newsguy.com...
> > When using the Miller-Rabin (M-R) primality test on a number n, with say,
> > 20 iterations.
> >
> > Is n considered composite if out of those 20 iterations, M-R returned
> > composite at least once, or is it considered probably composite if out of
> > the 20 iterations, M-R returned composite more times than it returned
> > probably prime?
>
> Miller-Rabin returns one of two possible results: "p is probably prime" or
> "p is definitely composite". If M-R returns composite at least once, then p
> is known to be composite.

Just add a bit...

If you do initial trial division and then M-R you're very likely to
detect a composite on your very first trial. It's very rare to need
two trials and definitely unseen to require 20 [for random candidates].

You can approach M-R one of two ways really. If your candidate is
random you can use fixed bases and get a very high detection rate in as
little as one pass. Similarly if your candidate was chosen [say by
someone else] you can use random bases and get a high detection rate.

By "high" I mean above the 1/4 error rate.

If someone else choose both the bases and the candidate they can
optimally get past k trials with an success probability of 2^{-2k}.

So something like the primality testing in LibTomMath or other math
libraries are typically not meant for candidates which are not chosen
randomly. Something to be aware of...

Tom