Multiplying two 300-digit primes together is the work of an instant — your phone does it before you lift your finger. Splitting the resulting 600-digit number back into those two primes, with no hint about what they were, is a task that would keep every computer on Earth busy for longer than the age of the universe. Same two numbers, one operation and its inverse — yet one direction is trivial and the other is, as far as anyone knows, hopeless.

That gulf is not a curiosity; it is the foundation of RSA and much of the secure internet. The public key is a number n = pq, published for all to see; the private key is the pair (p, q), kept secret precisely because nobody can dig it out of n. Break the factoring problem and you break RSA. This page is the story of the best attacks we have — a ladder of ever-cleverer algorithms climbing toward the General Number Field Sieve, the champion for large numbers, and the quantum shortcut that could one day topple the whole edifice.

Two problems that look alike but aren't

First, the asymmetry that everything hangs on. Primality testing — deciding whether a number is prime — is easy: the Miller–Rabin test settles a 300-digit number in milliseconds, and the AKS test (2002) even does it in guaranteed polynomial time. Crucially, a primality test says "prime" or "composite" without ever producing a factor.

Factoring — actually splitting a composite n into its prime pieces — is believed to be hard. No polynomial-time classical algorithm is known, and the whole security of RSA is a bet that none exists. So we can effortlessly manufacture the giant primes RSA needs, and effortlessly multiply them, but not un-multiply the product. Encryption lives in that crack.

The first rungs: trial division, Pollard's ρ, Pollard's p−1

The naive attack is trial division: divide n by 2, 3, 5, \dots up to \sqrt n. Correct, and fine for small numbers, but a 300-digit n has \sqrt n with 150 digits — more divisions than there are atoms in the cosmos. We need cleverer ideas that don't march through every candidate.

Pollard's ρ is the first leap. Iterate a simple map like x \mapsto x^2 + c \pmod n and watch the values x_0, x_1, x_2, \dots. Modulo an unknown prime factor p, this sequence must eventually repeat, and by the birthday paradox a collision x_i \equiv x_j \pmod p turns up after only about \sqrt p steps — long before we'd ever see it modulo n. Each step we quietly compute \gcd(x_i - x_j,\, n); when it exceeds 1, out pops a factor. The cost is about \tilde O(n^{1/4}) = \tilde O(\sqrt p) — vastly better than \sqrt n, and it found the factor 1238926361552897 of the eighth Fermat number.

Pollard's p−1 is a specialist: it factors fast when some prime factor p has p-1 built only from small primes ("smooth"). It computes a^{M} - 1 \pmod n for a highly composite exponent M and takes a \gcd with n. This is exactly why RSA implementations choose safe primes, where p-1 has a large prime factor — to slam this door shut.

The big idea: a difference of squares

Every serious modern factoring algorithm — Dixon's method, the quadratic sieve, the number field sieve — is a variation on one beautiful trick. If we can find two numbers x and y with the same square mod n but which are not simply \pm each other, we win instantly.

Why it works: n divides the product (x-y)(x+y), but — since x \not\equiv \pm y — it divides neither factor by itself. So n's prime factors must be split between the two, and \gcd(x-y, n) scoops up the part living in x-y. The entire game is reduced to a scavenger hunt: find such a pair of squares.

Warm-up, n = 15. Notice 4^2 = 16 \equiv 1 = 1^2 \pmod{15}, and 4 \not\equiv \pm 1. So \gcd(4 - 1, 15) = \gcd(3, 15) = 3 — a factor, extracted without any dividing. Tiny, but it is exactly what the sieves do at scale.

Worked example: manufacturing squares from "smooth" relations

For real n we can't just spot a square — we build one. Take n = 1649. Square a few numbers just above \sqrt{1649} \approx 40.6 and reduce mod n, keeping only results that factor into small primes (these are called smooth):

Neither 32 nor 200 is a perfect square on its own. But multiply the two relations and the exponents add:

Now both sides are squares. On the left, 41\cdot 43 = 1763 \equiv 114 \pmod{1649}, so we have found x = 114, y = 80 with x^2 \equiv y^2. Since 114 \not\equiv \pm 80, the theorem fires:

That is the heart of every sieve. Collect many smooth relations x_i^2 \equiv (\text{small primes}), then find a subset whose product makes every prime's total exponent even — a perfect square. Choosing that subset is a problem of linear algebra over \mathbb{F}_2 (each relation is a vector of exponent parities; we seek a subset summing to the zero vector — a dependency). Solve the matrix, get a square, take a \gcd, done.

Dixon, the quadratic sieve, and the number field sieve

The three great algorithms differ only in how they gather smooth relations and over which numbers they hunt for smoothness:

• Dixon's method — pick x at random, hope x^2 \bmod n is smooth. Rigorous, but slow.
• Quadratic sieve (QS) — instead of random luck, sieve the polynomial Q(x) = (x + \lceil\sqrt n\rceil)^2 - n over a range of x, cheaply flagging which values are smooth (the same trick as the Sieve of Eratosthenes). Runtime L_n\!\left[\tfrac12,\ 1\right]. QS held the record through the 1990s and is still fastest below about 100 digits.
• General Number Field Sieve (GNFS) — the reigning champion for large n. It hunts for smoothness not among ordinary integers but among algebraic integers in a cleverly chosen number field, where the numbers involved are far smaller and smooth relations far more common. Same finish — a giant matrix over \mathbb{F}_2, then a \gcd — but a dramatically smaller exponent: L_n\!\left[\tfrac13,\ \left(\tfrac{64}{9}\right)^{1/3}\right], \qquad \left(\tfrac{64}{9}\right)^{1/3} \approx 1.923.

The table collects the ladder. Notice the jump in the first column — the \alpha in the L-notation — from 1 (exponential-ish) down to \tfrac13.

Reading the L-notation: what \tfrac12 vs \tfrac13 means

Subexponential runtimes live between polynomial and exponential, and we measure them on a single dial — the L-notation.

So the whole history of factoring is a slow slide of \alpha downward. Trial division sits near \alpha = 1. The quadratic sieve dragged it to \alpha = \tfrac12. GNFS pushed it to \alpha = \tfrac13 — still not polynomial (that would need \alpha = 0), but each drop is an enormous practical speed-up. The chart shows the estimated number of operations against the size of n: trial division rockets off the top, while GNFS stays comparatively flat.

The scoreboard, and the quantum cliff

The RSA Factoring Challenges turned all this theory into a public sport. RSA numbers are semiprimes n = pq published with a cash prize for whoever factors them. The current record is RSA-250 — a 250-decimal-digit (829-bit) number cracked in February 2020 with GNFS, consuming roughly 2700 core-years of computation spread across a cluster. The march is steady: RSA-129 fell in 1994, RSA-155 (512 bits!) in 1999, RSA-768 in 2009. The lesson for practice is blunt: 512- and 768-bit RSA are dead, and 1024 bits is retired; modern keys are 2048 or 3072 bits, sized to keep GNFS out of reach for decades.

But there is a cliff on the horizon. In 1994 Peter Shor found a quantum algorithm that factors in polynomial time (\alpha = 0, at last) by recasting factoring as period-finding and using the quantum Fourier transform to read off the period in one shot. A large enough fault-tolerant quantum computer would demolish RSA outright — no clever sieve required. The machines don't yet exist at the needed scale, but the mere possibility is why the world is migrating to post-quantum cryptography, built on problems (lattices, codes) that neither the number field sieve nor Shor's algorithm is known to break.