Baillie–PSW primality test

The Baillie–PSW primality test is a probabilistic primality testing algorithm that determines if a number is composite or a probable prime.

The Baillie-PSW test is a combination of a strong Fermat probable prime test to base 2 and a strong Lucas probable prime test. The Fermat and Lucas test each has its own list of pseudoprimes, that is, composite numbers that pass the primality test. For example, the first ten strong pseudoprimes to base 2 are 2047, 3277, 4033, 4681, 8321, 15841, 29341, 42799, 49141, and 52633 (sequence A001262 in OEIS). The first ten strong Lucas pseudoprimes (with Lucas parameters P = 1, Q = -1) are 5459, 5777, 10877, 16109, 18971, 22499, 24569, 25199, 40309, and 58519 (sequence A217255 in OEIS).

The power of the Baillie-PSW test comes from the fact that these lists of strong Fermat pseudoprimes and strong Lucas pseudoprimes have no known overlap. There is even evidence that the numbers in these lists tend to be different kinds of numbers. For example, pseudoprimes base 2 tend to fall into the residue class 1 (mod m) for many small m, whereas Lucas pseudoprimes tend to fall into the residue class −1 (mod m); see Section 6 of ^[1] and Table 2 and Section 5 of .^[2] As a result, a number that passes both a strong Fermat and a strong Lucas test is very likely to be prime.

No composite number below 2⁶⁴ (approximately 1.845·10¹⁹) passes the Baillie-PSW test.^[3] Consequently, this can be considered a deterministic primality test on numbers below that bound. There are also no known composite numbers above that bound that pass the test.

The authors of the test offered $30 for the discovery of a counterexample, that is, a composite number that passed this test. As of 1994, the value was raised to $620.^[4] As of June 2014 the prize remains unclaimed. However, a heuristic argument by Pomerance suggests that there are infinitely many counterexamples.^[5] Moreover, Chen and Greene ^{[6] [7]} have constructed a set S of 1248 primes such that, among the nearly 2¹²⁴⁸ products of distinct primes in S, there may be about 740 counterexamples.

The test

Let n be the odd positive integer that we wish to test for primality.

1. Optionally, perform trial division to check if n is divisible by a small prime number less than some convenient limit.
2. Perform a base 2 strong probable prime test. If n is not a strong probable prime base 2, then n is composite; quit.
3. Find the first D in the sequence 5, 8, 13, 20, 29, 40, ... (P² + 4) for which the Jacobi symbol (D/n) is −1. Set P = sqrt(D - 4) and Q = -1.
4. Perform a strong Lucas probable prime test on n using parameters D, P, and Q. If n is not a strong Lucas probable prime, then n is composite. Otherwise, n is almost certainly prime.

Remarks.

1. The first step is for efficiency only. The Baillie-PSW test works without this step, but if n has small prime factors, then the quickest way to show that n is composite is to find a factor by trial division.
2. The second step is a single application of the Miller-Rabin primality test. There is nothing special about using base 2; other bases might work just as well. However, much work has been done (see above) to verify that the combination of the base 2 strong probable prime test and a strong Lucas test does a good job of distinguishing primes from composites.
3. If n is a perfect square, then step 3 will never yield a D with (D/n) = −1; this is not a problem because perfect squares are easy to detect using Newton's method for square roots. If step 3 fails to produce a D quickly, one should check whether n is a perfect square.
4. Given n, there are other methods for choosing D, P, and Q; see pages 1401 and 1409 of.^[2] What is important is that the Jacobi symbol (D/n) be −1. Bressoud and Wagon (,^[8] pp. 266–269) explain why we want the Jacobi symbol to be −1, as well as why one gets more powerful primality tests if Q ≠ ± 1.
5. If Q ≠ ±1, there are additional tests that can be performed at almost no extra computational cost. After one has computed the powers of Q and the terms in the Lucas sequences that are used in the strong Lucas probable prime test, these additional primality conditions provide further opportunities to show that n is composite; see Section 6 of.^[2]

The danger of relying only on Fermat tests

There is significant overlap among the lists of pseudoprimes to different bases.

Choose a base a. If n is a pseudoprime to base a, then n is likely to be one of those few numbers that is a pseudoprime to many bases.

