Are there other ways of doing the Lucas -Lehmer primality test other than this?

Question

The usual ( but simple version) Lucas-Lehmer primality test, as done on Mersenne numbers ( of form $2^n-1$) is as follows:

$$s_0=4\\s_n=(s_{n-1})^2-2 \pmod {2^n-1}\\if\;s_{p-2}\equiv0\pmod{2^n-1}\\2^n-1\;is\;prime$$

Are there other ways to doing this tests ?

Answer 1

Yes, there are. First thing you will notice, is $2^n-1 \nmid2$ . This means, since every value of $s_n$ is even you can divide out the factor of two and it won't change which n values give a 0 result ( note: it will mess with the results for other values of n, as well as the values leading up to 0 in the new sequence). if we allow $y=x^2-2$ for a start and assume x is even, we get $y=4z^2-2$ for $z={x\over2}$ both parts of the difference divide by 2 and we get $y=2z^2-1$ our new start value will be 2. This is a bit more cumbersome to work with though.

Answer 2

There is a mathematical derivation of the Lucas-Lehmer test which hopefully should help you for understanding LLT/proof_of_correctness.

---

All we need to know is $ 3^{2^{p-1}-1} \equiv -1 \bmod 2^p -1$ if it is prime (a consequence of quadratic reciprocity, highly non-trivial).

Note that iff $2^p -1$ is prime then $\mathbb{Z}_{2^p-1}[\sqrt{3}] =\{ a+ b \sqrt{3}, (a,b) \in \mathbb{Z}/(2^p -1)\mathbb{Z}\}$ is a field with $(2^p-1)^2$ elements. Also :

$p | 2^{p-1} -1$ (Fermat little theorem) so that $2^{2^{p-1}-1} \equiv 1 \bmod 2^p -1$,

$2+\sqrt{3}= \frac{1}{2-\sqrt{3}}= \frac{(2.3+2 \sqrt{3})^2}{3 . 2^3}$.

• If $2^p -1$ is prime then $$(2.3+2 \sqrt{3})^{2^p-1} \underset{\text{(binomial theorem)}}{\equiv} (2.3)^{2^p -1} + (2\sqrt{3})^{2^p-1} \equiv 2.3-2\sqrt{3} \bmod 2^p-1$$

  thus $$(2+\sqrt{3})^{2^{p-1}} =\frac{(2.3+2 \sqrt{3})^{2^p}}{(3 . 2^3)^{2^{p-1}}}\equiv \frac{(2.3+2 \sqrt{3})(2.3-2\sqrt{3})}{-3. 2^3}\equiv -1 \bmod 2^p-1 \qquad \tag{1}$$ Note $(1)$ implies $S_{p-1} = (2+\sqrt{3})^{2^{p-1}} +(2-\sqrt{3})^{2^{p-1}} \equiv -2 \bmod 2^p-1 $ where $S_0 = 4,S_{n+1} = S_n^2-2=(2+\sqrt{3})^{2^{n}}+(2-\sqrt{3})^{2^{n}}$

• Now assume that $(1)$ is true but $2^p-1$ is not prime. Let $q$ be its least prime divisor so that $q^2 \le 2^p-1$. We obtain $$(1) \implies (2+\sqrt{3})^{2^{p-1}} \equiv -1 \bmod q$$ This implies $2^{p}$ is the multiplicative order of $2+\sqrt{3}$ in $\mathbb{Z}_q[\sqrt{3}]$. But its multiplicative group has $r$ elements, with $r \le q^2-1$. Whence we should have $$(2+\sqrt{3})^{r} \equiv 1 \bmod q$$ a contradiction since $r \le q^2-1 < 2^p$.