Introduction

Since 1999, the Electronic Frontier Foundation has run a standing bounty for record-breaking prime numbers, under a program called the Cooperative Computing Awards. The rules are refreshingly simple: find a prime number with enough digits, and the EFF cuts you a check.

Two tiers have already been won. In 1999 a 1,000,000-digit prime earned its finder $50,000; in 2008 a 10,000,000-digit prime earned $100,000. Both wins came from the same source: GIMPS, the Great Internet Mersenne Prime Search, a volunteer network that has donated spare computer cycles to prime-hunting since 1996.

Two prizes remain completely unclaimed. The EFF will pay $150,000 for the first prime with at least 100,000,000 digits, and $250,000 for the first with at least 1,000,000,000 digits. As of today, the largest prime ever found — discovered in 2024 — has only about 41 million digits: further along than the 10-million mark, but still less than half the digits the next prize demands.

Try It: Hunt a Mersenne Prime

Every record prime GIMPS has ever found has the shape 2p−12^{p}-1 for some prime exponent pp — a Mersenne number. Pick a small exponent below and run the Lucas-Lehmer test, the same test that certifies real record primes, just at a size your browser can handle instantly.

<p class="hint">Every known record prime has the form $2^p - 1$ (a Mersenne number) for a prime exponent $p$. Pick an exponent and run the Lucas-Lehmer test — the exact same test GIMPS runs on numbers with tens of millions of digits, just small enough here to finish instantly.</p>
<div class="row">
  <label for="expSelect">Exponent p:</label>
  <select id="expSelect"></select>
  <button id="run" type="button">Run Lucas-Lehmer test</button>
</div>
<div class="status" id="status">Pick an exponent and run the test.</div>
<pre class="trace" id="trace"></pre>
<div class="chart-wrap">
  <p class="chart-title">Record prime sizes vs. the two unclaimed EFF prizes</p>
  <div class="chart" id="chart"></div>
  <p class="chart-caption">Bars use a logarithmic scale (each step up is 10x more digits). The striped red bars are the EFF’s remaining $150,000 (100,000,000-digit) and $250,000 (1,000,000,000-digit) thresholds — both still unclaimed.</p>
