Why am I getting the wrong result when applying the extra strong Lucas pseudoprime test?

Question

I'm trying to do the Lucas extra strong pseudoprime test but get the wrong result. For example $13$ is prime but the test gives composite. Here is what I tried:

$n=13$ then $n+1=14=7 \cdot 2^1$ gives $d=7$ and $s=1$.
set $P=3,Q=1,D=3^2-4=5$

$U_1=1$ and $V_1=P=3$
$U_2=3$ and $V_2=7$
$U_3=8$ and $V_3=5$
$U_6=1$ and $V_6=10$
$U_7=0$ and $V_7=11$
$U_{14}=0$ and $V_{14}=2$

There's two ways the number can be a pseudoprime 1) $U_d \equiv 0 \pmod{n}$ and $V_d \equiv 2 \pmod{n}$; or 2) $V_{d2^r} \equiv 0$ for $0 \leq r < s$

We have $14=2\cdot7$ so $d=7$ For 1) $U_7$ is congruent to 0 but the second necessary condition, $V_7$ isn't congruent to 2. For 2) $V_7$ is considered again but still $11$ isn't congruent to $0 \bmod 13$. Since neither of these congruence hold, the test gives composite.

What is wrong with what I have done?

I have heard that the extra strong test is faster than the strong test. Is this true? I find it unlikely since it has an additional condition that must be checked, but maybe something to do with the parameters makes it end earlier.

Answer 1

You're missing the $\pm$ on the $2$ in the first condition.

A number $n$ passes the test if one of the following conditions holds:

1. $U_d \equiv 0 \pmod n$ and $V_d \equiv \pm 2 \pmod n$.
2. $V_{d \cdot 2^r} \equiv 0 \pmod n$ for some $r$, $0 \le r < s$.

In your case, $U_7 \equiv 0 \pmod{13}$ and $V_7 \equiv 11 \equiv -2 \pmod{13}$, so the first condition holds.

Answer 2

The test requires a larger power of 2.

Essentially, you are looking to see if a prime 7 mod 24 is prime, the period of this divides p+1. 14 is not of this form. You might use with 4807.

The prime test involved here is essentially the same as if $p \mid b^{p-1}-1$, for some base b, then p is a pseudoprime.

The inclusion of the jacobi determinate also includes the class-2 criterian (that $p \mid b\^\^p - b), where the double-carat represents the nth term of t_0=2, t_1=b, t(n+1)=b.t(n)-t(n-1).

The jacobi is not really necessary here, as the value at p is ascending or descending as the period is upper or lower. The same algorithm has been used to search for instances where $p^2\mid b\^\^p - b$.

The actual isopower (which is what the ^^ is called), can be calculated at 3/2 of the speed of the ordinary power, and serching for $b$ rather than the period-marker $2$, means that there is no need to evaluate the Jacobi.

The power of 2 condition seems to be being used because the mathematicians do not have a general algorithm for finding isopowers. It's not needed.