How to find first term in sequence for Lucas Lehmer Riesel test

Question

I'm trying to do the Lucas Lehmer Riesel primality test. It works on numbers of the form $k \cdot 2^n-1$ with $k<2^n$. The test basically involves calculating a term in a sequence and checking if the number being tested divides it. The Wikipedia article seems to be missing a step and I'm hoping someone can fill it in:

It says to find a $P$ that satisfies the Jacobi Symbols $(\frac{P-2}{N})=1$ and $(\frac{P+2}{N})=-1$

Then it states "To find the starting value $u_o$ from the $P$ value we can use a Lucas($P$,$1$) sequence, as shown in 2 as well as page 124 of.3 "

I think what it's saying is to do the Lucas sequence with parameters $P$ and $1$ but how do you know what term to go up to? I'm guessing some term is the value of $u_o$? Also is it the $U$ or $V$ sequence?

Note that if $k=1$ or $k=3$ then there are other techniques for determining the starting value.

Answer 1

You have converted the input $N$ into the form $k \cdot 2^n-1$. That's the $k$ being discussed.

The value you want is $V_k(P,1)$ as stated in the article.

The sentence before that, "The latter explains that when $3\nmid k$, $P=4$ may be used, hence the earlier search is not necessary." is a standalone sentence that just clarifies that there is a shortcut in that case.

The entire process to select the starting value is:

1. If $k$ is not divisible by 3, then $u_0 = V_k(4,1)$.
2. Otherwise, if $k = 3$ and $n = 0 \pmod 4$ or $n = 3 \pmod 4$, then $u_0 = 5778$.
3. Otherwise, perform the search for P using the Jacobi symbols, then $u_0 = V_k(P,1)$.

Assuming you have a function to do the modular Lucas sequence, the whole thing is on the order of 16 lines of GMP code. Then the test itself is about 5 lines (loop from 3 .. n inclusive performing u=u^2-2 mod n).

Some of the confusion is that there was an original version with just the bullet points that follows Riesel and ends up with "if it isn't one of the easy cases it's really complicated." I didn't want to completely erase that, but since there is a fairly straightforward and complete solution that verifiable works, it made sense to add it. It might be better if separated out more firmly into Method 1 (Riesel) and Method 2 (Rödseth).