Shor’s Algorithm – The Quantum Algorithm That Threatens Modern Cryptography • GTech Booster

Few algorithms in the history of computer science have generated as much sustained attention outside of academic circles as Shor’s algorithm. It is the single result most frequently cited whenever someone explains why quantum computing matters for cybersecurity, why organizations are beginning to migrate toward post-quantum cryptography, and why RSA and elliptic curve cryptography, the two algorithm families underpinning most of the internet’s security today, are considered to have a genuine long-term expiration date. This article explains what Shor’s algorithm actually is, the mathematical problem it solves, why that problem matters so much for cryptography, how the algorithm works at a conceptual level, complete with the core equations involved, and where things actually stand today in terms of real-world quantum computers capable of running it at a meaningful scale.

Origins and Historical Context

Shor’s algorithm was developed by American mathematician Peter Shor, then working at Bell Labs, and published in 1994. At the time, quantum computing was still a largely theoretical field, with most researchers focused on proving what quantum computers could theoretically do in principle rather than actually building working machines capable of doing it. Shor’s result was a genuine watershed moment for the field because it demonstrated, for the first time, a concrete and practically important problem where a quantum computer could offer an exponential speedup over the best known classical algorithms, rather than merely a modest or theoretical advantage.

Before Shor’s paper, quantum computing was interesting primarily to physicists and theoretical computer scientists. After it, quantum computing became a matter of direct, urgent interest to governments, militaries, and the cryptographic community, because Shor had shown a plausible mathematical path toward breaking the security assumptions that essentially all modern public key cryptography depended on.

The Problems Shor’s Algorithm Actually Solves

Shor’s algorithm solves two closely related mathematical problems, both of which happen to be the exact hard problems that modern public key cryptography relies on for its security.

Integer factorization

The first and more famous application is integer factorization. Given a large composite number N that is the product of two prime numbers p and q, the goal is to find those two prime factors:

N = p × q

N is public. Finding the secret primes p and q from N alone is the problem believed to be computationally infeasible for large N.

For classical computers, no known efficient algorithm exists for this problem when N is sufficiently large, and the best known classical algorithms scale so poorly that factoring a sufficiently large number, such as the modulus used in a 2048-bit RSA key, is considered computationally infeasible with any classical computer that could plausibly be built, even accounting for continued hardware improvements over a very long time horizon. This difficulty is precisely why RSA is secure: the public key can be freely shared because recovering the private key requires factoring a number that is deliberately chosen to be far too large for any classical computer to factor in a practical amount of time.

The discrete logarithm problem

The second application, a closely related variant of the algorithm, solves the discrete logarithm problem. In its classical multiplicative form, given a generator g, a modulus p, and a value A, the problem is to find the secret exponent x such that:

A ≡ g^x (mod p)

Finding x from A, g, and p is the discrete logarithm problem. The elliptic curve version of this same problem, replacing modular exponentiation with repeated point addition on a curve, underlies ECDSA and Diffie-Hellman key exchange.

Just as with factoring, no efficient classical algorithm is known for solving discrete logarithm problems at the scale used in real-world cryptographic systems, and that difficulty is the entire basis for the security of those systems.

The significance of Shor’s algorithm is that it provides an efficient method for solving both of these problems on a sufficiently capable quantum computer, running in polynomial time, meaning the computational effort required grows manageably as the problem size increases, rather than exploding exponentially the way it does for the best known classical approaches. This is the specific property that makes Shor’s algorithm a genuine existential threat to RSA, Diffie-Hellman, DSA, and ECDSA alike, essentially the entire foundation of public key cryptography as it has been deployed for the past several decades.

How Shor’s Algorithm Actually Works

At a conceptual level, Shor’s algorithm works by cleverly transforming the factoring problem into a different problem, called period finding, that quantum computers happen to be exceptionally well suited to solving efficiently.

From factoring to period finding

The key mathematical insight is that factoring N can be reduced to finding the period of a function built from modular exponentiation. Pick a random integer a smaller than N. Define the function:

f(x) = a^x mod N

This function is periodic: it repeats after every r steps, where r is called its period, or order.

That periodicity means there exists a smallest positive integer r, the period, satisfying:

a^r ≡ 1 (mod N)

Once r is known, the factors of N can usually be recovered with simple classical arithmetic performed afterward.

