Fermat's
Clock

Take a clock with twelve hours. Add five hours to ten and you do not get fifteen — you get three, because the clock forgets every full turn. This is modular arithmetic, arithmetic that wraps, and it is the arithmetic in which the modern world keeps its secrets. Pierre de Fermat studied it in the 1640s for the pure pleasure of numbers; three and a half centuries later, three cryptographers at MIT turned one of its quiet asymmetries into the lock on nearly every private message ever sent. The whole edifice rests on a single lopsided fact: some sums on the clock are trivial to do forwards and monstrous to undo.

The lopsided fact is this. Multiply two large prime numbers together and you get their product in the time it takes to blink. But hand someone only that product and ask them to recover the two primes — to factor it — and you have set them a task that can outlast the sun. Multiplication is a one-way street. You can drive down it at once; the return trip, for a number of the right size, takes longer than the universe has existed.

"Multiplying is a stroll; factoring is a search of the whole world. The public key is the product, shouted to everyone. The private key is the pair of primes, and finding them again is the labour no one can afford." — after R. Rivest, A. Shamir & L. Adleman, 1977

I · The One-Way StreetEasy forward, impossible back

Below is the workbench of an attacker. Someone — call her Alice — chose two secret primes, multiplied them on her clock, and published only the product N as her public key. Her two primes are the hidden gears; you, the attacker, see only N. Your task is to run it backwards: factor N the most direct way there is, by trial division — testing N mod d for d = 2, 3, 5, 7, … until one divides evenly and the secret falls out. For a balanced product of two primes, you must climb roughly to √N before you succeed.

Start small and it works: a product of two-digit primes cracks before you can read this sentence, and Alice's gears spin open to reveal her secret. Then climb the key sizes. Somewhere around forty digits the estimated time slips past a human lifetime; by fifty-two digits it passes three billion years; and at the two-thousand-bit size that guards real traffic, the estimate is a number with hundreds of digits of its own. The animation is deliberately slowed so you can watch — but the clock in the corner tells the honest time an idealized machine would need, and it is telling you the truth about the abyss.

II · Cleverer Than Brute ForceWhy fifty digits is not enough

Trial division is the honest bound, not the last word. If it were, a fifty-digit key — three billion years to break, by the clock above — would be unbreakable, and yet a laptop factors fifty-digit numbers before lunch. The reason is that mathematicians have spent a century inventing ways to not search all the way to √N. John Pollard's rho method finds a factor in about N^¼ steps by hunting for coincidences in a random walk on the clock; his p−1 method and Hendrik Lenstra's elliptic-curve method exploit the hidden structure of the factors; and the quadratic and general number field sieves — the champions Knuth surveys in §4.5.4 — run in sub-exponential time, faster than any power of the digit count would suggest.

The size of a safe key is not set by how slow the dumbest attack is, but by how slow the cleverest known attack is. That is why RSA moved from 512 bits to 1024 to 2048 as the sieves improved — each a race against the mathematicians.

This is the sober correction to the instrument's drama: its "three billion years" is the cost of the naïve climb to √N, and the naïve climb is not what an adversary would do. Real security is calibrated against the number field sieve, which is why a genuinely safe modulus today is not fifty digits but six hundred — the RSA-2048 preset, a number whose factors have never been found by anyone, and whose owners, having multiplied them once, threw them away on purpose.

III · The Oldest Algorithm Guards the Newest SecretEuclid returns

Here is the turn that closes the circle back to the first room of this museum. To use her key, Alice needs a number d that undoes her public exponent e — a modular inverse, the value with e · d ≡ 1 on a clock of size φ(N). Computing it is not a matter of searching; it falls out instantly from the extended Euclidean algorithm — the very Bézout machinery you turned in Exhibit 1.1, which writes the greatest common divisor as a·s + b·t. Euclid, three hundred years before Christ, supplied the one step that makes RSA usable. The security rests on Fermat's clock; the key generation rests on Euclid's saw. The oldest algorithm we have quietly guards the newest secret we keep.

"An algorithm must be seen to be believed." — D. E. Knuth

And yet the trapdoor is not eternal. In 1994 Peter Shor showed that a large enough quantum computer could factor in time polynomial in the number of digits — running the return trip up the one-way street as easily as the trip down. No such machine yet exists at the required scale, but its shadow has already changed the field: the next generation of cryptography, the post-quantum schemes, are being built on different hard problems in anticipation. The clock still keeps our secrets tonight. Whether it keeps them a generation from now is the open question at the frontier — and the reason the study of what is easy, what is hard, and what merely looks hard has never mattered more.