No single algorithm has done more to bring quantum computing into cybersecurity conversations than Shor’s algorithm. Discovered by mathematician Peter Shor in 1994, it demonstrated that a sufficiently powerful quantum computer could factor large integers exponentially faster than the best known classical methods — directly threatening the mathematical foundation of RSA encryption, one of the most widely deployed cryptographic systems in the world. This article walks through what the algorithm actually does, how it works mathematically, why factoring matters for cryptography, and a realistic assessment of the current state of the threat.
Why Factoring Matters: The RSA Connection
RSA encryption, developed in 1977 and still widely used today for secure key exchange and digital signatures, relies on a simple but powerful asymmetry: it’s computationally easy to multiply two large prime numbers together, but computationally very hard to reverse the process — that is, to take their product and recover the original two primes.
An RSA public key is built from the product $N = p \times q$, where $p$ and $q$ are large prime numbers (typically each several hundred digits long for modern key sizes like RSA-2048). The security of RSA rests entirely on the assumption that factoring $N$ back into $p$ and $q$ is computationally infeasible using classical computers, given large enough primes. The best classical factoring algorithm, the general number field sieve, has sub-exponential but still infeasible running time for sufficiently large $N$ — for a 2048-bit RSA key, factoring is estimated to require more computational time than the age of the universe using currently known classical methods and hardware.
Shor’s algorithm changes this calculus entirely by providing a method that runs in polynomial time on a quantum computer — meaning the time required grows manageably, rather than explosively, as the key size increases.
From Factoring to Period-Finding
The genius of Shor’s algorithm isn’t a direct method for factoring — it’s a clever mathematical reduction that transforms the factoring problem into a period-finding problem, which quantum computers happen to be extremely good at solving efficiently using the Quantum Fourier Transform (covered in its own dedicated article).
Here’s the mathematical chain of reasoning:
- To factor $N$, pick a random integer $a$ that is coprime to $N$ (shares no common factors other than 1).
- Consider the function $f(x) = a^x \mod N$. This function is periodic — it repeats with some period $r$, meaning $f(x + r) = f(x)$ for all $x$.
- If you can find that period $r$, and if $r$ is even and $a^{r/2} \not\equiv -1 \pmod{N}$, then $\gcd(a^{r/2} – 1, N)$ and $\gcd(a^{r/2} + 1, N)$ will very likely reveal nontrivial factors of $N$ — that is, the actual prime factors $p$ and $q$.
The entire challenge, then, reduces to: how do you efficiently find the period $r$ of this modular exponentiation function? Classically, finding this period for large $N$ is itself computationally hard — comparable in difficulty to factoring directly. This is where the quantum part of the algorithm comes in.
The Quantum Period-Finding Subroutine
Shor’s algorithm finds the period $r$ using the following quantum procedure:
- Prepare two quantum registers: an input register in an equal superposition over many possible values of $x$, and an output register initialized to $|0\rangle$.
- Compute the modular exponentiation $f(x) = a^x \mod N$ using quantum gates, entangling the input and output registers. After this step, the combined state is a superposition over all $(x, f(x))$ pairs — and because $f(x)$ is periodic, this creates a structured, periodic pattern of entanglement between the two registers.
- Apply the Quantum Fourier Transform (QFT) to the input register. The QFT converts the periodicity in the state (which isn’t directly visible through measurement) into a measurable peak in a transformed “frequency” basis, through the constructive and destructive interference mechanisms discussed in the interference article.
- Measure the input register. The measurement yields a value closely related to $\frac{c}{r}$ for some integer $c$, revealing information about the period $r$ with high probability.
- Classical post-processing: using the continued fractions algorithm (a classical, efficient technique), extract the actual period $r$ from the measured value.
- Compute the factors using the GCD calculations described above. If the process fails (which can happen with some probability due to unlucky choices of $a$ or measurement outcomes), the algorithm simply repeats with a different random $a$.
This structure — spread amplitude across many states, entangle registers to embed problem structure, use the QFT to concentrate amplitude via interference on the answer, measure, then do lightweight classical cleanup — is a template shared with several other quantum algorithms, but Shor’s application of it to factoring is what gives it such outsized real-world significance.
Complexity Comparison
The complexity difference between classical and quantum factoring is dramatic. The general number field sieve (best known classical algorithm) has a running time that scales roughly as:
$$O\left(\exp\left[c (\log N)^{1/3} (\log \log N)^{2/3}\right]\right)$$
for some constant $c$ — sub-exponential, but still growing explosively for cryptographically relevant key sizes. Shor’s algorithm, by contrast, runs in:
$$O\left((\log N)^2 (\log \log N)(\log \log \log N)\right)$$
polynomial time, meaning the resource requirements grow much more gently as $N$ (and thus key size) increases. This is the essence of why Shor’s algorithm is described as providing an “exponential speedup” — the gap between classical and quantum running time widens dramatically as key sizes grow, which is precisely the opposite of what cryptographic security requires.
Practical Example: A Toy Factoring Walkthrough
To ground the abstract math, consider factoring $N = 15$ (small enough to work through by hand, though trivial for classical computers — real applications concern numbers hundreds of digits long).
- Choose $a = 7$ (coprime to 15).
- The function $f(x) = 7^x \mod 15$ cycles through values: $7^0 = 1, 7^1 = 7, 7^2 = 4, 7^3 = 13, 7^4 = 1, \ldots$ — so the period is $r = 4$.
- Since $r$ is even, compute $7^{r/2} = 7^2 = 49 \equiv 4 \pmod{15}$.
- Compute $\gcd(4 – 1, 15) = \gcd(3, 15) = 3$ and $\gcd(4 + 1, 15) = \gcd(5, 15) = 5$.
- Both 3 and 5 are indeed the prime factors of 15.
This exact procedure, scaled up to real quantum hardware and much larger numbers, is what Shor’s algorithm implements — with the period-finding step (step 2 here) done efficiently via quantum superposition, entanglement, and the QFT rather than by simple classical enumeration, which becomes infeasible for large $N$.
Choosing the Base and Handling Edge Cases
The algorithm as described glosses over a few important practical details worth spelling out. First, the random base $a$ chosen in step one must satisfy $\gcd(a, N) = 1$; if it doesn’t (checked efficiently using the classical Euclidean algorithm before ever touching the quantum computer), then $\gcd(a, N)$ itself is already a nontrivial factor of $N$, and the algorithm succeeds immediately without needing the quantum subroutine at all. Second, even when $a$ is properly coprime to $N$, the period-finding and subsequent GCD steps don’t always yield a valid factorization on the first attempt — for instance, if the found period $r$ turns out to be odd, or if $a^{r/2} \equiv -1 \pmod N$, the GCD computation won’t reveal a nontrivial factor. In these cases, the algorithm simply restarts with a freshly chosen random $a$. It’s a mathematically proven property of the underlying number theory that, on average, only a small, bounded number of attempts (a constant expected number, not growing with the size of $N$) are needed before a successful run occurs, which is part of why the algorithm’s overall expected running time remains efficient despite this probabilistic element.
The Role of Classical Continued Fractions
It’s worth giving the classical post-processing step — mentioned briefly above — a closer look, since it’s easy to overlook amid the quantum mechanics but is actually essential to the algorithm working at all. After the quantum period-finding subroutine measures a value, call it $y$, from the input register, that value is related to the true period $r$ by the approximate relationship $\frac{y}{2^n} \approx \frac{c}{r}$ for some unknown integer $c$, where $2^n$ is the size of the register used. The continued fractions algorithm, a well-established and efficient classical number-theory technique dating back centuries, is used to find the best small-denominator fraction $\frac{c}{r}$ approximating $\frac{y}{2^n}$, which reveals candidate values for $r$.
This step matters because the raw quantum measurement doesn’t hand you the period directly — it hands you a noisy, rounded piece of information that requires classical mathematical processing to extract the precise integer period. This interplay between an efficient quantum subroutine (period-finding via the QFT) and efficient classical post-processing (continued fractions) is a recurring pattern in quantum algorithm design, and it’s a good reminder that most practical quantum algorithms are genuinely hybrid, not purely quantum from start to finish.
Real-World Demonstrations So Far
Shor’s algorithm has been experimentally demonstrated on small numbers using real quantum hardware — early demonstrations factored numbers like 15 and 21 using a handful of physical qubits, and various research groups have continued to push these small-scale demonstrations forward using both true quantum hardware and simplified or “compiled” versions of the algorithm tailored to specific small inputs. These demonstrations are genuine and scientifically meaningful, but it’s important to be precise: factoring a small number like 15 or 21 provides essentially zero cryptographic threat and often uses simplifications not generalizable to large numbers. Factoring a cryptographically relevant 2048-bit RSA key is an entirely different scale of engineering challenge.
What It Would Actually Take to Break RSA-2048
Various peer-reviewed estimates (refined over the years as error correction research has matured) suggest that breaking a 2048-bit RSA key using Shor’s algorithm would require on the order of several thousand to around twenty million physical qubits, depending heavily on assumptions about gate fidelity, error correction overhead, and algorithmic optimizations, with the computation potentially taking anywhere from hours to days on such a machine. Current publicly known quantum processors have, at most, a few hundred physical qubits, none of which are yet organized into large-scale fault-tolerant logical qubits. This gap — between hundreds of noisy physical qubits today and millions of reliable, error-corrected physical qubits needed for real cryptographic attacks — represents a substantial, multi-year-to-multi-decade engineering effort, not an imminent capability.
Shor’s Algorithm and Elliptic-Curve Cryptography
While most popular discussion of Shor’s algorithm focuses on RSA and integer factoring, it’s important to know that a closely related quantum algorithm — using the same core period-finding and QFT machinery, adapted to a different mathematical group structure — efficiently solves the discrete logarithm problem, which underlies elliptic-curve cryptography (ECC) and Diffie-Hellman key exchange. This matters a great deal in practice because ECC is, if anything, more widely deployed than RSA in modern systems: it’s the basis for most TLS/HTTPS key exchange today (via ECDH), for cryptocurrency signature schemes (via ECDSA), and for many modern secure messaging protocols. Because ECC typically achieves comparable classical security to RSA using much smaller key sizes, some early intuitions assumed it might be more quantum-resistant — but this isn’t the case; the discrete-logarithm variant of Shor’s algorithm breaks ECC just as thoroughly, given sufficient fault-tolerant quantum hardware, which is why post-quantum cryptography migration efforts, discussed below, need to replace both RSA and ECC-based systems, not just one or the other.
Security Implications and Industry Response
Despite the significant gap between current hardware and a real threat, the cybersecurity industry has taken the long-term risk seriously for several important reasons:
- “Harvest now, decrypt later” attacks: adversaries (particularly well-resourced nation-states) can capture and store encrypted traffic today, with the intention of decrypting it once cryptographically relevant quantum computers become available. Data with long confidentiality requirements — state secrets, medical records, long-term financial data — is particularly at risk from this strategy even though decryption capability doesn’t exist yet.
- Migration timelines are long: replacing cryptographic infrastructure across the entire internet, financial systems, and government infrastructure historically takes many years to over a decade, which is why standards bodies began preparing well before quantum computers posed an immediate threat.
- NIST post-quantum cryptography standards: in response, NIST ran a multi-year public competition and, in 2024, finalized initial post-quantum cryptographic standards (including CRYSTALS-Kyber, renamed ML-KEM, for key encapsulation, and CRYSTALS-Dilithium, renamed ML-DSA, for digital signatures), based on mathematical problems believed to be hard even for quantum computers, such as lattice-based cryptography. Migration to these standards is an active, ongoing industry-wide effort as of the time of writing.
Advantages and Limitations of Shor’s Algorithm
The advantage of Shor’s algorithm is unambiguous from a theoretical computer science standpoint: it’s a rigorously proven, exponential speedup for a problem (integer factoring) that underlies widely deployed real-world cryptography. It stands as one of the most significant results in the history of computer science precisely because of this direct, practical relevance.
The limitations are almost entirely about hardware readiness rather than algorithmic correctness. Shor’s algorithm requires deep, wide quantum circuits with many sequential entangling gates, executed with very high fidelity — exactly the kind of computation that current, error-prone NISQ-era hardware struggles with, as discussed in the decoherence and error correction article. Until large-scale, fault-tolerant quantum computers exist, Shor’s algorithm remains a proven mathematical result without a matching real-world execution platform for cryptographically significant problem sizes.
Established Result vs. Future Threat
It’s worth being unambiguous about the distinction here: Shor’s algorithm itself is not speculative — it’s a rigorously proven, peer-reviewed, mathematically certain result about what a sufficiently powerful quantum computer could do. What remains uncertain and forward-looking is the timeline for building hardware capable of running it against cryptographically relevant key sizes. Expert estimates vary, but many credible assessments place large-scale, fault-tolerant, cryptographically relevant quantum computing at a decade or more away, with meaningful uncertainty in either direction depending on the pace of error correction and hardware scaling breakthroughs.
Practical Guidance for Organizations Today
For organizations wondering what, concretely, to do about Shor’s algorithm today, the practical guidance emerging from standards bodies and security researchers generally converges on a few points. First, inventory cryptographic assets — many organizations don’t have a clear picture of where RSA, ECC, or Diffie-Hellman are used across their systems, which is a necessary first step before any migration can be planned. Second, prioritize migration for data and systems with long confidentiality requirements, given the “harvest now, decrypt later” risk discussed above — a medical record or state secret that needs to remain confidential for decades is at meaningfully higher near-term risk than a short-lived session key. Third, adopt crypto-agility as a design principle, meaning systems should be built so cryptographic algorithms can be swapped out without a full architectural overhaul, since post-quantum standards are still evolving and additional updates are likely. Finally, begin piloting NIST’s finalized post-quantum standards (ML-KEM and ML-DSA, among others) where feasible, particularly for new systems, rather than waiting for a more urgent, reactive migration once quantum hardware progress accelerates unexpectedly.
Wrapping Up
Shor’s algorithm stands as one of the most consequential results in the history of computer science: a mathematically rigorous demonstration that quantum computers can factor large integers exponentially faster than any known classical method, directly threatening the security foundation of RSA and related cryptographic systems used to secure the modern internet. While current hardware remains far from being able to execute this algorithm against real-world cryptographic key sizes, the long-term threat is credible enough that the cybersecurity industry has already begun a multi-year transition toward post-quantum cryptographic standards designed to resist this exact kind of attack. Understanding Shor’s algorithm — both its genuine mathematical power and the very real hardware gap that currently limits its practical impact — is essential context for anyone thinking seriously about the future of digital security.