The Classical Cipher: Why Our Computers Are Running Out of Steam

Imagine a line of soldiers, standing at attention, each holding a single flag that can only be waved in one of two ways: up or down. They are utterly predictable, moving in perfect, rigid response to a commander’s orders. This is the world of classical computing—a realm of absolute certainty, where every calculation is a march of these binary soldiers, step by step, through a landscape of 1s and 0s. For seventy years, this army has conquered astonishing peaks: it guides spacecraft across the solar system, translates human languages in real time, and defeats grandmasters at chess. Yet, there is a problem—a seemingly innocent puzzle—that brings this mighty force to a shuddering halt. It is a problem so simple to state that a child can understand it, yet so profound in its implications that it threatens to unravel the very foundations of our digital security. That problem is factoring a large number. And the story of why our binary soldiers fail at this task is the story of why we need a new kind of machine—a machine that does not march, but dreams.

The Binary Battalion: Soldiers of Determinism

To understand the impending crisis, we must first meet the troops. The fundamental unit of classical information is the bit—a contraction of "binary digit." A bit is a switch with two states: 0 or 1, off or on, false or true. Every piece of data in your computer—a photograph, a song, this very text—is ultimately a long, long string of these bits. Think of a bit as a single soldier in an enormous army. This soldier is not a free thinker; he or she follows one command at a time, with no ambiguity. The entire operation of a classical computer is the orchestration of billions of such soldiers, executing a pre-written script—an algorithm—with clockwork precision.

The commander of this army is the central processing unit (CPU). It fetches an instruction from memory, decodes it, and then dispatches orders to specific groups of bits. These orders are the basic logical operations: AND (both bits must be 1 to yield 1), OR (at least one bit is 1 to yield 1), NOT (flip the bit), and XOR (bits differ to yield 1). These are the only moves the soldiers know. From these simple, deterministic steps, all of modern computing is built. There is no probability, no superposition of states. A bit is either 0 or 1, never both. The entire computational process is a single, unwavering path through a vast decision tree. The computer is a master of brute force, but only within the strict confines of its binary logic.

This deterministic, step-by-step nature is both the strength and the Achilles' heel of classical computing. It is a strength because it guarantees correctness. If the algorithm is correct and the hardware functions, the answer will be right, every single time. There is no mystery, no uncertainty. But it is a weakness because the number of steps required to solve a problem can grow inhumanly fast as the problem size increases. The soldiers must physically traverse each step of the path. If the path is long, the journey takes a long time. And for some problems, the path is not just long—it is astronomically, cosmically long.

The Deceptively Simple Puzzle: Factoring

Let us meet our adversary: integer factorization. Given a positive integer *n*, find its prime factors. For example:

• 15 = 3 × 5
• 21 = 3 × 7
• 91 = 7 × 13

These are trivial. A child can factor them in their head. The algorithm is conceptually straightforward: try dividing *n* by every integer *d* from 2 up to √*n*. The first *d* that divides *n* evenly is a factor; you then repeat the process with the quotient. This is called trial division. For a small number like 91, √91 is about 9.5, so you only need to test 2, 3, 4, 5, 6, 7, 8, 9. Seven works, and you’re done. The computational cost is tiny.

Now, consider a number that is 100 digits long. √*n* is a number with 50 digits. How many trial divisions would that require? In the worst case, you might have to test nearly every integer up to that 50-digit number. The number of atoms in the observable universe is estimated to be around 10^80—a 1 followed by 80 zeros. A 50-digit number is on the order of 10^50. So, for a 100-digit number, trial division could require up to 10^50 tests. That is a 1 followed by 50 zeros. To put this in perspective: if your classical computer could perform a trillion (10^12) trials per second—which is extraordinarily fast—it would still take about 10^28 seconds to complete. The age of the universe is roughly 4 × 10^17 seconds. You would need more time than the universe has existed, by a factor of 10 billion billion. The binary soldiers would still be marching, long after the stars have burned out.

This is not just a hypothetical. This exact problem—factoring large numbers—is the cornerstone of modern cryptography. The security of your online banking, your private messages, and your digital identity rests on the assumption that factoring a specific type of large number (a product of two large primes) is computationally infeasible for any classical computer. The algorithm that underpins this security is RSA, named after its inventors Rivest, Shamir, and Adleman. RSA works by taking two large, random prime numbers (each hundreds of digits long), multiplying them together to create a public key, and keeping the primes secret as the private key. Anyone can encrypt a message with the public key, but only someone who knows the prime factors can decrypt it. The security of the entire system hinges on the fact that no classical algorithm can factor that product in any reasonable amount of time.

In 1994, mathematicians factored a 129-digit number, known as RSA-129, which had been published as a challenge in 1977. It took a global effort of hundreds of volunteers using the Multiple Polynomial Quadratic Sieve (MPQS) algorithm, coordinated over the internet. The computation took about 8 months. That was for a 129-digit number. Today, the standard for secure RSA keys is 2048 bits, which is a number with about 617 decimal digits. The largest RSA number factored to date is RSA-250, a 250-digit (829-bit) number. In February 2020, a team announced its factorization. The effort required a massive, optimized implementation of the General Number Field Sieve (GNFS), the most powerful classical factoring algorithm known. It used roughly 2700 core-years of computing time. That is equivalent to a single CPU core running continuously for 2700 years. For a 617-digit RSA-2048 number, estimates suggest it would take a classical supercomputer millions of years using the best known algorithms. The binary soldiers are simply overwhelmed by the scale of the search space.

The Algorithmic Struggle: From Brute Force to Elegant Despair

Faced with the absurdity of trial division, computer scientists and mathematicians have developed far more sophisticated algorithms. The evolution of factoring algorithms is a tale of relentless ingenuity, a battle waged not with more soldiers, but with smarter strategies. Yet, every victory is pyrrhic; each new algorithm merely delays the inevitable exponential wall.

The first major improvement beyond trial division was Fermat’s factorization method (17th century). It exploits the fact that if *n* = *p* × *q* and *p* and *q* are close to each other, then *n* can be expressed as the difference of two squares: *n* = *a*² - *b*² = (*a* - *b*)(*a* + *b*). You start with *a* = ceil(√*n*) and increment *a* until *a*² - *n* is a perfect square. This works brilliantly if the factors are near √*n*, but fails catastrophically if they are far apart—which is exactly what good cryptography forces them to be (primes chosen randomly are unlikely to be close).

The true classical workhorses are sieve-based methods. The Quadratic Sieve (QS), developed in the 1980s, and its more powerful descendant, the Multiple Polynomial Quadratic Sieve (MPQS), work by find