Pseudoprime Statistics, Tables, and Data 
(Fermat, Miller-Rabin, Lucas, Strong Lucas, Extra-Strong Lucas, Baillie-PSW)

by Dana Jacobsen

• PSP data from Jan Feitsma and William Galway, replicated to 1e12 with my code. SPSP-2's computed with my code from the Feitsma PSP-2 list. All Lucas data data generated with my code. See the Galway link for full PSP/SPSP data to 2^64.

• All code used from Math::Prime::Util (latest code in GitHub, GMP code also available). I use the forprimes feature to loop over primes generated with a segmented sieve, running the particular test on all the odd composites between the last prime and this one. This method means no primality tests need to be done. It is grossly less efficient than Jan Feitsma's more complicated methods. I am using my native 64-bit code, which is 3-6x faster than my GMP versions (though obviously limited to 2^64). Generation at ~2e13 for Lucas is about 1e10 range per hour per thread.

• The strong pseudoprimes to base 2 are a subset of the pseudoprimes to base 2. The strong Lucas pseudoprimes are a subset of the Lucas pseudoprimes. The extra strong Lucas pseudoprimes are a subset of the almost extra strong Lucas pseudoprimes. Because the LPSP and SLPSP tests use the Selfridge parameters while the AESLPSP and ESLPSP tests use the Baillie OEIS parameters, they have different pseudoprime sets. Below 2^64, the PSPs and SPSPs are a disjoint set from any of the listed Lucas PSPs. Above 2^64 we believe there is overlap but no examples have been found.

• We use the Selfridge parameters for the Lucas and strong Lucas pseudoprimes. The primary reference is Lucas Pseudoprimes by Baillie and Wagstaff (1980).

• The extra strong test is defined in Grantham 2000 theorem 2.3, as well as earlier preprints. It does not mention how to choose the parameter. The sequence above uses the parameter selection described in OEIS A217719 and Wikipedia:
  
        P = 3; Q = 1
      while (jacobi(P*P-4,n) != -1)
        P++;

  Thomas R. Nicely's code does what looks like the same test, but uses a different parameter selection (he stops when jacobi(D,n) != 0 rather than jacobi(D,n) == -1) which leads to overlap with the strong pseudoprime test, making it not useful for a BPSW-style test. Presumably this parameter choice came from something in Mo/Jones (which I do not have), as it is not in Grantham's papers. Baillie and Wagstaff (1980) pages 1401-1406 spend some time justifying why one should use jacobi(D,n) = -1 when combining a Lucas and PSP test. The parameter choice shown earlier is the natural extension to the extra strong test and avoids all the problems Nicely discusses.
  
  MathWorld incorrectly defines the test as using Q = -1, contradicting their reference (Grantham 1998). Nicely discovered this error in 2005. Using Q = -1 results in a completely broken test. Note the comment later in their paragraph about using parameter (b,1) which is correct and contradictory to the earlier portion.
  
  Pari's documentation does not match the code. It indicates a strong Lucas test, but the implementation for years has been an almost extra strong test (see below). It indicates Q = -1 and Q = 1 in the same sentence. As expected, the code uses Q = 1 since Q = -1 is nonsense. It indicates P is the smallest positive integer meeting the conditions, where in fact P starts at 3 and increments by 2.
  
  David Cleaver's mpz_prp software has code for the extra strong test. Make sure you get version 1.1 (3 July 2013) or later, as earlier versions had an incorrect test. It does not define a parameter selection method. The incorrect v1.0 code is also in GMPY2. Note: I believe his other Lucas code works just fine, so it only impacts this one function which is not used by any other parts of the software.

• The "almost extra strong" test is a generalization of the Lucas test used in Pari's is_pseudoprime. Use Crandall and Pomerance algorithm 3.6.7 to quickly get the V parameter, then perform an extra strong test only using V. This leads to some more pseudoprimes (since the U = 0 condition is ignored) but can be implemented such that it runs extremely fast, and still produces fewer pseudoprimes than the strong test.
  
  The version above uses the Baillie OEIS parameter selection, so it is a superset of the OIES A217719 extra strong test. It takes about 2/3 the time of a strong Lucas-Selfridge test in my implementations. As n increases in size, the times converge however, so this is most useful for small n, depending on your big integer library.
  
  It is also possible to recover U_n using Crandall and Pomerance equation 3.13: U_n = D^-1 (2V_{n+1} - PV_n) allowing us to run the full extra-strong test at the cost of a single modular inversion. This computation is easy and fast in GMP, so we can get the full extra-strong test at essentially the same performance as the almost extra strong test.
  
  The Pari implementation has two differences. First, it does not include the required gcd check, probably because the overall implementation does trial division to 101 so it is unlikely to be necessary. More importantly, it uses a slightly different parameter selection: P += 2 in the method shown above, instead of P += 1. This leads to a different set of pseudoprimes, though the quantity produced seems to be similar. Here are the first 1e11 Pari LucasPsP pseudoprimes.

• The BPSW test uses a combination of strong probable prime test with base 2 (the SPSP-2 column above) and a Lucas test. The reference by Baillie and Wagstaff indicate this should be a strong Lucas test with one of two specified parameter selections (the Selfridge method being the most commonly used). However, there are no BPSW pseudoprimes below 2^64 using any of the four Lucas tests above, and no known BPSW pseudoprime of any size. While many math packages say they uses a BPSW test, many seem to use a custom variant of the Lucas test and will produce a different set of pseudoprimes than the above.

• There are additional, easy to apply, tests that can be performed to strengthen the Lucas tests. See Wikipedia's Lucas PSP page or section 6 of the Lucas Pseudoprimes paper.

• There are other compositeness tests (with associated pseudoprimes), but the Fermat, Miller-Rabin, and Lucas tests are the most commonly used.
  
  Of some interest are the Frobenius pseudoprimes, as they have much smaller error bounds: 1/7710 (cite) vs. 1/8 for the extra strong Lucas test (cite), 4/15 for strong Lucas test (cite), 1/4 for the Miller-Rabin test (cite). The computational cost is about 3x a Miller-Rabin test.
  
  Paul Underwood has come up with a Frobenius-style test (in "Quadratic Compositeness Tests", preprint, 2012) that costs about 2.4x the cost of a Miller-Rabin test and has no known counterexamples (exhaustively verified to 7e13). Code in C, C+GMP, Perl, and Javascript
  
  Perrin pseudoprimes have also been of some interest, though I believe mostly as curiosities as they are time-consuming to calculate (even using modular matrix exponentiation).

• Jan Feitsma's list of pages
• Jeff Gilchrist's Pseudoprime page
• ATH's list of Lucas pseudoprimes to 3*10^12
• The best known SPRP bases sets. This shows minimal sets required for deterministic testing of small numbers