For example, n = 341 is a pseudoprime to base 2. It follows from Theorem 1 on page 1392 of ^[2] that there are 100 values of a (mod 341) for which 341 is a pseudoprime base a. (The first ten such a are 1, 2, 4, 8, 15, 16, 23, 27, 29, and 30). The proportion of such a compared to n is usually much smaller.

Therefore, if n is a pseudoprime to base a, then n is more likely than average to be a pseudoprime to some other base (see page 1020 of ^[1]). For example, there are 21853 pseudoprimes to base 2 up to 25·10⁹. This is only about two out of every million odd integers in this range. However (see page 1021 of ^[1]):

• 4709 of these 21853 numbers (over 21 percent) are also pseudoprimes to base 3; (and to all 3-smooth base)
• 2522 of these 4709 numbers (over 53 percent) are pseudoprimes to bases 2, 3, and 5; (and to all 5-smooth base)
• 1770 of these 2522 numbers (over 70 percent) are pseudoprimes to bases 2, 3, 5, and 7. (and to all 7-smooth base)

29341 is the smallest pseudoprime to bases 2 to 10. (and to all 7-smooth base) This suggests that probable prime tests to different bases are not independent of each other, so that performing Fermat probable prime tests to more and more bases will give diminishing returns. On the other hand, the calculations up to 2⁶⁴, mentioned above, suggest that Fermat and Lucas probable prime tests are independent (see also page 1400 of ^[2]), so that a combination of these types of tests would make a powerful primality test, especially if the strong forms of the tests are used.

There is also overlap among strong pseudoprimes to different bases. For example, 1373653 is the smallest strong pseudoprime to bases 2 to 4 (and to all 3-smooth base), and 3215031751 is the smallest strong pseudoprime to bases 2 to 10 (and to all 7-smooth base). Arnault ^[9] gives a 397-digit composite number N that is a strong pseudoprime to all bases less than 307. (and to all 293-smooth base) Because this N is a Carmichael number, N is also a (not necessarily strong) pseudoprime to all bases less than p, where p is the 131-digit smallest prime factor of N. A quick calculation shows that N is not a Lucas probable prime when D, P, and Q are chosen by the method described above, so this number would be correctly determined by the Baillie-PSW test to be composite.

Applications of combined Fermat and Lucas primality tests

The following computer algebra systems and software packages use some version of the Baillie–PSW primality test.

Maple's isprime function ,^[10] Mathematica's PrimeQ function ,^[11] PARI/GP's isprime and ispseudoprime functions ,^[12] and Sage's is_pseudoprime function ^[13] all use a combination of a Miller-Rabin (Fermat strong probable prime) test and a Lucas test. Maxima's primep function uses such a test for numbers greater than 341550071728321 .^[14]

The FLINT library has functions n_is_probabprime and n_is_probabprime_BPSW that use a combined test, as well as other functions that perform Fermat and Lucas tests separately .^[15]

The BigInteger class in standard versions of Java and in open-source implementations like OpenJDK, has a method called isProbablePrime. This method does one or more Miller-Rabin tests with random bases. If n, the number being tested, has 100 bits or more, this method also does a non-strong Lucas test that checks whether U_n+1 is 0 (mod n). ^{[16] [17]} The use of random bases in the Miller-Rabin tests has an advantage and a drawback compared to doing a single base 2 test as specified in the Baillie–PSW test. The advantage is that, with random bases, one can get a bound on the probability that n is composite. The drawback is that, unlike the Baillie–PSW test, one cannot say with certainty that if n is less than some fixed bound such as 2⁶⁴, then n is prime.

In Perl, the Math::Primality^[18] and Math::Prime::Util^[19][20] modules have functions to perform the strong Baillie-PSW test as well as separate functions for strong pseudoprime and strong Lucas tests. In Python, the NZMATH^[21] library has the strong pseudoprime and Lucas tests, but does not have a combined function.

GNU Multiple Precision Arithmetic Library's mpz_probab_prime_p function uses a Miller-Rabin test, but does not appear to use a Lucas test .^[22] Magma's IsProbablePrime and IsProbablyPrime functions use 20 Miller-Rabin tests for numbers > 34·10¹³, but do not combine them with a Lucas probable prime test .^[23]

References

Further reading

• Nicely, Thomas R., The Baillie-PSW primality test. 
• Weisstein, Eric W., "Baillie-PSW Primality Test", MathWorld.