If you can efficiently find that period r, you can use it to compute the factors of N through a relatively straightforward classical calculation. Specifically, when r is even and a raised to the power r over 2 is not simply -1 modulo N, the greatest common divisors below reveal the two factors:

gcd(a^r/2 − 1, N) and gcd(a^r/2 + 1, N)

Each of these greatest common divisor calculations, computed classically using the Euclidean algorithm, typically yields one of the two prime factors of N.

The genuinely hard part, the part classical computers struggle with, is finding r efficiently when N is large. Classical algorithms have no efficient way to do this, but a quantum computer does.

The quantum Fourier transform

This is where quantum mechanics does the heavy lifting. Shor’s algorithm prepares a quantum register in an equal superposition of many input values simultaneously, then evaluates f(x) into a second register, entangling the two. Measuring the second register collapses the first into a superposition of only those x values sharing the same f(x), which already carries hidden periodicity. The algorithm then applies the quantum Fourier transform, defined for a basis state as:

QFT|x⟩ = (1 / √N) Σ_y=0^N−1 e^2πi·xy/N |y⟩

The quantum Fourier transform converts periodicity in the input register into sharp, easily measured peaks in the output register, a task with no known efficient classical equivalent.

This step efficiently extracts the periodicity information needed to solve the original problem, in a way that has no efficient classical equivalent, because a classical computer would need to check the possibilities largely one at a time or in ways that do not scale nearly as well as the quantum approach. Measuring the transformed register yields a value strongly correlated with the period r, which classical post-processing, using continued fractions, then converts into the actual value of r.

Turning the period into the factors

Once the quantum computer has found the period r, the algorithm switches back to ordinary classical computation, using the gcd calculation shown above to recover the factors. If the specific run does not produce a usable factor, which can happen due to the probabilistic nature of quantum measurement or an unlucky choice of a, the algorithm is simply run again with a new random a, and repeated attempts converge quickly toward success.

This overall structure, using a quantum computer for the genuinely hard subproblem while relying on ordinary classical computation for the more straightforward surrounding steps, is a common and important pattern across many quantum algorithms, not just Shor’s, and reflects a realistic view of how quantum and classical computing are expected to work together in practice rather than quantum computers fully replacing classical ones for every task.

Why This Matters So Much for Cryptography

The practical implication of Shor’s algorithm is stark once you understand what it actually does. RSA’s security rests entirely on factoring N being hard. Diffie-Hellman, DSA, and ECDSA’s security all rest on some version of the discrete logarithm problem being hard. Shor’s algorithm efficiently solves both. This means that a sufficiently large, sufficiently reliable, fault-tolerant quantum computer running Shor’s algorithm could, in principle, recover an RSA private key from its corresponding public key, or recover an ECDSA private key from its public key, undermining essentially the entire foundation of how secure communication, digital signatures, and identity verification work across the modern internet, from HTTPS website encryption to secure messaging to software code signing to cryptocurrency wallets.

Crucially, and this point matters for understanding real-world risk correctly, larger classical key sizes do not meaningfully solve this problem the way they solve resistance against classical brute-force attacks. Doubling an RSA key from 2048 to 4096 bits meaningfully increases the effort required for a classical factoring attack, but it does not fundamentally change the outcome against a quantum computer running Shor’s algorithm, since the algorithm’s fundamental structure undermines the entire mathematical approach these systems depend on, rather than merely requiring proportionally more computational effort the way classical brute-force attacks do. This is precisely why simply using bigger RSA or ECDSA keys is not considered a viable long-term defense against the quantum threat, and why an entirely different category of algorithm, built on different underlying mathematical problems believed to remain hard even for quantum computers, is required instead.

The Current State of Real-World Quantum Computers

Here is where the picture becomes considerably more reassuring in the near term, and it is worth being precise about the current state of affairs rather than either dismissing the threat or overstating its immediacy.

Running Shor’s algorithm against a cryptographically meaningful number, such as an actual 2048-bit RSA modulus or a real-world elliptic curve private key, requires a quantum computer with an enormous number of high-quality, error-corrected logical qubits, generally estimated in published research to be in the range of several thousand to well over a million physical qubits, depending on the specific error correction approach assumed and the target key size, along with extremely low error rates sustained over long computation times. Actually building a quantum computer at that scale, with that level of reliability, remains a substantial unsolved engineering challenge.

