# BPSW Primality Test - Selection of D & Q parameters

I'm studying a paper by the authors of the Baillie-PSW primality checker here, but am baffled by a detail of its Lucas primality test.

A BPSW implementation typically:

1. Sorts out $n \le 3$, even $n$, then $n$ divisible by small factors.
2. Subjects $n$ to a strong base-2 Fermat primality test.
3. Check for squareness of $n$.
4. Subjects $n$ to a strong Lucas primality test with a particular protocol for selection of its $P$, $D$ and $Q$ parameters.
5. If the preliminaries, the strong Fermat test, check for squareness and the strong Lucas test all fail to prove $n$ composite, then $n$ is assumed prime.

The Lucas primality test for $n$ requires three auxiliary integer parameters, $P$, $D$ and $Q$, related by the equation $D = P^2 - 4Q \ne 0$. The BPSW authors insist on certain additional properties: In particular, that a value of $D$ is required such that the Jacobi symbol $\left( \frac{D}{n} \right)$ is -1 (if it's 0 then lucky you! You've found a factor!). They point out clearly that if $n$ or $D$ is square, then the Jacobi symbol will be $\ge 0$ (by the rules of the symbol).

The authors offer several strategies for selection of $P,D,Q$. The most popular is due to John Selfridge:

1. Select the first $D \in \{ 5, -7, 9, -11, 13, -15, \ldots \}$ s.t. $\left( \frac{D}{n} \right) = -1$ (or 0) holds.
2. $P=1$
3. $Q = (P^2 - D)/4 = (1-D)/4$

The authors also point out that if $Q \ne \pm 1$ on top of $\left( \frac{D}{n} \right) = -1$, then the primality test can be strengthened even further at very low additional cost.

Finally, the authors also prove that the search for a $D$ satisfying the Jacobi-symbol requirement usually terminates within 2-3 evaluations.

And now we get to my question. As described, Selfridge's strategy starts off with $D=5$. If this is accepted, then $Q=(1-5)/4=-4/4=-1$, losing primality-checking strength. Next up is $D=7$, which is OK, but if that doesn't work then we're at $D=9$, which is square (and thus, unusable (?)). And soon enough you might encounter $D=25$, which is also square.

Why does the most-commonly-used BPSW Lucas parameter-selection strategy start with such a poor set of values? What makes this strategy preferable?

For that matter, all strategies examined by the author ask for the first $D$ in some series to satisfy $\left( \frac{D}{n} \right) = -1$, and yet the authors seem to gloss over the possibility of random search, or a search started at a high(er) value of $D$, where

1. $Q$ would be guaranteed $\ne \pm 1$
2. Square $D$ are much less dense.

especially in light of their proof that only 2-3 values of $D$ need to be checked on average before a suitable one is found.

You could even design a strategy that is guaranteed to avoid square $D$'s. In much the same way that incrementing $1$ by successive odd integers $3, 5, 7, \ldots$ generates all squares ($1^2+3=2^2$, $2^2+5=3^2$, $3^2+7=4^2 \ldots$), incrementing $2$ by those same successive odd integers produces numbers that cannot be square ($5, 10, 17, 26, 37, 50, \ldots$). Taking every second non-square so produced would satisfy the requirement that 4 divides evenly $(1-D)$: 5, 17, 37...

Why is that? Does the BPSW algorithm rely on the first, or low, values of $D$?

My research has led me to only this page by Thomas R. Nicely, who writes only a single off-hand sentence on the topic:

Additional conditions sometimes imposed (Riesel, 1994, p. 130), that N not divide Q and that D be square-free, were found to be irrelevant to this application of Lucas sequences.

which doesn't really tell me much.

• A couple comments. The testing for small factors is purely something practical for any implementation and isn't part of BPSW itself. For D values, skipping 9 and 25 is easy enough, or just let the Jacobi computation find it. Note that ~85% of arbitrary inputs will select D=5 or -7, so it really isn't a big deal. Also note oeis.org/A217719 (extra strong test) where Baillie (many years later) just uses Q=1, P=3,4,5,6,7,... until (D|n)=-1. Pari/GP's test uses Q=1,P=3,5,7,... until (D|n)=-1. Re the ES test, note Nicely's comments are in error. Oct 3, 2016 at 17:10

First, computing Jacobi (D/n) is roughly equivalent to GCD(n, something). Compared to the rest of the primality test, this is a tiny amount of calculation.

Second, the last section of the Lucas Pseudoprime paper shows that you usually don't need to try very many D's before finding one with (D/n) = -1.

Third, I have found that exactly how you get P, Q doesn't matter much in the sense that the number of Lucas pseudoprimes up to x is roughly the same. As the person writing the above question noted, it is a good idea to make sure abs(Q) > 1. Method A* in the Lucas Pseudoprimes paper does this.

I would say the strategy is convenient, but not necessarily "preferable" to other methods. Except that, after all these years of using method A or A*, no one has found a counterexample. If you choose another method for finding P and Q, you run the risk that one of the resulting Lucas pseudoprimes would be a strong pseudoprime base 2.

A suggestion for strengthening the test: I would also suggest checking, at the end of the calculation, that V_{n+1} = 2Q (mod n). I'm currently using method A* and looking for composite solutions. So far, n = 913 is the only odd composite n up to 60 billion that satisfies this congruence. Once V_{n+1} has been calculated (mod n), this additional check is virtually free.

• Holy smokes, are you the Robert Baillie himself? Jul 19, 2017 at 17:34
• I just across this thread again. There are now more data: We found only FIVE odd composites under 10^15 for which V_{n+1} = 2Q (mod n). See arxiv.org/abs/2006.14425 Jun 27, 2021 at 19:24

## Here Is The Deterministic Lucas Primality Test, Only One Test Needed To Rule Out Any Composite Number, NO Need For Checking Strong Pseudoprimes Base Two, Good Luck

here i will present to you best way of choosing $$P, Q$$ and $$D$$ parameters for Lucas primality test. this selection is always correct and no composite number will pass this test. here is my overview of $$BPSW$$ test.

## Weakness of BPSW Test

• it is not dynamic, for any number $$n$$ always selection of $$D$$ start with $$5$$. At the end we use the same $$D$$ to test primality of many $$n$$
• second order is controlled by previous two terms, so for checking the primality of a number we should device a way that check all two terms at a point that we use to test the primality of number $$n$$.
• combined tests, lucas and spsp2 test

## New Way Of Selecting $$P, Q$$ and $$D$$

Let $$n$$ be a number that we are testing for primality, calculate $$y = floor(\sqrt{n})$$. Then check if $$n$$ is perfect square. Let $$D = P^2 + 4Q$$, use small $$P$$, $$\{1, 2, ..., 9\}$$ prefer primes. then calculate $$D$$ by varying $$Q$$, $$Q> y - 1$$, calculate Jacobi symbol $$(D/n)$$, $$(D/n)= - 1$$. then you are done. set your $$P, Q$$ and $$D$$. Use Jacobi symbol to avoid factorization of big numbers

## Testing

we dont need to repeat the mistakes, compute $$U_n$$ and $$U_{n+ 1}$$. if $$n$$ is prime, $$\{U_n, U_{n+1}\} = \{n - 1, 0\}$$ the number of $$Q$$ that you will need to test depends on the Value of $$P$$. is $$P$$ is $$!$$ maximum $$47$$ $$Q$$s, does not depend on $$n$$. Many composite numbers satisfy only one test of these two, and many of them the divisibility test.

• It's still probabilistic. If you have a proof it's deterministic I'd love to see it. Feb 20, 2020 at 15:00