Factoring RSA moduli
Factor balanced semiprimes without supplied structure or partial key information. Asymptotic bounds are separate from concrete challenge factorizations.
Balanced semiprimes · quantum
Logical quantum computation with polynomial classical post-processing
Results
| # | PUBLICATION / AUTHORS | DATE | TIME BOUND | SPACE BOUND | EVIDENCE |
|---|---|---|---|---|---|
| — | Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum ComputerSIAM Journal on Computing 1997SourceBibTeX / details | 30 Aug 1995 | poly(log N) quantum and classical work | Not extracted from the source | PublishedSource checked |
Comparison definition & assumptions
- Regime
- Logical quantum computation with polynomial classical post-processing
- Computation
- Quantum
- Rigor
- Provable
- Instances
- RSA-type balanced semiprimes
- Cost scale
- Expression only
- Parameter
- n = ceil(log₂ N)
- Description
- Quantum asymptotic factorization bounds for RSA-type semiprimes. Concrete resource estimates require an explicit circuit and error-correction model.
- Comparison rules
- Quantum asymptotic factorization bounds for RSA-type semiprimes. Concrete resource estimates require an explicit circuit and error-correction model. Only compare entries with this cost scale, input domain and computational model. Polynomial and quasi-polynomial expressions without an extracted scalar are not ranked.
- Tags
- rsa, quantum, polynomial time