Karim Belabas on Sat, 21 Aug 2010 20:12:18 +0200


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

Re: Improvement to BPSW_isprime_small


Thanks for notifying us. I have modified BSPW_isprime_small() accordingly
[ 'testing' branch only ].

Cheers,

    K.B.

* Charles Greathouse [2010-08-18 20:26]:
> 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.
--
Karim Belabas, IMB (UMR 5251)  Tel: (+33) (0)5 40 00 26 17
Universite Bordeaux 1          Fax: (+33) (0)5 40 00 69 50
351, cours de la Liberation    http://www.math.u-bordeaux1.fr/~belabas/
F-33405 Talence (France)       http://pari.math.u-bordeaux1.fr/  [PARI/GP]
`