Factoring ยท Algorithms
Logical-resource estimate for factoring RSA-2048
Theorem statement
Suppose an RSA-2048 public key has known public modulus $N$, whose private prime factors are unknown distinct primes $p$ and $q$. There exists a quantum algorithm that returns $d\in\{p,q\}$ with probability at least $2/3$, using $6.19\times 10^3$ logical qubits, $8.1\times 10^9$ Toffoli gates, $6.42\times 10^9$ maximal circuit depth, and $3.69\times 10^4$ classical arithmetic operations.
- $$N$$
- Known public modulus.
- $$p$$
- Unknown private prime factor.
- $$q$$
- Unknown private prime factor.
- $$d$$
- Recovered prime factor.
Sources
- How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits
Craig Gidney, Martin Ekera, 2019
Lean context
- Lean declaration
QuantumAlg.Factoring.FormulaEnvelope.RSA2048.main
Copy a short prompt with the import, theorem name, citations, and public source link.