Lucas-Lehmer Test

The Lucas-Lehmer test is an efficient method used to determine whether a Mersenne number \( M_p = 2^p - 1 \) is prime.

Mersenne numbers follow the form \( M_p = 2^p - 1 \), where \( p \) is a prime number.

The test consists of the following steps:

1. Initialization
   Start with \( S_0 = 4 \), the first term of the Lucas-Lehmer sequence.
2. Recursion
   Generate the sequence using the recurrence relation: $$ S_{n+1} = S_n^2 - 2 \pmod{M_p} $$ where \( M_p = 2^p - 1 \).
3. Iteration
   Repeat the recursion for \( p-2 \) iterations, from \( n = 1 \) to \( n = p-2 \).
4. Final check
   If \( S_{p-2} \equiv 0 \pmod{M_p} \), then \( M_p \) is prime. Otherwise, it is composite.

Note. The Lucas-Lehmer test is highly efficient, with relatively low computational complexity compared to other primality tests. However, it only applies to Mersenne numbers and cannot be used for general primality testing. For instance, 11 is prime but not a Mersenne number since it cannot be written as \( 2^p - 1 \).

Practical Example

Let's test the Mersenne number 31:

$$ M_5 = 2^5 - 1 = 31 $$

Here, \( p = 5 \).

We initialize the Lucas-Lehmer sequence:

$$ S_0 = 4 $$

The choice of 4 as the starting value is standard since it reliably produces a valid sequence for all Mersenne numbers.

Note. In theory, different starting values \( S_0 \) could be used, but not all will work correctly. Some may lead to sequences that fail to determine the primality of \( M_p \).

Now, we compute the sequence for \( p - 2 = 5 - 2 = 3 \) iterations:

$$ S_1 = (4^2 - 2) \mod 31 = 14 $$

$$ S_2 = (14^2 - 2) \mod 31 = 8 $$

$$ S_3 = (8^2 - 2) \mod 31 = 0 $$

Since \( S_3 \equiv 0 \mod 31 \), we confirm that \( M_5 = 31 \) is prime.

Example 2

Now, let's test the Mersenne number 2047:

$$ M_{11} = 2^{11} - 1 = 2047 $$

Here, \( p = 11 \).

We initialize the sequence:

$$ S_0 = 4 $$

Next, we compute the sequence for \( p - 2 = 11 - 2 = 9 \) iterations:

$$ S_1 = (4^2 - 2) \mod 2047 = 14 $$

$$ S_2 = (14^2 - 2) \mod 2047 = 194 $$

$$ S_3 = (194^2 - 2) \mod 2047 = 788 $$

$$ S_4 = (788^2 - 2) \mod 2047 = 701 $$

$$ S_5 = (701^2 - 2) \mod 2047 = 119 $$

$$ S_6 = (119^2 - 2) \mod 2047 = 1877 $$

$$ S_7 = (1877^2 - 2) \mod 2047 = 240 $$

$$ S_8 = (240^2 - 2) \mod 2047 = 282 $$

$$ S_9 = (282^2 - 2) \mod 2047 = 1736 $$

Since \( S_9 \neq 0 \mod 2047 \), we conclude that \( M_{11} = 2047 \) is not prime.

In fact, 2047 is composite: \( 2047 = 23 \times 89 \).

And so on.