Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
It's clear that Mathematica uses the Baillie–PSW test for its PrimeQ function (which tests primality), and as I read in the Mathematica documentation, it starts with trial division, then base 2 and 3 Miller–Rabin, and then Lucas pseudoprime test. My question is:
Can we remove base 2 and 3 and use only a random base?
Also, can any one suggest a good reference about this primality test other than Wikipedia?
The advantage in using base 2 is that we know all of the psp's base 2 up to $2^{64}$. It has been verified that none of these psp(2)'s passes a Lucas test when the parameters $P, Q$ are chosen in accord with any of the methods in the Baillie/Wagstaff paper.
If you choose a random base, there might be some composite $n$ that passes both the Fermat and Lucas tests. For example, $n = 5777$ is a strong psp base 76, and is also a Lucas pseudoprime.
By the way, if you implement a Lucas test, I would also recommend adding the following check, which is virtually free once you reach the end of the Lucas calculation. If $n$ is an odd prime and $(n, QD) = 1$ where $D = P^2 - 4Q$, (and, as usual, $\left(\frac{D}{n}\right) = -1$ (a Jacobi symbol), then $V_{n+1} \equiv 2Q \pmod n$. If $D, P$, and $Q$ are chosen by method $A^*$ (see Baillie/Wagstaff), then 913 is the only odd composite number up to 25 billion for which this congruence holds. (The B/W paper gives a limit of $10^8$, but I've recently carried the calculation farther). So, in addition to the sprp(2) and slprp(P,Q) tests, this congruence adds additional strength to the primality test.
References for the test:
Pomerance, Selfridge, Wagstaff, "The Pseudoprimes to 25 x 10^9", July 1980. Page 1024-1025, Check if n is a strong probable prime base 2. Check whether n is a Lucas probable prime using method A (Selfridge) or B. The authors offer $30 to the first finder of a counterexample or proof of non-existence. It references the next paper when discussing the test.
Baillie and Wagstaff, "Lucas Pseudoprimes", October 1980. Page 1401. Trial divide to some convenient limit. Check whether n is a strong probable prime base 2. Check whether n is a strong Lucas probable prime using method A (Selfridge) or B.
Pomerance, "Are there counter-examples to the Baillie-PSW Primality Test?", 1984. References PSW80: Check whether n is a strong probable prime base 2. Check whether n is a Lucas probable prime using the Selfridge parameters (method A). He mentions that even if condition 1 is weakened, every composite to n <= 25*10^9 still fails. The short paper repeatedly calls this combination of a strong base-2 prp and Lucas-Selfridge prp tests the "Baillie-PSW" test.
All of these describe using a strong base-2 probable prime test. The slightly earlier PSW paper indicates a Lucas test, while the BW paper recommends a strong Lucas test. The 1980 papers indicate that one of two specific parameter selection methods should be used, while Pomerance's 1984 paper drops the non-Selfridge method.
In my opinion, the paper by Baillie and Wagstaff is the primary reference, though should be read in combination with Pomerance, Selfridge, and Wagstaff. Consensus over time is that the Selfridge (method A) parameter selection should be used. Other variations commonly used include the extra-strong test, the "almost" extra-strong test, and Frobenius tests. See the page "Pseudoprime statistics, Data, and Tables" for more info and links.
To answer your Mathematica questions:
Based on Pinch (1993), Mathematica used to do a base 2 strong pseudoprime test, as it should, but used a borked "Lucas" test that was not the test Baillie et al. indicated. Pinch found pseudoprimes to their test. He also indicates that Wolfram modified their Lucas test in some way, but not to use the Lucas test that should be used for BPSW. Without information from Wolfram, we don't know what they've done in the last 24 years since then. Perhaps they beefed up their "Lucas" test and added the base-3 M-R test to cover up issues. Maybe they're now using a proper Lucas test. We don't know.
If the correct Lucas test was used, then the base 3 test could be removed and we'd be left with a similar BPSW test to that used by most other packages. We'd know there were absolutely no counterexamples less than 2^64, and no known larger counterexamples. Adding another test, whether base 3 or a random base, would add a bit more certainty for >64-bit inputs. I don't think that's a bad idea.
Replacing the base-2 test with a random-base test is, in my opinion, a bad idea. We have well known results for using base 2, including the very nice no-64-bit-counterexamples one. It makes the test deterministic. While using a random base will still retain the anti-correlation property with regard to the Lucas test, it has different tradeoffs. Personally I think it's a better idea to use a proper BPSW test (base 2 SPRP + strong/AES/ES Lucas) plus one or more random-base tests if you want to defeat adversaries who secretly know BPSW pseudoprimes. Or add the extra work for a Frobenius test on top of the Lucas test.
You are asking two questions. I will only answer the first.
It is very likely that Mathematica uses the base 2 and 3 test as an optimization. These bases are probably faster to test (because of their magnitude), and they work for both numbers. You can skip this test if you want, but the resulting function would be slower on average.
