The deck
Factor a number
The Clay Mathematics Institute once ran a poster in the Boston subway with an encrypted message on it, back when the reassuring line of the day was that the sun would burn out before serious encryption could be broken. The poster was right about its own key and wrong about the era — and the difference between those two is a storage bill.
That is this page's whole argument: a precomputed library of primes converts an arithmetic problem into a storage problem, and storage gets cheaper on a schedule. Behind this page sits a verified library of 1.6 billion consecutive primes, built one at a time and checked against itself, still growing. The table further down says what that means in dollars. The box below says it in microseconds.
try:
starting the deck scan…
Where this came from
Greg and I were working the ROME contract at NASA Langley when a colleague, Ian, put up a Chuck Norris facts site and it took a million hits in its first month, entirely on material sent in by strangers. We built the Vin Diesel and Mr. T versions to find out whether that was the character or the mechanism. It was the mechanism.
Around 2007 we turned the same question on primes: not whether one machine could factor something, but whether the work could be laid out ahead of time and shared. The deck behind this page is that question, still running. And what it showed is the argument at the top of this page — precomputation converts arithmetic into storage. Here is what the conversion costs.
Arithmetic into storage
A complete deck reaching the square root of a modulus, at one byte per prime:
| Modulus | Primes needed | Deck size | Single-core sieve time |
|---|---|---|---|
| 70 bit | 1.5 billion | 1.5 GB | 49 minutes |
| 90 bit | 1.2 trillion | 1.2 TB | 27 days |
| 128 bit | 426 quadrillion | 426 PB | 27,000 core-years |
| 160 bit | 22 sextillion | 22 ZB | 1.4 billion core-years |
| 305 bit — the Clay key | 77 tredecillion | 7.7 × 1019 YB | 3.5 × 1020 × the age of the universe |
Sizes computed with li(x) and validated against the real deck to 0.0004%.
Read down the deck-size column. A library of primes is buildable right up to about 128 bits and falls off a cliff immediately after. 426 petabytes is roughly $6 million of disk — a procurement decision, not a physics one — and 100,000 cores sieve it in about three months. At 2007 prices the same library was about $166 million. Storage gets cheaper on a schedule; the sun was never the relevant clock.
Then the cliff. Two more doublings of the modulus and the deck for the Clay key is not a bigger disk order — it is 390 billion times all the storage on Earth.
Five methods, and the sense to switch
Nothing here relies on one trick. Every piece that comes back composite goes around a ladder until it is resolved or the tool admits it is beaten:
- The deck — trial division, which strips small factors outright and, when nothing divides, proves there is no small factor at all.
- Square-root-centred search — Fermat's method, whose cost depends on how close the two factors are. On a number whose factors sit near √n it lands in a step or two. When they are far apart it gives up quickly and says so.
- Pollard–Brent — whose cost depends on the smaller factor instead, so it wins in exactly the cases where the square-root search loses.
- A quadratic sieve, run through PARI/GP, for composites the first three rungs leave standing.
- An APRCL primality proof, for survivors too large for the deterministic primality test below to settle on its own.
Rungs two and three are opposites, and watching them trade places is the point. Paste the square-root special above and Fermat's search finds both factors one step above √n, in about a microsecond — the same split takes Pollard–Brent some twenty-four thousand times longer. Paste a number with one small factor and one enormous one and the positions reverse. Neither method is better; the shape of the number decides.
If every rung is exhausted the page says so plainly and states what is still known: how many bits, that it is composite, and that it has no prime factor below the deck's ceiling — which is a real constraint on where its factors can be, not a shrug.
What the deck can promise
The guarantee bound is 1,389,111,913,721,164,139,809 — the square of the largest prime in the deck. It does not limit what you may enter; it marks where the deck alone can promise a complete answer. Below it, an answer is provably complete: if a number that size had a prime factor larger than every prime in the deck, it would be forced to have a partner smaller than the deck's largest — and the deck would have caught it. So nothing can be hiding. Above the bound that promise lapses; the tool tries anyway, and whatever it finds is still proved — every factorisation is multiplied back and checked before it is shown to you.
And when the page says a piece is prime, it says which kind of certainty it means. Below 3.32 × 1024, a deterministic Miller–Rabin test over thirteen bases is a proof outright. Above that line the same test only makes a number probable — and the honest word stays “probable” until the APRCL proof on the fifth rung has certified it.
The deck's own contribution is the part nobody else can offer: it can tell you which prime each factor is, counting from 2. And if you press the second button, it will do the whole job the honest slow way — dividing by every prime in turn — so you can watch how much longer that takes. That gap is the entire argument. Building a library of primes is enormously expensive and pays back only across many questions, never on a single one.
What it cannot do, and why that is the point
Then there is the poster's key itself: a 305-bit RSA modulus. Paste it and the page will try — the arithmetic no longer tops out, it shifts to arbitrary precision and keeps going — but the key sits on the far side of the cliff in the table above. Against a library of primes, the reassuring line of the day holds: the sun really does burn out first.
The trouble is that the poster was not offering the kind of key that line was coined for. Nobody is brute-forcing a 128-bit symmetric key — 2128 was safe then and is safe now. A 305-bit RSA modulus rests on factoring instead, which is a different problem with a different history: RSA-100, a larger number at 330 bits, had already been factored in April 1991, before the poster was printed, and today cado-nfs factors RSA-100 in 7 minutes 42 seconds on a six-core consumer desktop CPU. Right about its own number against this page's whole method; wrong about the decade before the ink was dry.
The poster this came from
Two of the numbers on it are worth pasting into the box at the top.
The first, 1234567 = 127 × 9721, is the poster's teaching example — the easy case, shown so the hard one lands.
The second is the one it leaves open: 1020030004000050000060000007 = ? × ? × ? … It is ninety bits, which is above this deck's guarantee. Paste it anyway. Every one of its six prime factors is in the library — the largest, 12,373,564,559, sits comfortably below the largest prime here. The guarantee and the capability are not the same thing, and this is the number that proves it.
How the library has grown
When this page first went up, the library held eight hundred million primes. It holds billions now, and it is still growing as you read this — a sieve works away on the same server, held to a small share of the machine so it never crowds the sites it shares with, and it marks the chart below for every hundred million primes it adds. Each mark lifts the guarantee bound: the largest number the deck can take apart with a promise that nothing was missed. The line only goes one way.
The largest numbers this page has taken apart
Every number factored here that is big enough to be worth keeping lands on this list, largest first — with the primes the page pulled out of it and the bit-length it ran to. The Clay poster's own line stays pinned at the top, whatever else arrives; it is the one that started all of this.