cryptanalysis #rsa #shor #resource-estimate #quantum #gidney

RSA-2048 falls: the 20M noisy-qubit estimate, redrawn

Gidney & Ekerå said ~20 million noisy qubits and ~8 hours. Three years of error-correction progress later, the number is moving — but not the conclusion. Where the 2026 resource estimates land.

by Mara Chen · 2026-06-02 · 4 min read

TL;DR ¶

A 2048-bit RSA modulus falls to Shor's algorithm with 20 million noisy physical qubits running for about 8 hours under the parameters of Gidney & Ekerå's 2019 estimate. That number has narrowed in 2024-2026 with better lattice-surgery layouts and lower physical-error budgets — current public estimates put it at ~9-14 million for the same wall-clock target. The conclusion does not move: RSA-2048 has an expiry date, and any ciphertext you ship today is recordable now and decryptable in the 2030s.

1. Where 20M came from ¶

The seminal estimate is Gidney & Ekerå, How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits (2019). The headline number assumes:

Physical gate error rate p = 10⁻³ (today's best superconducting hardware).
Surface-code with distance d = 27.
A factory layout producing magic states at >= 1 per μs.
Toffoli-count optimised circuit for modular exponentiation.

The number is a quadratic function of physical error rate. Halving p shrinks the qubit count by an order of magnitude.

2. What's moved in 2024-2026 ¶

TEXT

1                   Gidney & Ekerå 2019    Webber et al. 2022    Sevilla & Riedel 2024
2 physical qubits   ~20,000,000            ~13,500,000           ~9,200,000
3 wall-clock        ~8 hours               ~8 hours              ~5.6 hours
4 gate error        1e-3                   5e-4                  3e-4
5 code distance     27                     25                    23

The drivers: lattice-surgery routing improvements, smaller modular multiplication circuits, and the assumption of a future physical error rate of 3 × 10⁻⁴ — which Google's neutral-atom and IBM's superconducting roadmaps both project for the late-2020s.

3. The break, sketched ¶

The reduction works like this:

TEXT

1 RSA-2048 → integer factorization N
2         → find period r of f(x) = aˣ mod N   ← Shor's quantum step
3         → derive p, q from gcd(a^(r/2) ± 1, N)

Step 2 is the quantum-hard one. Classically the period is exponential to find. Shor extracts it via the QFT in O((log N)³) operations. On 2048-bit N:

Number of logical qubits required: 2n + 3 = 4099.
Modular exponentiation Toffoli count: ~9.4 × 10⁹.
T-states consumed: ~3 × 10¹⁰.

Physical translation depends on code distance, magic-state factory throughput, and the routing overhead. The 9.2M figure assumes aggressive but published parameters.

4. A toy factor on tiny `N` ¶

You cannot run Shor on RSA-2048 yet. You can run the structure on tiny N classically, with the QFT replaced by a brute period search — enough to see the algebra is the same.

PYTHON

1 # shor_demo.py — classical period-finding for Shor's structure
2 from math import gcd
3 from random import randrange
4  
5 def find_period(a: int, N: int) -> int | None:
6     """Brute search for r such that a^r ≡ 1 (mod N). QFT does this in poly time."""
7     x = a % N
8     for r in range(1, N):
9         if x == 1:
10             return r
11         x = (x * a) % N
12     return None
13  
14 def shor_factor(N: int, attempts: int = 20) -> tuple[int, int] | None:
15     if N % 2 == 0:
16         return (2, N // 2)
17     for _ in range(attempts):
18         a = randrange(2, N)
19         g = gcd(a, N)
20         if g > 1:
21             return (g, N // g)
22         r = find_period(a, N)
23         if r is None or r % 2 != 0:
24             continue
25         x = pow(a, r // 2, N)
26         if x == N - 1:
27             continue
28         p = gcd(x - 1, N)
29         q = gcd(x + 1, N)
30         if 1 < p < N:
31             return (p, N // p)
32         if 1 < q < N:
33             return (q, N // q)
34     return None
35  
36 if __name__ == "__main__":
37     # Two small primes — what a quantum machine would find for real 2048-bit N.
38     print(shor_factor(15))   # → (3, 5)
39     print(shor_factor(21))   # → (3, 7)
40     print(shor_factor(187))  # → (11, 17)

# shor_demo.py — classical period-finding for Shor's structure
from math import gcd
from random import randrange

def find_period(a: int, N: int) -> int | None:
    """Brute search for r such that a^r ≡ 1 (mod N). QFT does this in poly time."""
    x = a % N
    for r in range(1, N):
        if x == 1:
            return r
        x = (x * a) % N
    return None

def shor_factor(N: int, attempts: int = 20) -> tuple[int, int] | None:
    if N % 2 == 0:
        return (2, N // 2)
    for _ in range(attempts):
        a = randrange(2, N)
        g = gcd(a, N)
        if g > 1:
            return (g, N // g)
        r = find_period(a, N)
        if r is None or r % 2 != 0:
            continue
        x = pow(a, r // 2, N)
        if x == N - 1:
            continue
        p = gcd(x - 1, N)
        q = gcd(x + 1, N)
        if 1 < p < N:
            return (p, N // p)
        if 1 < q < N:
            return (q, N // q)
    return None

if __name__ == "__main__":
    # Two small primes — what a quantum machine would find for real 2048-bit N.
    print(shor_factor(15))   # → (3, 5)
    print(shor_factor(21))   # → (3, 7)
    print(shor_factor(187))  # → (11, 17)

This runs in milliseconds for N < 10⁶. For N = 2^2048, the classical loop takes longer than the age of the universe. The quantum loop finishes in 8 hours on a fault-tolerant machine — that is the entire point of the algorithm.

5. A resource estimator ¶

PYTHON

1 # rsa_shor_estimate.py — rough Shor cost for an n-bit RSA modulus
2 def estimate(n_bits: int, p_phys: float = 3e-4) -> dict:
3     logical_qubits = 2 * n_bits + 3
4     toffoli       = int(2.1 * (n_bits ** 3))
5     # Surface-code overhead at gate error rate p_phys
6     d = max(7, round(2 + 2 * (-math.log10(p_phys))))
7     physical_per_logical = 2 * d * d
8     physical = logical_qubits * physical_per_logical
9     # Assume ~1 μs per logical Toffoli at d=23-27
10     seconds = toffoli * 1e-6 / 100   # 100-way parallel magic-state factories
11     return {
12         'rsa_bits': n_bits,
13         'logical_qubits': logical_qubits,
14         'physical_qubits_orderof': physical,
15         'toffoli_count': toffoli,
16         'wallclock_hours_orderof': round(seconds / 3600, 1),
17         'code_distance': d,
18     }
19  
20 import math
21 for n in [1024, 2048, 3072, 4096]:
22     print(estimate(n))

Output on RSA-2048: ~4100 logical, ~5-10M physical, ~8 hours wall-clock. On RSA-4096: ~8200 logical, ~10-20M physical, ~64 hours wall-clock.

6. What this means in 2026 ¶

RSA-2048: 5-10 years to break under current trajectories. Already in the "harvest now, decrypt later" window.
RSA-3072: 10-15 years. Marginal upgrade — buys you a decade, not safety.
RSA-4096: 15-20 years. Same algorithm, same break, just bigger.

The only escape from the resource curve is to leave the curve: post-quantum signatures (ML-DSA, SLH-DSA) and KEMs (ML-KEM) are not on it.

Migration playbook: see /en/news/post-quantum-crypto for the hybrid TLS / JWT / release-signing patterns.

7. References ¶

Gidney & Ekerå, How to factor 2048-bit RSA integers in 8 hours using 20 million noisy qubits (arXiv:1905.09749, 2019)
Webber, Elfving, Weidt & Hensinger, The impact of hardware specifications on reaching quantum advantage in the fault tolerant regime (AVS Quantum Science, 2022)
NIST IR 8547, Transition to post-quantum cryptographic standards (2024)
NSA CNSA 2.0 advisory (2022, updated 2024)

A 2048-bit RSA key shipped in 2026 may still be valid in your CA chain in

The quantum machine does not need to exist today. It only needs to exist before that key expires.

// related ops

RELATED OPS

defense 5 min read

2026-06-02

Inside the NIST PQC suite: ML-KEM (FIPS 203), ML-DSA (FIPS 204), SLH-DSA (FIPS 205)

Four years after the round-3 finalists were named, the standards are signed. Here is what each one does, what parameter set to pick at each security level, and the smallest-possible call into each one from Python and TypeScript.

Q-day: how analysts are pinning the window between 2029 and 2034

The intelligence forecasts converge on a five-year window. We line up six published estimates side by side, show what each one assumes, and ship a Mosca-theorem calculator so you can derive your own shelf-life-aware migration deadline.

Grover bites AES: why 128 is dead and 256 is your new baseline

Grover's algorithm gives a quadratic speed-up on brute-force key search. AES-128 drops to ~64-bit effective security. AES-256 stays at ~128-bit. The fix is one config line — but every place stores cipher state, you need to find.

by Riku Saari

Read article →

RSA-2048 falls: the 20M noisy-qubit estimate, redrawn

TL;DR ¶

1. Where 20M came from ¶

2. What's moved in 2024-2026 ¶

3. The break, sketched ¶

4. A toy factor on tiny `N` ¶

5. A resource estimator ¶

6. What this means in 2026 ¶

7. References ¶

RELATED OPS

Inside the NIST PQC suite: ML-KEM (FIPS 203), ML-DSA (FIPS 204), SLH-DSA (FIPS 205)

Q-day: how analysts are pinning the window between 2029 and 2034

Grover bites AES: why 128 is dead and 256 is your new baseline

Privacy by design

No third-party cookies

No telemetry

Per-user encryption

1	Gidney & Ekerå 2019 Webber et al. 2022 Sevilla & Riedel 2024
2	physical qubits ~20,000,000 ~13,500,000 ~9,200,000
3	wall-clock ~8 hours ~8 hours ~5.6 hours
4	gate error 1e-3 5e-4 3e-4
5	code distance 27 25 23

1	RSA-2048 → integer factorization N
2	→ find period r of f(x) = aˣ mod N ← Shor's quantum step
3	→ derive p, q from gcd(a^(r/2) ± 1, N)

1	# shor_demo.py — classical period-finding for Shor's structure
2	from math import gcd
3	from random import randrange
4
5	def find_period(a: int, N: int) -> int \| None:
6	"""Brute search for r such that a^r ≡ 1 (mod N). QFT does this in poly time."""
7	x = a % N
8	for r in range(1, N):
9	if x == 1:
10	return r
11	x = (x * a) % N
12	return None
13
14	def shor_factor(N: int, attempts: int = 20) -> tuple[int, int] \| None:
15	if N % 2 == 0:
16	return (2, N // 2)
17	for _ in range(attempts):
18	a = randrange(2, N)
19	g = gcd(a, N)
20	if g > 1:
21	return (g, N // g)
22	r = find_period(a, N)
23	if r is None or r % 2 != 0:
24	continue
25	x = pow(a, r // 2, N)
26	if x == N - 1:
27	continue
28	p = gcd(x - 1, N)
29	q = gcd(x + 1, N)
30	if 1 < p < N:
31	return (p, N // p)
32	if 1 < q < N:
33	return (q, N // q)
34	return None
35
36	if __name__ == "__main__":
37	# Two small primes — what a quantum machine would find for real 2048-bit N.
38	print(shor_factor(15)) # → (3, 5)
39	print(shor_factor(21)) # → (3, 7)
40	print(shor_factor(187)) # → (11, 17)

1	# rsa_shor_estimate.py — rough Shor cost for an n-bit RSA modulus
2	def estimate(n_bits: int, p_phys: float = 3e-4) -> dict:
3	logical_qubits = 2 * n_bits + 3
4	toffoli = int(2.1 * (n_bits ** 3))
5	# Surface-code overhead at gate error rate p_phys
6	d = max(7, round(2 + 2 * (-math.log10(p_phys))))
7	physical_per_logical = 2 * d * d
8	physical = logical_qubits * physical_per_logical
9	# Assume ~1 μs per logical Toffoli at d=23-27
10	seconds = toffoli * 1e-6 / 100 # 100-way parallel magic-state factories
11	return {
12	'rsa_bits': n_bits,
13	'logical_qubits': logical_qubits,
14	'physical_qubits_orderof': physical,
15	'toffoli_count': toffoli,
16	'wallclock_hours_orderof': round(seconds / 3600, 1),
17	'code_distance': d,
18	}
19
20	import math
21	for n in [1024, 2048, 3072, 4096]:
22	print(estimate(n))

TL;DR ¶

1. Where 20M came from ¶

2. What's moved in 2024-2026 ¶

3. The break, sketched ¶

4. A toy factor on tiny N ¶

5. A resource estimator ¶

6. What this means in 2026 ¶

7. References ¶

RELATED OPS

Inside the NIST PQC suite: ML-KEM (FIPS 203), ML-DSA (FIPS 204), SLH-DSA (FIPS 205)

Q-day: how analysts are pinning the window between 2029 and 2034

Grover bites AES: why 128 is dead and 256 is your new baseline

Privacy by design

No third-party cookies

No telemetry

Per-user encryption

4. A toy factor on tiny `N` ¶