Talk:Baillie–PSW primality test

A mess

This article is a mess and it would take a month of Sundays to correct all of the errors in it.

• It inherits the error from Richard Guy's book confusing B-PSW with Selfridges Fermat/Fibonacci test. I put in a correction of a sort.

• It defines the term "Baillie-PSW test" to be only the strongest version of the test and then uses it in the broader sense often.

• It didn't even mention that Pomerance, Selfridge, and Wagstaff were authors of the BPSW test until I put that in.

• The first error may occur in the title: A solid case could be made to take Baillie's name off. The first paper that mentions the $30 prize has authors Pomerance, Selfridge, and Wagstaff only.

&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&

• OK. I took out the bold P, S, and W.
• OK. If Pomerance says Baillie's name should be there, that's good enough for me.
• It wouldn't hurt to say this in the article.
• I was fooled by the BW paper being published in October--after the PSW paper. Of course P, and S had seen it in preprint form.
• Bad news about Chen and Greene being confused also! Let's not add to the confusion!

$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$

• I put in BW's result that the average number of D's that need to be tried is about 3.14.
• I took the 'red' out of the link to Samuel Wagstaff. It doesn't like Samuel K. Wagstaff, Jr.

Garfield Garfield

It's a wiki, so you're welcome to improve it (noting that others may "improve" it back). MathPerson made huge improvements in 2013 when it was little more than a stub.

I don't particularly like the bolded letters and would prefer something like "It is named after the authors ..., ..., ..., and ... who introduced it in two papers published in 1980." I thought the authors were clear from the references, but I guess it wasn't to you. I've been thinking of inserting the (arguably) more common acronym BPSW somewhere in the first paragraph.

Re the strong test, PSW July 1980 indicates the test is a SPSP-2 + Lucas test, but cites the October 1980 paper as the source of the test. BW October 1980 says the test is a SPSP-2 + strong Lucas test (in other words, the PSW80 paper cited this, but then dropped the "strong" from the Lucas test). Pomerance 1984 cites PSW80, calls the test Baillie-PSW, and calls it a SPSP-2 plus Lucas-Selfridge test. I don't think there is any room to argue against the first test being a strong probable prime test with base 2. Personally I think the BW80 paper is the definitive source, as it is the one that goes into detail about the various alternatives, why they chose this test, and why we ought to use the strong Lucas test. It gives the algorithm on page 1401. PSW80 cites it.

It looks like Chen and Greene have also confused BPSW with the Selfridge conjecture, as they clearly describe that (a PSP-2 and Fibonacci congruency) and not the BPSW test, but write "We call such numbers Baillie-PSW pseudoprimes." I think the text should make it more clear that they have just made a mistake in calling it that. The remarks section could also be improved in this regard.

DAJ NT (talk) 00:16, 28 August 2015 (UTC)

I do want to point out that while I believe it should be a strong test (both historical and noting that there is no practical reason not to do so -- it runs the same speed or faster and the pseudoprimes are a subset), many authors follow Pomerance and just say a Lucas test, which also opens the door to many variants as noted below in this page for implementations (they are doing neither a Lucas-Selfridge test nor a strong Lucas-Selfridge test). Pomerance certainly knows the topic, so there is a good argument against my view as well. DAJ NT (talk) 13:53, 28 August 2015 (UTC)

I think the test is actually randomized because the base of the Strong Pseudoprimality test is not defined... Fetofs ^Hello! 01:33, 21 April 2006 (UTC)

Page 1401 of Baillie and Wagstaff (1980) states "Step 2. If n is not a strong probable prime to base 2, then n is composite." While people play loose with the parameters and Lucas test, the base for the M-R test is definitely 2.