Real-world demonstrations of Shor’s algorithm to date have been limited to factoring very small numbers, historically numbers like 15 and 21, using a handful of qubits under carefully controlled laboratory conditions, numbers trivially factorable by hand, let alone by an ordinary classical computer. Some experimental setups have used simplified or partially classical-assisted versions of the algorithm specifically tuned to factor a particular known small number, which further limits how directly those demonstrations translate into evidence about scaling toward cryptographically relevant key sizes. There is a substantial and widely acknowledged gap between these small-scale laboratory demonstrations and a quantum computer actually capable of threatening real-world RSA or ECDSA keys used in production systems today.

Current quantum computers, often described as being in the noisy intermediate-scale quantum era, remain limited by error rates and qubit counts that fall dramatically short of what full, fault-tolerant Shor’s algorithm execution against a real cryptographic key would require. Serious estimates from researchers in the field vary considerably on when, or even whether with currently understood approaches, a sufficiently capable machine will actually be built, with credible published timelines ranging from many years to multiple decades, and genuine scientific disagreement remaining about exactly how the engineering challenges involved will ultimately be resolved.

Why Organizations Are Preparing Anyway

Despite that meaningful gap between today’s quantum computers and a cryptographically relevant Shor’s algorithm attack, a significant and active effort is already underway across governments, standards bodies, and industry to migrate toward post-quantum cryptography, algorithms based on different mathematical problems believed to remain hard even for quantum computers, such as certain lattice-based, code-based, or hash-based cryptographic constructions.

This preparation reflects a specific and well-understood risk sometimes referred to as “harvest now, decrypt later.” An adversary can record encrypted communications or data today, store it, and simply wait until a sufficiently capable quantum computer eventually exists to decrypt that captured data retroactively. For data with a long required confidentiality lifetime, government secrets, long-term medical records, certain financial or legal records, this risk is meaningful today even though no quantum computer currently capable of executing the attack exists yet, precisely because the data being protected right now may still need to remain confidential many years or decades into the future. Additionally, the cryptographic transition itself, updating protocols, software, hardware, and organizational practices across the entire internet’s infrastructure, is understood to be a slow, multi-year undertaking in its own right, which is why standards bodies including NIST have already finalized initial post-quantum cryptographic standards well ahead of any confirmed timeline for a cryptographically relevant quantum computer actually being built.

Common Misconceptions Worth Addressing

A few misunderstandings about Shor’s algorithm come up often enough to be worth directly correcting.

Shor’s algorithm does not break all cryptography.

It specifically threatens algorithms whose security rests on integer factorization or the discrete logarithm problem, meaning RSA, Diffie-Hellman, DSA, and elliptic curve variants like ECDSA and ECDH. Symmetric encryption algorithms like AES, and cryptographic hash functions like SHA-256, are affected differently by quantum computing, primarily through a separate and considerably less severe result called Grover’s algorithm, which provides only a quadratic rather than exponential speedup, generally addressed simply by using somewhat larger key or output sizes rather than requiring an entirely different algorithm family.

A working demonstration on a small number is not the same as a threat to real cryptography.

Factoring the number 21 in a laboratory does not mean an equivalent quantum computer can factor a 2048-bit RSA modulus. The scaling challenge between these two situations is genuinely enormous, involving orders of magnitude more qubits, dramatically lower error rates, and sustained coherence over far longer computations.

“Quantum-resistant” and “quantum-proof” are not quite the same claim.

Post-quantum cryptographic algorithms are believed to resist known quantum attacks based on current mathematical understanding and analysis, but as with any cryptographic scheme, absolute permanent security can never be guaranteed with total certainty, only confidence based on the best available cryptanalysis to date.

Wrapping Up

Shor’s algorithm stands as one of the most consequential results in the history of computer science precisely because of the enormous gap between how simple its core message is and how far-reaching its implications are. A quantum computer, if built at sufficient scale and reliability, can efficiently solve the exact mathematical problems that essentially all of modern public key cryptography depends on for its security, a feat with no known efficient classical equivalent. That quantum computer does not yet exist at anything close to the scale required to threaten real-world cryptographic keys, and serious uncertainty remains about exactly when, or under what engineering approach, it eventually will. But the algorithm’s very existence, published back in 1994 and never meaningfully challenged since as a correct and efficient solution to these problems, has already reshaped how governments, standards bodies, and the security industry think about long-term cryptographic planning, driving a global migration toward post-quantum cryptography that is well underway today, years or potentially decades before the specific threat it defends against is expected to become an operational reality.