I read here that Baillie-PSW primality test is proven correct up to $2^{64}$, but I understand PrimeQ
is only proven correct up to $10^{16}$, or was that extended up to $2^{64}$? Doesn't PrimeQ
use a variation of Baillie-PSW? For many years I have wondered why Wolfram Research hasn't verified that PrimeQ
is correct up to $2^{64}$, and ensure it is the fastest of all known algorithms that could make that claim.
1 Answer
The MSE post https://math.stackexchange.com/questions/123465/do-we-really-know-the-reliability-of-primeqn-for-n1016 may be a satisfactory affirmative answer. It looks like the work to show PrimeQ
is valid up to $2^{64}$ was never published, but it is still hosted here http://www.janfeitsma.nl/math/psp2/index. Finally, a Google search found a writeup of this work that appeared in a student research forum http://ceur-ws.org/Vol-1326/ in 2015, which lends credence to the result.
-
$\begingroup$ The main link (used by wikipedia) is this. web.archive.org/web/20191121062007/http://www.trnicely.net/misc/… $\endgroup$ Aug 16, 2022 at 23:50
PrimeQ
was proven correct up to $10^{16}$? $\endgroup$