|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: http://www.cecm.sfu.ca/Pseudoprimes/index-2-to-64.html 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: http://www.trnicely.net/misc/bpsw.html 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 Analyst/Programmer 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.