</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 .7rem; line-height: 1.45; }
.row { display: flex; align-items: center; gap: .6rem; flex-wrap: wrap; margin-bottom: .6rem; }
label { font-size: .9rem; font-weight: 600; color: #1d3557; }
select { font: 600 14px ui-monospace, monospace; padding: .35rem .5rem; border-radius: 6px;
          border: 1px solid #adb1b8; background: #fff; }
button { font: 600 14px system-ui, sans-serif; padding: .45rem .9rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
.status { font-size: 1rem; font-weight: 600; margin: .5rem 0; min-height: 1.4em; }
.status.ok { color: #0a7d33; }
.status.bad { color: #c92f3c; }
.trace { background: #eef1f4; border: 1px solid #cdd9e3; border-radius: 8px; padding: .55rem .7rem;
         font: 12px ui-monospace, monospace; max-height: 110px; overflow: auto; white-space: pre-wrap;
         word-break: break-all; margin: 0 0 .8rem; color: #333; }
.chart-wrap { border-top: 1px dashed #cdd9e3; padding-top: .7rem; }
.chart-title { font-size: .85rem; font-weight: 700; color: #1d3557; margin: 0 0 .5rem; }
.chart { display: flex; align-items: flex-end; gap: 10px; height: 130px; padding: 0 .2rem; }
.bar-col { display: flex; flex-direction: column; align-items: center; justify-content: flex-end;
           height: 100%; flex: 1; }
.bar { width: 100%; max-width: 34px; background: #457b9d; border-radius: 4px 4px 0 0; position: relative; }
.bar.prize { background: repeating-linear-gradient(45deg, #e63946, #e63946 5px, #f2818b 5px, #f2818b 10px); }
.bar-label { font-size: .62rem; color: #444; margin-top: .3rem; text-align: center; line-height: 1.2; }
.chart-caption { font-size: .78rem; color: #555; margin: .5rem 0 0; line-height: 1.4; }

const i18nFmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));

// Lucas-Lehmer test: for a Mersenne candidate M = 2^p - 1 with p prime,
// define s_0 = 4 and s_(i+1) = (s_i^2 - 2) mod M; M is prime iff s_(p-2) = 0.
function lucasLehmer(p) {
  if (p === 2) return { prime: true, steps: [] }; // p=2 gives M=3, prime by inspection (loop would run 0 times anyway).
  const M = (1n << BigInt(p)) - 1n;
  let s = 4n;
  const steps = [];
  for (let i = 0; i < p - 2; i++) {
    s = (s * s - 2n) % M;
    if (i < 6 || i >= p - 3) steps.push(s.toString()); // only keep the first few and last few residues so the trace stays short.
  }
  return { prime: s === 0n, steps, M };
}

// Small prime exponents to try (mix of real Mersenne primes and composites).
const EXPONENTS = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31];

function digitsOf(p) {
  // digit count of 2^p - 1 is floor(p * log10(2)) + 1.
  return Math.floor(p * Math.log10(2)) + 1;
}

function populateSelect() {
  const sel = document.getElementById('expSelect');
  EXPONENTS.forEach((p) => {
    const opt = document.createElement('option');
    opt.value = String(p);
    opt.textContent = i18nFmt(`p = %p% (M has %d% digit(s))`, { p, d: digitsOf(p) });
    sel.appendChild(opt);
  });
  sel.value = '7';
}

function setStatus(t, cls) {
  const s = document.getElementById('status');
  s.textContent = t;
  s.className = 'status ' + cls;
}

function run() {
  const p = Number(document.getElementById('expSelect').value);
  const { prime, steps, M } = lucasLehmer(p);
  const trace = document.getElementById('trace');
  const mStr = M !== undefined ? M.toString() : '3';
  const shownSteps = steps.length ? steps.join(', ') : '(' + `no iterations needed for p=2` + ')';
  trace.textContent = i18nFmt(`Testing M = 2^%p% - 1 = %m%. Lucas-Lehmer sequence (mod M): %steps%`, { p, m: mStr, steps: shownSteps });
  if (prime) setStatus(i18nFmt(`✓ 2^%p% - 1 IS prime (Lucas-Lehmer residue = 0).`, { p }), 'ok');
  else setStatus(i18nFmt(`✗ 2^%p% - 1 is NOT prime (Lucas-Lehmer residue ≠ 0).`, { p }), 'bad');
}

// Real GIMPS/Mersenne record-prime digit counts plus the two unclaimed EFF thresholds.
const RECORDS = [
  { label: `1996
(420,921 digits)`, digits: 420921 },
  { label: `2008
(~13M digits, $100k won)`, digits: 12978189 },
  { label: `2018
(~25M digits)`, digits: 24862048 },
  { label: `2024
(~41M digits, current record)`, digits: 41024320 },
  { label: `$150,000 prize
(100,000,000 digits)`, digits: 100000000, prize: true },
  { label: `$250,000 prize
(1,000,000,000 digits)`, digits: 1000000000, prize: true }
];

function renderChart() {
  const chart = document.getElementById('chart');
  chart.innerHTML = '';
  const max = Math.max(...RECORDS.map((r) => r.digits));
  RECORDS.forEach((r) => {
    const col = document.createElement('div'); col.className = 'bar-col';
    const bar = document.createElement('div'); bar.className = 'bar' + (r.prize ? ' prize' : '');
    // log scale so a 1000x range of digit counts still fits on one chart.
    const pct = Math.max(3, (Math.log10(r.digits) / Math.log10(max)) * 100);
    bar.style.height = pct + '%';
    bar.title = i18nFmt(`%n% digits`, { n: r.digits.toLocaleString() });
    const label = document.createElement('div'); label.className = 'bar-label'; label.textContent = r.label;
    col.appendChild(bar); col.appendChild(label);
    chart.appendChild(col);
  });
}

populateSelect();
renderChart();
document.getElementById('run').addEventListener('click', run);
Result
Console

Then look at the chart of real record-prime sizes over time. The bars for 100,000,000 digits and 1,000,000,000 digits mark the two unclaimed EFF prizes — notice how far the tallest bar of actual discoveries still falls short of even the smaller one.

The Real Complexity

The EFF prize sounds like it is about size, but the real difficulty is about search, not verification.

  • Checking is fast, for the numbers that matter. A general primality test on an arbitrary nn-digit number is already efficient — primality testing has been known to run in polynomial time since the AKS algorithm (2002). But GIMPS doesn't even need that: for a candidate of the special form Mp=2p−1M_p = 2^{p}-1, the Lucas-Lehmer test is dramatically faster in practice. Starting from s0=4s_0 = 4, it repeats si+1=(si2−2) mod Mps_{i+1} = (s_i^2 - 2) \bmod M_p exactly p−2p-2 times; MpM_p is prime if and only if the final sp−2≡0(modMp)s_{p-2} \equiv 0 \pmod{M_p}. No trial division, no guesswork — one deterministic loop settles the question.
  • Finding a candidate worth testing is the expensive part. Lucas-Lehmer only applies once you already have a prime exponent pp to plug in, and even then most Mersenne numbers 2p−12^{p}-1 turn out composite. There is no known shortcut that jumps straight to "the next Mersenne prime" — you must generate exponent after exponent and run the full test on each, and the arithmetic itself grows brutally: multiplying numbers with tens of millions of digits, over and over, even with the fastest known multiplication algorithms.
  • Digits scale roughly with the exponent. A Mersenne number 2p−12^{p}-1 has about p⋅log⁡102≈0.30103 pp \cdot \log_{10}2 \approx 0.30103\,p digits. Hitting the EFF's 100,000,000-digit threshold needs an exponent pp around 332 million; the billion-digit prize needs pp around 3.32 billion. Each jump in exponent roughly doubles or triples the cost of every Lucas-Lehmer iteration, on numbers that already dwarf anything in daily computing.
  • So it is a race against a moving, unproven frontier. Nobody has proved infinitely many Mersenne primes exist, so nobody can even guarantee the prize is winnable in principle — GIMPS simply keeps testing exponent after exponent, distributed across tens of thousands of volunteer computers, and waits.

That is the punchline: verifying one specific giant number is a solved, efficient problem, but discovering which giant number to verify next has no known efficient strategy at all.

Where It Matters

Hunting record primes looks like pure recreation, but the machinery built to do it powers real infrastructure:

  • Cryptography: large primes are the raw material of RSA keys and Diffie-Hellman key exchange; Mersenne-shaped numbers in particular show up in fast modular-arithmetic tricks used across cryptographic libraries.
  • Pseudorandom number generators: the widely used Mersenne Twister generator takes its name and its enormous period, 219937−12^{19937}-1, directly from a Mersenne prime.
  • Fast multiplication: squeezing a Lucas-Lehmer test on a hundred-million-digit number to run in reasonable time relies on the same fast multiplication algorithms — Fast Fourier Transform–based methods — that also speed up scientific computing and cryptography at large.
  • Distributed and volunteer computing: GIMPS is one of the longest-running citizen-science computing grids, a proof of concept for coordinating strangers' idle CPUs later reused by projects across many fields.

Understand why the EFF prize is hard and you've met the same computational core behind factoring and every system that leans on the asymmetry between generating and verifying huge numbers.

Conclusion

The EFF has already paid $50,000 and $100,000 for record primes, proof that the bounty is real and the search works. But the two prizes that matter most today — $150,000 for 100 million digits, $250,000 for a billion — sit unclaimed, and the current record of roughly 41 million digits shows just how much distance is still on the table.

None of that gap comes from checking being hard: the Lucas-Lehmer test settles any single candidate cleanly and quickly. It comes from having no shortcut to the next candidate worth checking at all — a small, satisfying instance of how much harder it is to search a space than to confirm a single point inside it, echoing the same gap that shows up across P vs NP.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/eff-prime-prize/Content licensed under CC BY-NC 4.0.