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:


*

*Sorts out $n \le 3$, even $n$, then $n$ divisible by small factors.

*Subjects $n$ to a strong base-2 Fermat primality test.

*Check for squareness of $n$.

*Subjects $n$ to a strong Lucas primality test with a particular protocol for selection of its $P$, $D$ and $Q$ parameters.

*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:


*

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

*$P=1$

*$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


*

*$Q$ would be guaranteed $\ne \pm 1$

*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: 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.
A: 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.
