## Re: Miller-Rabin bases to 2^64

Expand Messages
• ... Even better see: http://gilchrist.ca/jeff/factoring/pseudoprimes.html Paul
Message 1 of 3 , Jan 17, 2011
--- 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
Your message has been successfully submitted and would be delivered to recipients shortly.