The EFF Cooperative Computing Prime Prize

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.

Every record prime GIMPS has ever found has the shape $2^{p}-1$ for some prime exponent $p$ — 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">{{hint_para}}</p>
<div class="row">
  <label for="expSelect">{{label_exponent}}</label>
  <select id="expSelect"></select>
  <button id="run" type="button">{{btn_run}}</button>
</div>
<div class="status" id="status">{{status_idle}}</div>
<pre class="trace" id="trace"></pre>
<div class="chart-wrap">
  <p class="chart-title">{{chart_title}}</p>
  <div class="chart" id="chart"></div>
  <p class="chart-caption">{{chart_caption}}</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; }

// Code not found

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 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 $n$-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 $M_p = 2^{p}-1$, the Lucas-Lehmer test is dramatically faster in practice. Starting from $s_0 = 4$, it repeats $s_{i+1} = (s_i^2 - 2) \bmod M_p$ exactly $p-2$ times; $M_p$ is prime if and only if the final $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 $p$ to plug in, and even then most Mersenne numbers $2^{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 $2^{p}-1$ has about $p \cdot \log_{10}2 \approx 0.30103\,p$ digits. Hitting the EFF's 100,000,000-digit threshold needs an exponent $p$ around 332 million; the billion-digit prize needs $p$ 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.

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, $2^{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.

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.