What Is RSA Factoring, and Why Is It Hard?

RSA encryption — the algorithm behind a large share of internet security — relies on one asymmetry: multiplying two large prime numbers together is fast, but recovering those two primes from their product is, as far as anyone has proven, extremely slow. There’s no proof that factoring is fundamentally hard in the mathematical sense (that’s an open question in complexity theory), but decades of attempts have never found a fast general method — and that empirical track record is what the RSA Factoring Challenge was built to keep testing.

The challenge numbers

Starting in 1991, RSA Laboratories published a series of large numbers, each the product of exactly two large primes, and invited the public to factor them. Each number is named for its length in decimal digits — RSA-100, RSA-576, RSA-2048, and so on. The challenge officially ended in 2007, but the numbers, and the standing question of whether each has been factored, remain a de facto benchmark for how far factoring techniques have actually progressed.

Where the record stands

The largest challenge number factored to date is RSA-250, a 250-digit (829-bit) number, factored in February 2020 by a team — Fabrice Boudot, Pierrick Gaudry, Aurore Guillevic, Nadia Heninger, Emmanuel Thomé, and Paul Zimmermann — using the General Number Field Sieve, at a cost estimated around 2,700 CPU-core-years. RSA-260, the next number in the series, remains unfactored; estimates put it well beyond 10,000 core-years with current techniques.

Why the gap matters

The jump in difficulty from RSA-250 to RSA-260 isn’t small. The General Number Field Sieve’s running time grows sub-exponentially but still very steeply with the number of digits, which is exactly why RSA key sizes are chosen with a comfortable safety margin above the current factoring record rather than just above zero. Real-world RSA keys in use today (2048 bits and up) are dramatically larger than anything that’s ever been factored.

Why it’s here

Unlike a pure math conjecture, RSA factoring is a running, falsifiable benchmark: someone either publishes a factorization with a checkable certificate, or they don’t. That makes it an unusually clean thing to track — every RSA challenge number in the Registry carries its exact factoring status and, where it’s been broken, the paper and method that did it.