View Single Post
Old 2011-04-27, 18:33   #28
Jeff Gilchrist
 
Jeff Gilchrist's Avatar
 
Jun 2003
Ottawa, Canada

7·167 Posts
Default

Quote:
Originally Posted by ATH View Post
This has already been done: http://www.trnicely.net/misc/bpsw.html
"Furthermore, preliminary analysis by Gilchrist of Feitsma's database, further extended, indicates that no Baillie-PSW pseudoprime (standard or strong) exists below 2^64 (24 October 2009; double checking of this result is in progress), approximately 1.8446744e19."

But I just took the list of the 31,894,014 SPRP base2 < 2^64 and did a Lucas-Selfridge test on them, it took around 15min, and none of them are lucas PRP. So assuming doublechecking proves that the SPRP list is complete there is BPSW pseudoprime below 2^64.
Jan Feitsma has posted the results as "preliminary" because nobody has verified the math of his algorithm to ensure that all the base 2 psp up to 2^64 have been enumerated. David Cleaver (WraithX on these boards) and I verified the pseudoprime database with Jan's algorithm using independently written code so we have double checked that his algorithm generated the same set of psp using different code. But Jan has not proven that his algorithm in fact enumerates 100% of the psp up to 2^64. Jan was originally in contact with Wil Galway (the one hosting the 2^64 database now) to review his math but for whatever reason his algorithm was never evaluated.

Back in 2009 when David and I finished double checking the psp database, I was able to confirm there were no BPSW psp up to 2^64 with his database (assuming we did in fact enumerate all of them) and posted that here: http://gilchrist.ca/jeff/factoring/pseudoprimes.html

Charles Greathouse has also confirmed no BPSW psp exist using the BPSW implementation in PARI with Jan Feitsma's database so two different implementations of BPSW have also been tried.

Last fiddled with by Jeff Gilchrist on 2011-04-27 at 18:39
Jeff Gilchrist is offline   Reply With Quote