Skip to content
ContentLora

    Tip: press / anywhere to search.

    Explainer

    How quantum computers break encryption

    Shor's 1994 algorithm lets a large quantum computer solve factoring and discrete logarithms, the math problems that RSA and elliptic-curve cryptography depend on, while symmetric ciphers such as AES only need larger keys.[1][2] No such machine exists yet, but published estimates of the hardware needed fell sharply in 2025 and 2026.[3][4]

    Editor reviewedUpdated Post-quantum cryptography and securityComputing

    The problem in one paragraph

    Much of today’s encryption depends on a lopsided math problem. Multiplying two huge prime numbers is easy. Working backwards from the product to the two primes is so hard that a normal computer is estimated to need billions of years for large enough numbers.[5] RSA encryption depends on that gap. In 1994 Peter Shor showed that a quantum computer could close it, and that the same trick also breaks the other main family of public-key cryptography, based on “discrete logarithms”.[1]

    Public-key cryptography in use today rests on two hardness assumptions: integer factorization (RSA) and discrete logarithms, in finite fields (Diffie-Hellman, DSA) or on elliptic curves (ECDH, ECDSA, EdDSA). Shor’s algorithm reduces both to period finding, which a quantum computer performs efficiently using the quantum Fourier transform. A large-scale quantum computer would therefore break all of these schemes, not just RSA.[1][6]

    What survives

    Not everything breaks. Symmetric encryption, where both sides already share a secret key (AES, for example), faces only a modest speed-up from a different quantum method, Grover’s algorithm. NIST judged that doubling the key length is enough to stay safe.[2] The real damage is to the public-key systems used to set up those shared keys and to sign data.[6]

    Grover’s algorithm gives a quadratic speed-up for unstructured search, so a k-bit key offers roughly k/2 bits of security against a quantum attacker. NIST’s 2016 report concluded that doubling key sizes suffices if Grover ever becomes practical. It also noted that this heuristic may be conservative given the cost of quantum hardware.[2] AES-256 and SHA-2/SHA-3 at suitable output lengths are therefore treated as quantum-safe. The migration effort focuses on key establishment and signatures.[7]

    How big a machine is needed

    Breaking encryption will take quantum computers with many thousands of working qubits, and today’s qubits are fragile.[8] Machines that powerful get a special name: a “cryptographically relevant” quantum computer.[9] Researchers keep finding cheaper ways to run the attack. In 2019 one estimate said breaking RSA-2048 would need 20 million noisy qubits. By May 2025 the same researcher had cut that to under a million.[3]

    Resource estimates are given in physical qubits under assumed error rates and surface-code overheads. Gidney’s May 2025 estimate for RSA-2048 is under a million noisy qubits and under a week of runtime, down from 20 million qubits for eight hours in 2019.[3] In March 2026 Google estimated that 256-bit ECC needs fewer than 1,200 logical qubits and 90 million Toffoli gates, or under 500,000 physical superconducting qubits for a few minutes. Google published a zero-knowledge proof of the result rather than the circuit.[4][10] Cloudflare also reported a 2026 estimate from Oratomic of about 10,000 qubits for P-256 on neutral-atom hardware. Key details of that estimate were not published.[11] For the state of the hardware, see quantum computing crash course, surface-code and neutral-atom-qubits.

    When could it happen?

    Nobody knows. NIST says expert estimates range from a few years to a few decades.[12] In a 2024 survey of 32 experts, the average estimated chance of a cryptographically relevant machine within ten years was about 19% to 34%, depending on how answers were read.[13] In 2026 the G7’s cybersecurity working group said recent advances suggest such machines may come sooner than expected.[14] Uncertainty does not mean waiting is safe. Data stolen today can be decrypted later; see harvest now, decrypt later. The fix is new algorithms, explained in how post-quantum cryptography works.

    Questions readers ask

    Which encryption does a quantum computer break?

    Public-key systems based on factoring (RSA) or discrete logarithms (including elliptic-curve cryptography). Symmetric ciphers are only weakened, and doubling the key size compensates.[6][2]

    How many qubits would it take to break RSA-2048?

    A May 2025 Google estimate put it at fewer than a million noisy qubits running for under a week, down from 20 million in a 2019 estimate.[3]

    Is elliptic-curve cryptography safer than RSA against quantum attacks?

    No. A March 2026 Google estimate said 256-bit elliptic-curve cryptography could fall to fewer than 1,200 logical qubits, or under 500,000 physical qubits in a few minutes.[4]

    What is a cryptographically relevant quantum computer?

    It is the term experts use for a quantum computer mature enough to break current public-key encryption.[9]

    Sources

    Each numbered claim is a statement we checked against the sources listed with it. Status shows how well established it is.

    1. [1]

      In 1994 Peter Shor of Bell Laboratories showed that quantum computers can efficiently solve the mathematical problems that public-key cryptosystems rely on, such as factoring and discrete logarithms. confirmedas of 2026-10-10

    2. [2]

      Grover's algorithm gives only a quadratic speed-up against symmetric-key systems, and NIST judged that doubling the key size would be enough to preserve their security. confirmedas of 2026-10-10

    3. [3]

      A May 2025 Google preprint estimated that 2048-bit RSA could be factored in less than a week by a quantum computer with fewer than a million noisy qubits, down from a 2019 estimate of 20 million noisy qubits. confirmedas of 2026-10-10

    4. [4]

      In March 2026 Google researchers estimated that breaking 256-bit elliptic-curve cryptography would need fewer than 1,200 logical qubits and 90 million Toffoli gates, or under 500,000 physical superconducting qubits running for a few minutes. confirmedas of 2026-03-31

    5. [5]

      Many current encryption algorithms rely on the fact that multiplying two large primes is easy, while recovering those prime factors from the product is estimated to take a conventional computer billions of years for large enough numbers. confirmedas of 2026-10-10

    6. [6]

      A large-scale quantum computer would make insecure the public-key systems based on integer factorization, such as RSA, and those based on the discrete logarithm problem, which includes elliptic-curve cryptography. confirmedas of 2026-10-10

    7. [7]

      Post-quantum algorithms are designed for two main tasks, general encryption (establishing keys) and digital signatures used for authentication. confirmedas of 2026-10-10

    8. [8]

      NIST notes that breaking present-day encryption will need quantum computers with many thousands of qubits, and that qubits are fragile and easily corrupted by disturbances. confirmedas of 2026-10-10

    9. [9]

      A quantum computer mature enough to break current public-key encryption is called a "cryptographically relevant" quantum computer (CRQC). confirmedas of 2026-10-10

    10. [10]

      Google disclosed its 2026 elliptic-curve attack estimate with a zero-knowledge proof instead of publishing the full attack details. confirmedas of 2026-03-31

    11. [11]

      Cloudflare reported that the company Oratomic published a resource estimate in 2026 suggesting P-256 elliptic-curve cryptography could be broken with about 10,000 qubits on a neutral-atom quantum computer, while withholding some details. reportedas of 2026-04-07

    12. [12]

      NIST says no one knows when a quantum computer able to threaten current encryption will appear, with expert estimates ranging from a few years to a few decades. confirmedas of 2026-10-10

    13. [13]

      In the Global Risk Institute's 2024 survey of 32 experts, average estimates of the chance of a cryptographically relevant quantum computer within 10 years ranged from about 19% (pessimistic reading) to about 34% (optimistic reading). confirmedas of 2024-12-31

    14. [14]

      The G7 Cybersecurity Working Group said in September 2026 that several recent advances suggest quantum computers able to break widely used public-key cryptography may be developed sooner than anticipated. confirmedas of 2026-09-03

    Revision history (1)
    1. Page created.

    Created Oct 10, 2026. Last reviewed by an editor on Oct 10, 2026. Next scheduled review: Jan 10, 2027.

    Cite this page

    "How quantum computers break encryption." ContentLora, updated Oct 10, 2026. https://contentlora.com/explain/how-quantum-computers-break-encryption

    Spotted an error? Suggest a correction or emailcorrections@contentlora.com.

    Keep exploring

    ☰ Contents