Shor's algorithm: the RSA factoring bill

Algorithm preset

Logical qubits

Toffoli gate count

T-depth (serial layers)

Physical error rate

Code cycle time

Error budget

Physical qubits (total)

Estimated runtime

Code distance

Surface-code rounds of redundancy

Data-block physical qubits

2 × logical × d²

T-gate count

4 T per Toffoli

Physical per logical

Error-correction overhead factor

Highlighted share: magic-state factories (conservative bound shown).

Shor's algorithm vs RSA: the real cost of factoring

Shor's 1994 algorithm factors an n-bit RSA modulus in polynomial time - but "polynomial" hides the bill. The standard modern costing is Gidney & Ekerå (2019/2021): RSA-2048 needs about 6,189 logical qubits and 2.6×10⁹ Toffoli gates, which they mapped to ~20 million physical qubits running 8 hours with a heavily parallel factory layout. In 2025, Gidney showed better distillation and storage tricks cut that to under 1 million physical qubits and under a week.

The calculator above is pre-loaded with the Gidney-Ekerå logical figures and a serial T-depth, so its default answer (12-23 million qubits, about a day) deliberately brackets the published parallel results. Try these experiments:

Drop the physical error rate from 0.1% to 0.01% - the machine shrinks roughly 5x. Hardware quality beats qubit count.
Cut the T-depth by 100x (what aggressive parallel factories achieve) and watch runtime fall from a day to minutes.
Switch RSA-2048 to RSA-4096 - cost roughly triples. Key size buys classical time, not quantum safety.

Should you panic about RSA?

Not today - the largest Shor-style demonstrations remain toy numbers - but migration is a decades-long logistics problem, which is why NIST finalized post-quantum standards (ML-KEM, ML-DSA, SLH-DSA) in 2024 and agencies are telling everyone to inventory cryptography now. "Harvest now, decrypt later" means data with a long secrecy lifetime is already exposed to future machines.

Sources: Gidney & Ekerå, Quantum 5, 433 (2021), arXiv:1905.09749 · Gidney (2025), arXiv:2505.15917 · Fowler et al., Phys. Rev. A 86, 032324 (2012).