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