# Re: Miller-Rabin primality testing question

**From:** Tom St Denis (*tomstdenis_at_gmail.com*)

**Date:** 07/20/05

**Next message:**Tom St Denis: "Re: Why are there differences in the same algorithm?"**Previous message:**Tom St Denis: "Re: square mod"**In reply to:**Scott \: "Re: Miller-Rabin primality testing question"**Messages sorted by:**[ date ] [ thread ] [ subject ] [ author ] [ attachment ]

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

**Next message:**Tom St Denis: "Re: Why are there differences in the same algorithm?"**Previous message:**Tom St Denis: "Re: square mod"**In reply to:**Scott \: "Re: Miller-Rabin primality testing question"**Messages sorted by:**[ date ] [ thread ] [ subject ] [ author ] [ attachment ]