# 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 $$1313$$ is prime but the test gives composite. Here is what I tried:

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

$$U1=1U_1=1$$ and $$V1=P=3V_1=P=3$$
$$U2=3U_2=3$$ and $$V2=7V_2=7$$
$$U3=8U_3=8$$ and $$V3=5V_3=5$$
$$U6=1U_6=1$$ and $$V6=10V_6=10$$
$$U7=0U_7=0$$ and $$V7=11V_7=11$$
$$U14=0U_{14}=0$$ and $$V14=2V_{14}=2$$

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

We have $$14=2\cdot714=2\cdot7$$ so $$d=7d=7$$ For 1) $$U_7U_7$$ is congruent to 0 but the second necessary condition, $$V_7V_7$$ isn't congruent to 2. For 2) $$V_7V_7$$ is considered again but still $$1111$$ isn't congruent to $$0 \bmod 130 \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.

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

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

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

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