14
$\begingroup$

In mpz_nextprime(), after some sieving with small primes, an MR test function is called, with the number of trials set to 25 (https://github.com/alisw/GMP/blob/master/mpz/nextprime.c#L118):

      if (mpz_millerrabin (p, 25))
        goto done;

But then in mpz_millerrabin(), for large enough candidates (candidates bigger than $31\times2^{46}$), the number of trials is suddenly reduced to 1 (https://github.com/alisw/GMP/blob/master/mpz/millerrabin.c#L142):

      reps -= 24;

with no explanations.

As a result, for large candidates only three tests are run:

  • MR with base 2
  • Lucas
  • MR with random base

But the comment at the top of the millerrabin.c says that "Knuth indicates that 25 passes are reasonable." What is the reason the number of trials is unconditionally slashed this way?

$\endgroup$
5
  • $\begingroup$ Not expert in those stuff, I just happened to bump into OpenSSL code for this task a few days ago and looks like they do at least 64 rounds of MR independent of the size of the prime that they are searching for $\endgroup$
    – tur11ng
    Commented Dec 2, 2022 at 0:01
  • $\begingroup$ Yes, I am actually looking at it right now. 128 for >2048 bits and 64 otherwise. I was under the impression that GMP does 25 rounds, but I don't get what's being done in that code I quoted. $\endgroup$
    – fjarri
    Commented Dec 2, 2022 at 0:10
  • $\begingroup$ I think that the change means that the number of Miller-Rabin tests is reduced by 24 irrespective of the size of the number. $\endgroup$
    – Daniel S
    Commented Dec 2, 2022 at 7:46
  • 3
    $\begingroup$ It has been observed that the likelihood that a number which passes Miller Rabin for uniformly sampled random base is composite (a strong Fermat pseudoprime) drops sharply when the size of the number tested increases by orders of magnitude. See my Answer to this 2016 Math.SE about the gap between the proven results and the observed rarity of such large strong pseudoprimes. This supports the notion that a single MR test may suffice for very large numbers. $\endgroup$
    – hardmath
    Commented Dec 3, 2022 at 5:52
  • 1
    $\begingroup$ Interesting, I guess that also explains why in FIPS186-4, seemingly paradoxically, larger numbers require less MR iterations. $\endgroup$
    – fjarri
    Commented Dec 3, 2022 at 21:32

3 Answers 3

18
$\begingroup$

The Baillie-PSW test is being used in place of 24 Miller-Rabin tests. This is not unreasonable for large numbers when the cost of Miller-Rabin testing can become burdensome and also helps to prevent adversarial prime generation when the random base selection is poor.

It is an open question as to whether a Baillie-PSW pseudoprime exists or not. It is known that none exist up to certain bounds ($2^{64}$ has certainly been checked, but may have been surpassed). The problem has a certain notoriety among the computational number theory community.

It is argued that as there may be a lack of independence in failing Miller-Rabin tests, mixing Miller-Rabin and Lucas tests may be more effective. For example, pseudoprimes have been constructed that pass Miller-Rabin for all bases up to 307 and implementations that used fixed bases for Miller-Rabin tests have often had bespoke pseudoprimes constructed in order to show the limitations of this approach.

The change may have been motivated by the 2018 Prime and Prejudice paper by Albrecht et al which recommends the use of the Baillie-PSW test to counteract adversarial prime generation. In particular they construct a 1024-bit "GMP pseudoprime" that is a composite that tests as prime when GMP is instantiated with the PRNG in a static state.

$\endgroup$
5
  • 2
    $\begingroup$ Addition: MR+BPSW is sanctioned by NIST's FIPS 186-4 appendix C.3, table C.1. See also their appendix F.1 and references on the required number of rounds of (random-base) MR. For the latest developments on BPSW, see R. Baillie, A. Fiori, S. Wagstaff Jr. Strengthening the Baillie-PSW primality test, also at arXiv:2006.14425. $\endgroup$
    – fgrieu
    Commented Dec 2, 2022 at 8:02
  • $\begingroup$ Thanks, that's a very informative paper. Although it's still somewhat confusing since I can see a Lucas test in GMP, but not a Fermat one, so it's not really a full Baillie-PSW. If I understand the paper correctly, it recommends dropping MR completely in favor of Baillie-PSW, right? $\endgroup$
    – fjarri
    Commented Dec 2, 2022 at 8:02
  • 1
    $\begingroup$ @fjarri A strong Fermat test is a Miller-Rabin test to a particular base and so the base 2 Miller-Rabin call fulfils this requirement. I don't read the paper as requiring MR to be dropped, merely that B-PSW be introduced as necessary requirement. $\endgroup$
    – Daniel S
    Commented Dec 2, 2022 at 8:11
  • $\begingroup$ The P&P paper states "In the absence of known pseudoprimes, we recommend that libraries switch to using the Baillie-PSW primality test wherever possible." which I understood as a recommendation to drop the MR test. $\endgroup$
    – fjarri
    Commented Dec 2, 2022 at 8:20
  • 3
    $\begingroup$ @fjarri: I find reasonable to recommend dropping MR as the only test for adversarially generated $n$. In any case, I find reasonable to check parity, perhaps perform a test of divisibility by small primes ($3×5×7×11×…×23×29<2^{32}$ and $3×5×7×11×…×47×53<2^{64}$ makes it convenient to test the first 10 or 16 primes with a single pass), perform a strong pseudoprime to base 2, a well-tested variation of BPSW (and at this point we know no counterexample), then a second strong pseudoprime test to a random odd base in $[3,n/2)$ for extra confidence. $\endgroup$
    – fgrieu
    Commented Dec 2, 2022 at 8:24
8
$\begingroup$

The article, "Strengthening the Baillie-PSW primality test" referred to above, suggests adding a third test to the standard BPSW (MR test base 2 combined with Lucas).

But there's a third congruence that is true for primes, and rarely true for composite $N$: $V_{N+1} = 2 Q \pmod N$. A composite that satisfies this congruence is called a $V$-pseudoprime.

Up to 1E15, there are about 2 million base-2 psp's, and about 2 million Lucas pseudoprimes (and no overlap between these two sets).

However, there are only five $V$-pseudoprimes up to 1E15. None of these is either a base-2 psp or a Lucas pseudoprime.

Therefore, we recommended that a primality test include a check on the value of $V_{N+1}$. The $V$'s are typically computed along with the $U$'s, so almost no additional computation would be required.

$\endgroup$
3
  • $\begingroup$ Thank you for the reference (and for the method itself — you're the Robert Baillie, right?). I have discovered the paper myself just a few weeks ago and implemented in the library I was writing (github.com/entropyxyz/crypto-primes). Hopefully, it will replace the strong Lucas check in the new FIPS standard, because it allows for some nice performance optimizations. $\endgroup$
    – fjarri
    Commented Jan 6, 2023 at 22:27
  • $\begingroup$ Also, sorry for a slightly offtopic question, but it would be awesome to get an answer from the source, as it were. Does one need to check for gcd(Q, n) == 1 before the Lucas test itself? It is not clear to me from the paper. (gcd(2D, n) == 1 happens automatically by construction of D). $\endgroup$
    – fjarri
    Commented Jan 6, 2023 at 22:45
  • 1
    $\begingroup$ @fjarri Mathematica 13.2.1 also uses it, see: community.wolfram.com/groups/-/m/t/2898096 $\endgroup$ Commented Apr 14, 2023 at 13:54
5
$\begingroup$

Further thoughts: Doing dozens of MR tests (that is, strong Fermat tests) tests may not be the way to go.

  1. It takes roughly 4 times as long to do a BPSW test (Fermat + Lucas) as to do a Fermat test. It is not clear that the additional time needed to do one or two dozen Fermat tests produces more trustworthy results than BPSW.

  2. Most importantly: Fermat tests to different bases are not independent. The Pomerance/Selfridge/Wagstaff paper The Pseudoprimes to 25⋅109, has data to back this up. For example, Table 6 shows that there are 21853 psp(2) below 25*10^9, but that 4709 of these (21%) are also psp(3).

    The Baillie/Wagstaff paper Lucas Pseudoprimes, explains why: If N is a pseudoprime to some base a, this is probably because N is one of those few numbers that is pseudoprime to many bases. Therefore, N is more likely than most numbers of that size to be pseudoprime to another base, b. Theorem 1 in that paper gives a formula for the number of such bases mod N. For example, N = 341 is psp(2), but it is also psp to 99 other bases between 2 and N - 2.

By contrast, there are hints that Fermat and Lucas tests are independent. For example, Fermat and Lucas psp's tend (with exceptions, of course) to fall into residue classes +1 and -1 (mod m) for small m.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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