5
$\begingroup$

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.

$\endgroup$
2
  • 3
    $\begingroup$ Just curious, where have you seen that PrimeQ was proven correct up to $10^{16}$? $\endgroup$
    – thorimur
    Mar 12, 2021 at 2:46
  • 4
    $\begingroup$ PrimeQ does use Baillie-PSW. $\endgroup$ Mar 12, 2021 at 13:15

1 Answer 1

3
$\begingroup$

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.

$\endgroup$
1

Not the answer you're looking for? Browse other questions tagged or ask your own question.