View Single Post
Old 2021-04-27, 23:00   #7
charybdis's Avatar
Apr 2020

1111101102 Posts

Feitsma's data suggests a rough 4.5-times increase in the number of 2-PSPs for each additional 5 powers of 2. So the file for 2^79 would be ~90 times the size of the file for 2^64: very large for a download but not hard to store. 2^128 would of course be totally impractical. The proportion of 2-PSPs below 2^64 that are strong pseudoprimes is about 27%, and this appears to increase as the numbers get bigger, so it's not a whole load easier to only store the SPSPs.

The larger problem would be finding all these PSPs. The search up to 2^64 took tens of CPU-years. Granted, that was in 2009, and GPUs would likely be useful as it appears that the most difficult part of the search involved doing a lot of trial-factoring of Mersenne numbers. Going up to 2^79 ought to be ~2^15 times harder than 2^64 (as we just have to trial-divide 15 bits higher, right?). Even if using modern GPUs gives a speedup of factor 2^15 relative to CPUs from 2009 - others can enlighten me on what a realistic number would be - this would still suggest tens of GPU-years for a search to 2^79.

And that's before we get on to this part, where the algorithm that Feitsma used would require over a terabyte of memory, so a slower method would likely be required.
charybdis is offline   Reply With Quote