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

24905Re: Infallible isprime(p) routine for 0<2^32

Expand Messages
  • WarrenS
    Mar 11, 2013
      > > The $620 test (not $640) can already be performed with a cost of 3 SPRP tests, so this wouldn't be an improvement over what's already done.
      > --well, it probably would be somewhat improved, since the "cost of 3" claim I doubt
      > was really true. But it would be annoying since you'd need an 8192-entry table.

      --Indeed, Thomas R. Nicely implemented the BPSW $620-640 test
      and reported

      "However, a BPSW test typically requires roughly three to seven times as many bit operations as a single Miller-Rabin test. The strong version of BPSW differs only in replacing the standard Lucas-Selfridge test with the strong Lucas-Selfridge test... the strong Lucas-Selfridge test incurs roughly 10% more running time... [but] appear to be more effective."
      It might be his implementation was cruddy, but I doubt that is the whole explanation?
    • Show all 37 messages in this topic