Getting wrong result with Lucas probable prime test on specific composite

Question

I'm trying to do the extra strong Lucas probable prime test on $15$ but keep getting the wrong result. $15=3 \cdot 5$ so it's composite, but the Lucas test says it's prime.

The parameters are $Q=1, P=15, D=221$ Since $n+1$ is a power of 2, the odd part is 1 so $s=1$. Then the condition $V_{d\cdot2^r} \equiv 0 (\bmod{n})$ for $0 \le r < s$ is true. Because with $r=0$ then $V_1=15=n$

Where is my mistake? Is $P$ wrong?

Answer 1

I assume that you are choosing $P$ by the method suggested on Wikipedia: set $Q=1$, and try values of $P$ starting from $3,4,5,\dots$ until $D = P^2-4$ satisfies $\left(\frac Dn\right)=-1$. Here, $P=15$ is indeed the smallest value of $P$ for which this holds.

Part of the fine print (which Wikipedia doesn't mention, but which is included in the Mathematica code for OEIS sequence A217719, the list of extra strong Lucas pseudoprimes) is that when $\left(\frac Dn\right)=0$ (that is, when $\gcd(D,n) > 1$) we should also stop, except in the unusual case that $D=n$ which comes up only for $n=5$. At this point, we know that $n$ is composite, for example because $\gcd(D,n)$ is a nontrivial divisor of $n$ (but see the note at the bottom of this answer).

There's some other fine print, too: when $n$ is even, or when $n$ is a perfect square, we treat that as a special case, declare $n$ to be composite, and stop.

In real-life examples, this situation is basically never going to come up, because it happens when we randomly stumble on a nontrivial divisor of $n$, so it's extremely unlikely to happen when $n$ is not obviously composite. But it is an exceptional case that needs to be dealt with, and if you're testing the algorithm on small numbers, you'll see it often.

In particular, when we take $n=15$, we first try $P=3$ and get $D = P^2-4 = 5$; since $\gcd(D,n)>1$, we stop and conclude that $n$ is composite.

---

Why the "only $n=5$" detail above? Well, the case that $\left(\frac Dn\right) = 0$ can come up in two ways.

• It happens if $n \mid D$, or $P^2-4 \equiv 0 \pmod n$. This definitely happens when we reach $P=n-2$, but we should find a good $D$ before that happens except in the unusual case $n=5$. If it happens for $P<n-2$, then $\gcd(P+2,n)$ and $\gcd(P-2,n)$ are nontrivial divisors of $n$, and $n$ is composite.
• It happens when $1 < \gcd(n,D) < n$. This only happens for composite $D$. In this case, $\gcd(n,D)$ is a nontrivial factor of $n$.

So either way, for $n>5$, when we see $\left( \frac Dn\right)=0$, we stop.