The Lucas–Lehmer Test

Every few years a press release announces the largest known prime — a number with tens of millions of digits that would fill a thick novel if printed. How do mathematicians actually verify something that enormous is prime?

The answer is the Lucas–Lehmer test, a deterministic algorithm custom-built for Mersenne numbers of the form $2^p - 1$. These are the only candidates large enough to routinely break records, and they possess a special arithmetic structure that makes a fast test possible.

The core idea dates to Édouard Lucas in 1878, was made rigorous by Derrick Henry Lehmer in 1930, and has been the engine of the Great Internet Mersenne Prime Search (GIMPS) since 1996. Every record prime discovered since 1952 — including the current champion — was certified by exactly this test.

The algorithm is stunning in its simplicity. Build a sequence $s_0 = 4$, $s_{k+1} = s_k^2 - 2 \pmod{2^p - 1}$. After $p - 2$ steps, if $s_{p-2} = 0$ then $2^p - 1$ is prime. That's it. No probabilistic hedging, no error probability — a single congruence decides the question forever.

Enter a prime exponent $p$ below and run the Lucas–Lehmer sequence. The tester computes $s_0 = 4$, $s_{k+1} = s_k^2 - 2 \pmod{2^p - 1}$ for $p - 2$ steps and checks whether the final value is $0$.

<p class="hint">{{hint}}</p>
<div class="controls">
  <label for="pInput">{{label_p}}</label>
  <input id="pInput" type="number" min="2" max="127" value="7" step="1" />
  <button id="runBtn" type="button">{{btn_run}}</button>
</div>
<div id="verdict" class="verdict"></div>
<div id="info" class="info"></div>
<div id="steps" class="steps"></div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .9rem; color: #444; margin: 0 0 .8rem; line-height: 1.5; }
.controls { display: flex; align-items: center; gap: .6rem; flex-wrap: wrap; margin-bottom: .8rem; }
label { font-size: .95rem; font-weight: 600; }
input[type=number] { width: 80px; font: 600 16px ui-monospace, monospace; padding: .35rem .5rem;
                     border: 1px solid #aaa; border-radius: 7px; text-align: center; }
button { font: 600 14px system-ui, sans-serif; padding: .45rem 1rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button:hover { background: #16294a; }
.verdict { font: 700 1.05rem/1.4 system-ui, sans-serif; min-height: 1.6em; margin-bottom: .4rem; }
.verdict.prime { color: #0a7d33; }
.verdict.composite { color: #c92f3c; }
.verdict.error { color: #b45309; }
.info { font-size: .85rem; color: #555; margin-bottom: .6rem; }
.steps { max-height: 200px; overflow-y: auto; border: 1px solid #ddd; border-radius: 8px;
         padding: .5rem .7rem; font: 13px/1.6 ui-monospace, monospace; background: #f8fafc; }
.steps:empty { display: none; }
.step-row { white-space: nowrap; overflow: hidden; text-overflow: ellipsis; }
.step-row.final { color: #0a7d33; font-weight: 700; }
.step-row.fail  { color: #c92f3c; font-weight: 700; }

// Code not found

Notice how the intermediate values can be enormous yet the test always reaches a clean verdict. Small values of $p$ finish instantly; try $p = 31$ or $p = 61$ (both prime exponents that yield Mersenne primes) and compare with $p = 11$ or $p = 23$ (composite Mersenne numbers). The test is deterministic — there are no false positives and no false negatives.

How fast is the Lucas–Lehmer test, really?

• Naively, each squaring $s_k^2 \pmod{2^p - 1}$ involves multiplying two $p$-bit numbers and reducing modulo $2^p - 1$. Schoolbook multiplication costs $O(p^2)$ bit operations, giving $O(p^3)$ total — already vastly better than trial division, which would need $O(2^{p/2})$ steps.
• With FFT multiplication, the squarings cost $O(p \log p \log \log p)$ each. Over $p - 2$ steps the total is $O(p^2 \log p \log \log p)$ bit operations — polynomial in the number of digits.
• Reduction mod $2^p - 1$ is free. A $2p$-bit product $A \cdot 2^p + B$ satisfies $A \cdot 2^p + B \equiv A + B \pmod{2^p - 1}$, so reduction is a single addition and comparison — no division needed.
• It is proven correct and complete. The Lucas–Lehmer theorem (proved by Lehmer, 1930; simplified proofs by many authors since) is an if and only if statement: $2^p - 1$ is prime exactly when $s_{p-2} \equiv 0 \pmod{2^p - 1}$. There is no gap, no exception.
• It only works for Mersenne numbers. The structure of $2^p - 1$ is what makes the sequence behave so cleanly. Applying the same idea to an arbitrary odd number requires a different (harder) test — see, for example, the general primality testing landscape.

In practice, a GIMPS volunteer's CPU takes a few weeks to certify a 100-million-digit Mersenne candidate. That is the polynomial-time miracle: a problem that looks astronomically large still bends to an efficient algorithm.

Mersenne primes are not just recreational mathematics — they connect to deep structures and practical systems:

• Perfect numbers: every even perfect number has the form $2^{p-1}(2^p - 1)$ where $2^p - 1$ is a Mersenne prime (proved by Euler). Finding Mersenne primes is the only known way to find even perfect numbers, and whether any odd perfect numbers exist remains one of the oldest open questions in mathematics.
• GIMPS: the Great Internet Mersenne Prime Search has run since 1996, coordinating volunteers' CPUs worldwide. It discovered the current record prime — $2^{136279841} - 1$ (41 million digits) — in October 2024. Every result is verified by two independent Lucas–Lehmer runs.
• Cryptographic parameter generation: large Mersenne primes occasionally serve as field moduli or group orders in cryptographic protocols where reduction speed (exploiting the $2^p - 1$ structure) is a priority.
• Algorithm benchmarking: because the test is compute-bound and well-defined, Lucas–Lehmer runs are used to stress-test CPUs and validate high-precision arithmetic libraries.
• Number theory education: the test is one of the cleanest examples of a deterministic polynomial-time result in number theory — a counterpoint to the probabilistic landscape of general primality testing.

The test also illustrates a broader principle: special structure in the input (Mersenne form) can unlock algorithms that are completely out of reach for general inputs. Recognizing and exploiting that structure is one of the deepest skills in algorithm design.

The Lucas–Lehmer test is a rare gift: a problem that looks impossibly hard — decide whether a number with tens of millions of digits is prime — yields to a short, provably correct algorithm because the input has exactly the right structure.

Start with $s_0 = 4$. Square, subtract two, reduce modulo $2^p - 1$. Repeat $p - 2$ times. If the result is zero, you have just certified a new record prime. If not, $2^p - 1$ is composite — no exceptions, no caveats, guaranteed.

That guarantee matters. In a world full of probabilistic tests and heuristic shortcuts, the Lucas–Lehmer test stands as a reminder that sometimes mathematics delivers absolute certainty — and that the search for structure is always worth the effort. The next record prime is out there, and a dedicated volunteer's PC will find it with exactly this algorithm.