Why am I getting the wrong result when applying the extra strong Lucas pseudoprime test? 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. 
 A: 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:


*

*$U_d \equiv 0 \pmod n$ and $V_d \equiv \pm 2 \pmod n$.

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