Primality Algorithm

[Anton Stiglic]

----- Original Message ----- 
From: "Ben Laurie" <ben at algroup.co.uk>
To: "tom st denis" <tomstdenis at yahoo.com>
Cc: <cryptography at metzdowd.com>
Sent: Tuesday, May 20, 2003 5:20 AM
Subject: Re: Primality Algorithm


> tom st denis wrote:
> > In all honestly unless you are doing this for research purposes you
> > might as well just use say 8 rounds of Miller-Rabin.  For all practical
> > purposes that is just as good [chances of failure < 2^-80].
>
> I presume you meant 80 rounds.


No, he actually meant 3 :)

Well, it depends...

If you want to generate a 1024 prime say, by choosing random candidates
from a uniform and independent distribution (or by incremental search
starting from a random candidate), and testing the candidates with rounds
of Miller-Rabin until you get an integer that passes the Miller-Rabin tests,
then 3 rounds of Miller-Rabin is enough to get a probability of error
(picking
a integer that is in fact composite) of less than 2^80.

This is explained in section 4.4 of the Handbook of Applied Cryptography.
You can follow the references for the papers describing the original results
by Damgard, Landrock and Pomerance,  and also by Brandt and Damgard
in the case of incremental search.  The paper by Beauchemin, Brassard,
Crepeau, Goutier and Pomerance is also interesting for calculating the more
easy to find error bound of 2^80 when using 40 rounds or Miller-Rabin, the
reasoning is given in note 4.47 of HAC;  I say easier to find
error-probability
 bound but the result is not straight forward from
the fact that 1 round of Miller-Rabin will declare a composite to be prime
with
probability less than 1/4, as many people wrongly deduce.

If you are given a candidate from an unknown or not uniform and independent
distribution, and you are asked to test if its prime or not, then you need
40 rounds
of Miller-Rabin (so that the probability that a composite passes as a prime
be less
than 2^80).

--Anton


---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo at metzdowd.com