Lucas-Lehmer Test

Purpose: Decide whether a Mersenne number $M_p=2^p-1$ (with $p$ prime) is prime, deterministically, in $O(p^2)$ bit operations — or $O(p\log p\log \log p)$ with FFT multiplication.

The Test

Define the sequence
$s_0=4,s_{i+1}=s_i^2-2.$

Then for odd prime $p$:
$M_p=2^p-1\text{ is prime}⟺s_{p-2}\equiv 0(\mathrm{mod}{M}_p).$

Code

def lucas_lehmer(p):
    if p == 2: return True          # M_2 = 3 is prime
    M = (1 << p) - 1
    s = 4
    for _ in range(p - 2):
        s = (s * s - 2) % M
    return s == 0

Reduction without division

Because $2^p\equiv 1(\mathrm{mod}{M}_p)$, reducing mod $M_p$ is a shift-and-add:

def mod_mersenne(x, p, M):
    while x > M:
        x = (x & M) + (x >> p)
    return x - M if x == M else x

This is why the test is so cheap per step — no division at all.

Complexity

• $p-2$ iterations, each one squaring of a $p$-bit number
• Schoolbook: $O(p^2)$ per step → $O(p^3)$ total
• With FFT/IBDWT multiplication: $\tilde{O}(p)$ per step → $\tilde{O}(p^2)$ total

For $p\approx 8\cdot 10^7$ (the current record region) this is days of GPU time per candidate — which is exactly what GIMPS, the Great Internet Mersenne Prime Search, distributes across volunteers.

Why It Works (sketch)

Work in $\mathbb{Z}[\sqrt{3}]$ and set $\omega =2+\sqrt{3}$, $\bar{\omega }=2-\sqrt{3}$, so $\omega \bar{\omega }=1$. Then
$s_i={\omega }^{2^i}+{\bar{\omega }}^{2^i}.$
The condition $s_{p-2}\equiv 0(\mathrm{mod}{M}_p)$ is equivalent to ${\omega }^{2^{p-1}}\equiv -1$, which says the order of $\omega$ in the multiplicative group modulo $M_p$ is exactly $2^p$. Such an element can exist only if the group is large enough, forcing $M_p$ to be prime; conversely, when $M_p$ is prime, 3 is a quadratic non-residue mod $M_p$ (since $M_p\equiv 7(\mathrm{mod}12)$), and a Frobenius argument gives the required order.

Facts worth knowing

• $M_p$ can only be prime if $p$ itself is prime (if $p=ab$, then $2^a-1\mid 2^p-1$). The converse fails: $M_{11}=2047=23\cdot 89$.
• Only 52 Mersenne primes are known. The largest known prime has been a Mersenne prime almost continuously since 1952, entirely because of this test.
• Every even perfect number is $2^{p-1}(2^p-1)$ with $M_p$ prime (Euclid-Euler), so Mersenne primes and even perfect numbers are in bijection.

Variants / Use Cases

• Lucas-Lehmer-Riesel test — the analogue for numbers of the form $k\cdot 2^n-1$
• Pépin’s test — the corresponding deterministic test for Fermat numbers $2^{2^n}+1$
• Miller-Rabin — the general-purpose test; use it for anything not of Mersenne form
• Primality Testing — the topic page