Loading ...
Sorry, an error occurred while loading the content.

Re: Miller-Rabin bases to 2^64

Expand Messages
  • paulunderwooduk
    ... Even better see: http://gilchrist.ca/jeff/factoring/pseudoprimes.html Paul
    Message 1 of 3 , Jan 17, 2011
    • 0 Attachment
      --- 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.