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=721 gives d=7 and s=1.
set P=3,Q=1,D=324=5

U1=1 and V1=P=3
U2=3 and V2=7
U3=8 and V3=5
U6=1 and V6=10
U7=0 and V7=11
U14=0 and V14=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.


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.

Source : Link , Question Author : northerner , Answer Author : Misha Lavrov

Leave a Comment