For tests that purely use strong probable prime tests (e.g. "M-R with k bases"), some people implement this as the first k primes, others as k random bases between 2 and n-1. The latter seems more desirable for any situation where you have an adversary cleverly picking n values to fool you (though make sure your "random" selection doesn't use a fixed seed or it is really no better than fixed bases). DAJ NT (talk) 00:11, 27 May 2013 (UTC)

parameters and strong/non-strong

It would be nice to have a bit more clarification between a strong BPSW test and a variant, or some discussion of what this means. In my opinion, the current text correctly describes the strong BPSW test from page 1401 of Baillie and Wagstaff (1980). The current introduction (paragraph 2) describes it as a strong Fermat PRP test and a strong Lucas PRP test. It implies that the parameters are chosen as described in the test section. Section "The test" describes in detail using the strong PRP test, selecting D/P/Q using method A (Selfridge's method), then run a strong Lucas PRP test. This corresponds to page 1401 of Baillie and Wagstaff (1980).

David Cleaver wrote in 2011 that he did an exhaustive check under 2^64 and no counterexamples were found by either the non-strong or strong versions, both using the method A (Selfridge) parameters. I have run Feitsma's SPSP-2 database against the standard Lucas-Selfridge, strong Lucas-Selfridge, extra-strong Lucas, "almost extra strong" Lucas (extra strong test without the U=0 condition), Pari's Lucas test (the "almost extra strong" test with P += 2 parameters), GAP's method as I understand it, MPIR, and GMPY2. None of them produce false results in the 2^64 range.

The application section seems to be lacking in rigor with what software is running the test as described on the page, and which are running a variant (using different parameters and/or a non-strong Lucas-Selfridge test). For closed-source software this can be a bit difficult.

• Maple doesn't give a lot of information -- the Vr3 release notes indicate "one strong pseudo primality test and one Lucas test."
• Mathematica's PrimeQ is claimed on MathWorld to be "multiple Rabin-Miller test in bases 2 and 3 combined with a Lucas pseudoprime test." It isn't clear what Lucas test this is.
• Pari 2.3.5 and later uses what I will call an "almost extra strong" Lucas test. It is the extra strong test but only calculating V, so ignores the U=0 condition. This yields more pseudoprimes than the extra strong test but fewer than the strong test. The parameter selection is similar to the OEIS method, but increments P by 2, so yields a different set.
• SAGE 5.8 says it is using a strong Lucas test, but also says "IMPLEMENTATION: Calls the PARI ispseudoprime function", which the code in fact does. So it really does whatever Pari does.
• As mentioned in the text, the Maxima manual says that for integers over 341550071728321, primep uses some M-R tests (default 25, no mention of whether these are random), followed by "one Lucas pseudo-primality test".
• GAP uses a BPSW variant (see its integer.gi for details). Trial division to 1000, followed by a strong pseudoprime base 2 test, followed by a Lucas test with non-standard parameters and non-standard conditions. P=2, Q=1, while (D|n) != -1, increment P. Check that U_{n+1} == 0 and V_{n+1} == 2. This method produces very slightly fewer pseudoprimes than the standard Lucas-Selfridge test, but many more than the strong Lucas-Selfridge test.
• FLINT 2.3's n_is_probabprime does deterministic MR tests for small n, and says BPSW for larger. The "BPSW" test seems to instead be the PSW $620 test: if n is 3 mod 10 or 7 mod 10, then a Fermat test followed by Fibonacci test is done, otherwise a strong probable prime test is followed by a standard Lucas-Selfridge test.
• MPIR 2.6.0 uses a similar test as FLINT for numbers that fit in one limb (2^64) -- it's a PSP2+Fibonacci or SPSP2+Lucas-Selfridge. It has no counterexamples under 2^64 using Feitsma's database. Above 2^64 it uses 10 Miller-Rabin tests with randomly selected bases.
• T.R. Nicely's iBPSW() function does MR base 2 followed by a strong Lucas test using method A parameters.
• Perl's Math::Primality uses basically the same code as Nicely, in Perl + Math::GMPz.
• Perl's Math::Prime::Util has both C and pure Perl code for the strong BPSW test (e.g. MR base 2 test followed by a strong Lucas test using method A parameters). It also has implementations of other Lucas tests.
• Perl's Math::Prime::Util::GMP has C+GMP code doing the strong BPSW test as well as other Lucas tests.
• David Cleaver's mpz_prp software does the strong BPSW test (as well as separate tests, a non-strong test, and extra-strong test). In particular, mpz_bpsw_prp does a non-strong BPSW using method A parameters, and mpz_strongbpsw_prp does the strong test using method A parameters.
• Python's gmpy 2.0 uses David Cleaver's software and hence exports the 11 tests it provides including the strong BPSW test.

DAJ NT (talk) 23:57, 26 May 2013 (UTC)

Randomized Bases

These are some comments in reference to the Java isProbablePrime function mentioned in the applications. I think using a single base 2 and then optional extra tests is advantageous vs. just random tests for a few reasons:

• Deterministic within a range (currently 2^64). This is mentioned.
• One can still retain the advantage of a probability bound (4/15 or 1/8 for the Lucas test, 1/4 for each M-R). I'm not sure whether fixing one of the M-R bases at 2 has an impact on the bounds vs. a random base.
• Any false positive will have to have passed a BPSW test. This helps with determinism.
• Assume the PRNG used to select bases is compromised through malice or incompetence. In the worst case, all random bases are identical and may be an adversary's choice. In the BPSW+extra-MR case, even with a completely broken random base selection, it must pass BPSW plus one random base of an adversaries choice. We don't currently know any numbers that can pass BPSW, while it isn't too hard to come up with numbers that pass a strong Lucas test and M-R with multiple bases 3 < b < n. There are threads in the OpenJDK list about this issue.

Looking purely at residue classes, there doesn't seem to be a strong disadvantage, which would be my initial question (the BPSW test gets a lot of its strength because the pseudoprimes tend to fall in different residue classes, hence the tests have less overlap than random selection). It looks from a small sample like it isn't quite as strong a relationship as for base 2, but still definitely there.

With regard to OpenJDK, the implementation does use the behaviour mentioned on the article's main page. In older OpenJDK implementations there was also a math.Primality class that had different behavior (and whose function is called isProbablePrime). The documentation doesn't specify that a Lucas test is used, from what I see, so the implementation could change. DAJ NT (talk) 17:53, 10 October 2013 (UTC)

Not a probabilistic test

The "classic" variation of this test is not probabilistic. Probabilistic tests use random parameters to test a given number n such that the probability of a false positive is generally below some provable bound. E.g. for randomly selected witness a, the likelihood of a false positive on a Miller-Rabin (aka strong Fermat) test is at most 1/4th. This implies that repeating the test may give different outcomes if n is composite.

The Baillie-PSW test uses a fixed parameter selection and thus is not probabilistic. It is, in my opinion, best described as a heuristic test. Specifically, there are no known pseudoprimes but if a composite number were to pass the test, it would always do so, no matter how many times the test is repeated. Aragorn2 (talk) 10:09, 19 October 2022 (UTC)

A primality test is deterministic if it outputs True when the number is a prime and False when the input is composite with probability 1. Here even worse we do not know if the probability is 1. Valery Zapolodov (talk) 09:59, 15 April 2023 (UTC)