--- In

primenumbers@yahoogroups.com, "paulunderwooduk" <paulunderwood@...> wrote:

>

>

>

> --- In primenumbers@yahoogroups.com, "fabio_dias_moreira" <fabio@> wrote:

> >

> > Hi everyone,

> >

> > The Miller-Rabin test is not a deterministic primality test, but several bases combined can become a deterministic test below a certain number: e.g. the set of bases {2, 7, 61} correctly decides any N < 4.7G.

> >

> > Is there any known set of bases that correctly decides all N < 2^64? Googling around I found a bunch of sets of bases that correctly decide all N < 10^16, but that's still a factor of 2000 or so short.

> >

> > (What I'm actually looking for is a deterministic algorithm that is correct for N < 2^64, not necessarily Miller-Rabin based, as long as it's fast and simple to implement.)

> >

> > []s,

> >

>

> take the file from:

> http://www.cecm.sfu.ca/Pseudoprimes/index-2-to-64.html

> and apply the BPSW [1] formula to it to convince yourself that BPSW is good enough,

>

> [1] http://www.trnicely.net/misc/bpsw.html

Even better see:

http://gilchrist.ca/jeff/factoring/pseudoprimes.html
Paul