In order to decide out whether a number $n$ is extra strong Lucas pseudoprime, one usually chooses Lucas sequence where Jacobi symbol $(D/n) = -1$. Such a $D$ can be found by Method C by Robert Baillie, for example.
My question is, what to do when the Jacobi symbol $(D/n) = 0$? I've seen three approaches:
Exit as composite whenever $\lvert D \rvert\ \ne n$, continuing the search for $D$ otherwise. (Why continue the search? Why not simply return "not composite" when $\lvert D \rvert\ = n$?)
Simply return that $n$ is composite. (This can probably miss some pseudoprimes. How many, say, under $10^{10}$? Isn't it enough to filter out some small first primes first?)
Return $n$ is composite if $n = p+2$. (Isn't it the same as checking $\lvert D \rvert\ = n$?)
Btw., I'm asking this in the context of Baillie–PSW primality test.
PS: If $n$ is perfect square, does it always hold that $(D/n) = 0$? I'm asking because the search for Lucas chains is usually preceded by squareness test of $n$. Wouldn't it be possible to skip this test and only check for $(D/n) = 0$ instead?
Caveat: Baillie's method C chooses the parameters $P = 3$, $Q = 1$ and $P_{n+1} = P_n + 1$, other parameters might not work out as described below.
If $(D/n) = 0$ the sum $P + 2$ is a factor of $D$, so if $n = P + 2$ then $n$ is prime and composite with $(P+2)\mid n$ a factor of $n$ otherwise.
$n$ can be called a square if $(P + 2)^2 = n$ but that might take a long time to reach if we test large primes for cryptographic use.
The Jacobi $(D/n)$ will never be $-1$ if $n$ is a perfect square so it is much cheaper to test for squareness beforehand. Or wait a couple of rounds (the loops are quite cheap computationally) and add a test for squareness after some dozen or so loops.