Charles Greathouse on Wed, 18 Aug 2010 20:24:19 +0200

[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]

Improvement to BPSW_isprime_small

Last year Jan Feitsma (with Will Galway, I believe) completed a tour
de force: calculating all the 2-pseudoprimes up to 2^64. He has only
recently announced this result; you can find the list here:

In October 2009 Jeff Gilchrist and David Cleaver verified this result
with Jan's algorithm and independently-written code to guard against
bugs.  Further, Jeff checked that there were no BPSW pseudoprimes in
that range using Thomas R. Nicely's BPSW code:

I checked this result with Pari's ispseudoprime, duplicating Jeff's results.

As a result, the limits in BPSW_isprime_small can be raised
substantially.  This would dramatically improve the speed of checking
primes p in (10^15, 2^64) ~ (1e15, 1.8e19).

Charles Greathouse
Case Western Reserve University

P.S. I apologize in advance to anyone involved in this effort that I
failed to mention; with a project this size it's almost inevitable.