Among all the developments in quantum computing with implications for cybersecurity, Shor’s algorithm stands out as the most consequential. Developed in 1994 by mathematician Peter Shor, then at Bell Labs, it describes a quantum procedure capable of solving problems that are computationally intractable for classical computers. Those problems are the mathematical foundations on which most modern public-key cryptography is built.
Understanding what Shor’s algorithm is, how it works, and what it means for the encryption systems organizations rely on today is essential for any enterprise developing a quantum-resilient security strategy.
The Mathematical Foundation of RSA Encryption
To understand why Shor’s algorithm is threatening, it is necessary to first understand what it attacks. RSA encryption, the most widely deployed public-key cryptographic system in the world, derives its security from the difficulty of integer factorization. RSA key pairs are generated from two large prime numbers. The public key is derived from the product of these primes. The private key is derived from the primes themselves.
The security of RSA rests on a simple asymmetry: multiplying two large prime numbers together is computationally easy, but working backward from the product to identify the original primes is computationally infeasible for sufficiently large numbers. An RSA-2048 key, for example, has a modulus that is the product of two primes, each approximately 617 digits long. On a classical computer, factoring this number through exhaustive methods would require more computational effort than has existed in the history of computing.
Shor’s algorithm breaking RSA encryption methods that cybersecurity practitioners study carefully, is threatening precisely because it eliminates the computational asymmetry on which RSA’s security depends. Where classical computers require exponential time to factor large integers, Shor’s algorithm accomplishes the same task in polynomial time on a sufficiently powerful quantum computer.
The formal specifications for RSA cryptographic operations, including the mathematical primitives for encryption, decryption, and signature generation, are defined in RFC 8017, published by the IETF. These specifications are the authoritative technical reference for how RSA is implemented across the internet’s security infrastructure, covering key representation, encryption schemes, and signature schemes.
How Shor’s Algorithm Works
Shor’s algorithm exploits two fundamental properties of quantum computers: superposition, which allows qubits to represent multiple states simultaneously, and quantum interference, which allows the algorithm to amplify correct answers and suppress incorrect ones.
The algorithm converts the factoring problem into a period-finding problem. Given an integer N to factor, Shor’s algorithm selects a random integer and computes the period of a specific mathematical function involving that integer and N. Once the period is found, classical mathematical techniques allow the prime factors of N to be derived from it with high probability.
The critical insight is that quantum computers can find periods exponentially faster than classical computers. Classical period-finding algorithms scale exponentially with the size of the number being factored. Shor’s algorithm scales polynomially, meaning the time required grows far more slowly as the problem size increases. For an RSA-2048 key, this difference in scaling translates from millions of years of classical computation to potentially hours on a sufficiently capable quantum computer.
Shor’s algorithm also applies to the discrete logarithm problem, the mathematical foundation of elliptic curve cryptography and Diffie-Hellman key exchange. This means it threatens not just RSA but the full family of asymmetric cryptographic systems that underpin TLS connections, digital certificates, VPN authentication, code signing, and most other security protocols used across enterprise environments.
The Scale of the Threat to Enterprise Cryptography
The breadth of systems that rely on asymmetric cryptography threatened by Shor’s algorithm is difficult to overstate. Every TLS connection securing web traffic between browsers and servers relies on asymmetric key exchange for session establishment. Every digital certificate validating the identity of a server, a code-signing authority, or an email sender relies on RSA or elliptic-curve cryptographic signatures. Every VPN tunnel establishes secure communications between enterprise locations, authenticating using public-key cryptography.
If Shor’s algorithm becomes practically executable against real-world key sizes, the compromise is not limited to a single system or application. It is systemic. Every system that has relied on these cryptographic foundations would need to be reassessed and migrated.
As explained in MIT Technology Review’s widely cited analysis of Shor’s algorithm threat to asymmetric encryption, a quantum computer running Shor’s algorithm would be capable of cracking a 1,024-bit RSA implementation in under a day, based on estimates published by the US National Academies of Sciences, Engineering, and Medicine. For RSA-2048, the currently dominant standard, researchers have estimated that a quantum computer with approximately 20 million error-corrected logical qubits could factorize in roughly 8 hours.
Current quantum hardware is far from this scale. The most powerful quantum systems available in 2026 operate with thousands of physical qubits but require extensive error correction to produce reliable logical qubits, and the ratio of physical to logical qubits required for the error correction needed to run Shor’s algorithm at meaningful scale remains a significant engineering challenge. However, hardware capabilities have been advancing at a pace that has repeatedly surprised experts, and the uncertainty about the timeline is precisely the reason that preparation must begin now.
The Harvest Now, Decrypt Later Strategy
One of the most operationally significant dimensions of the Shor’s algorithm threat is that it is already affecting the security of data transmitted today. Nation-state threat actors and sophisticated adversaries are currently capturing encrypted communications and storing them with the explicit intention of decrypting them once quantum computing reaches sufficient scale. This strategy, widely referred to as harvest now, decrypt later, means that data protected by RSA and elliptic curve cryptography today is vulnerable to future decryption within the operational lifespan of a quantum computer’s development.
The implication is direct and urgent. Enterprises that transmit sensitive data whose confidentiality must be maintained for years or decades are already exposed to this threat. Intelligence communications, medical records, intellectual property, financial transaction histories, and legal documents are all categories of information that could face future decryption if they are currently protected by quantum-vulnerable cryptographic standards.
This reality is why standards bodies and governments have accelerated post-quantum cryptography standardization timelines. The threat does not begin when quantum computers can break encryption. It began when adversaries started capturing encrypted data for future decryption, which is already underway.
What Shor’s Algorithm Does Not Threaten
Understanding the scope of Shor’s algorithm requires equal clarity about what it does not threaten. Shor’s algorithm is specifically designed to solve the integer factorization and discrete logarithm problems. It does not apply to symmetric cryptographic algorithms or hash functions, which rely on different mathematical properties.
AES encryption, the dominant symmetric encryption standard used for protecting data at rest and for securing the payload of TLS connections after the initial handshake, is not broken by Shor’s algorithm. The relevant quantum threat to symmetric encryption comes from Grover’s algorithm, which provides a quadratic speedup for search problems, effectively halving the security provided by a given key length. The mitigation for Grover’s algorithm is straightforward: migrating from AES-128 to AES-256 restores an adequate security margin.
This distinction matters for enterprise planning. The migration required to address Shor’s algorithm, which involves replacing asymmetric cryptographic algorithms entirely, is substantially more complex and disruptive than the symmetric key length upgrade that addresses Grover’s algorithm. Organizations should understand both threats independently and plan their response to each accordingly.
The Post-Quantum Response to Shor’s Algorithm
The cryptographic community’s response to Shor’s algorithm has been the development and standardization of post-quantum cryptographic algorithms that replace the mathematical foundations targeted by Shor’s algorithm with problem types that are believed to resist both classical and quantum attacks.
In August 2024, the US National Institute of Standards and Technology finalized its first set of post-quantum cryptography standards after an eight-year evaluation process. The primary algorithms are ML-KEM, based on the CRYSTALS-Kyber lattice framework, for key encapsulation and encryption, and ML-DSA, based on CRYSTALS-Dilithium, for digital signatures. A hash-based signature alternative, SLH-DSA, was also standardized. These algorithms are built on mathematical problems, primarily lattice problems and hash functions, for which no quantum algorithm analogous to Shor’s has been demonstrated to provide an exponential speedup.
The security rationale for these choices is straightforward: if no known quantum algorithm breaks the underlying mathematical problem, the post-quantum algorithm is considered quantum-resistant. However, the discipline continues to evolve. The NIST evaluation process itself demonstrated that candidate algorithms believed to be strong can be broken by classical mathematical attacks, as happened with the SIKE algorithm. Post-quantum cryptography requires ongoing cryptanalysis and the maintenance of cryptographic agility to respond to future discoveries.
What Shor’s Algorithm Means for Enterprise Security Strategy
For enterprise security and IT leadership, the Shor’s algorithm threat translates into a specific and time-sensitive strategic program. The transition from quantum-vulnerable asymmetric cryptography to post-quantum alternatives is the largest cryptographic migration in the history of computing, and the organizations that begin planning now will be in a substantially better position than those that wait.
The first priority is a comprehensive cryptographic inventory. Organizations must identify every system, application, protocol, and integration that uses RSA or elliptic curve cryptographic operations. This inventory is the prerequisite for understanding the scope of the migration required and for prioritizing which systems to address first.
The second priority is evaluating the sensitivity lifetime of data currently being transmitted and stored under RSA or elliptic curve protection. For data that will remain sensitive beyond the anticipated timeline for cryptographically relevant quantum computers, the harvest now, decrypt later threat is already active, and transitioning to hybrid or post-quantum key exchange for that data should be treated as an immediate priority.
The third priority is engaging with technology vendors and cloud providers to understand their post-quantum cryptography roadmaps. Many dependencies on external systems cannot be migrated unilaterally. TLS configurations, certificate authorities, API authentication systems, and cloud platform cryptographic services must all support post-quantum algorithms before enterprises can fully transition.
The fourth priority is beginning the implementation of post-quantum or hybrid cryptography for the highest-risk systems, building the operational experience and validating the compatibility of new algorithms across the enterprise environment before the full migration is required.
Frequently Asked Questions
How close are quantum computers to being able to run Shor’s algorithm against real-world RSA keys?
Current quantum hardware cannot run Shor’s algorithm at the scale required to threaten real-world RSA key sizes. Estimates suggest that factoring RSA-2048 would require a quantum computer with millions of error-corrected logical qubits, which in turn requires hundreds of millions to billions of physical qubits depending on error rates. Current systems operate with thousands of physical qubits and limited error correction. Expert estimates for when cryptographically relevant quantum computers might emerge vary widely, from under a decade to several decades. The uncertainty is itself the primary reason for acting now rather than waiting for greater timeline clarity.
Does Shor’s algorithm affect all types of encryption equally?
Shor’s algorithm specifically threatens asymmetric cryptographic systems, including RSA, elliptic curve cryptography, and Diffie-Hellman key exchange, all of which rely on the integer factorization or discrete logarithm problems. It does not directly threaten symmetric encryption algorithms like AES or cryptographic hash functions. Those face a different and less severe threat from Grover’s algorithm, which is addressed by increasing key and output lengths rather than replacing the algorithms themselves. A complete quantum-resilient security posture requires addressing both threats, but they involve different urgencies and different technical responses.
What is the difference between post-quantum cryptography and simply using longer RSA keys?
Increasing RSA key lengths provides no meaningful protection against Shor’s algorithm. Because Shor’s algorithm scales polynomially with the size of the number being factored, increasing key length increases the difficulty of the quantum attack only modestly compared to how dramatically it increases computational cost for legitimate operations. Post-quantum cryptography replaces the mathematical problems targeted by Shor’s algorithm with entirely different problem types, primarily lattice problems and hash functions, for which Shor’s algorithm provides no speedup. Longer RSA keys are not a viable path to quantum resistance; algorithm replacement is.
