24905Re: Infallible isprime(p) routine for 0<2^32
- 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.--Indeed, Thomas R. Nicely implemented the BPSW $620-640 test
> --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.
"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?
- << Previous post in topic Next post in topic >>