Should GMP_BPSW_NOFALSEPOSITIVES_UPTO_64BITS default to 1?
Paul Eggert
eggert at cs.ucla.edu
Fri Jun 13 23:36:35 CEST 2025
Currently mpz/millerrabin.c contains this:
#ifndef GMP_BPSW_NOFALSEPOSITIVES_UPTO_64BITS
#define GMP_BPSW_NOFALSEPOSITIVES_UPTO_64BITS 0
#endif
It would be helpful to have a comment as to why the default is 0, as I
see indications in the published literature that defaulting to 1 should
be safe for Baillie PSW.
Alternatively, we could change the default to 1. Something like the
following, perhaps:
/* By default assume no BPSW false positives < 2^64, as per:
Gilchrist J.
Pseudoprime Enumeration with Probabilistic Primality Tests.
2013-07-01.
https://gilchrist.great-site.net/jeff/factoring/pseudoprimes.html
Also see:
Ishmukhametov ST, Mubarakov BG, Rubtsova RG, Oleinikova EV.
On the Baillie PSW Conjecture. Russ Math. 2024-08-06;68(4):72-78.
https://doi.org/10.3103/S1066369X24700294
*/
#ifndef GMP_BPSW_NOFALSEPOSITIVES_UPTO_64BITS
#define GMP_BPSW_NOFALSEPOSITIVES_UPTO_64BITS 1
#endif
More information about the gmp-devel
mailing list