Shor order finding and factoring assumptions
Research context
research method · established · As of 2026-10-10
Shor's factoring algorithm reduces factoring to order finding and uses modular exponentiation, quantum phase/Fourier processing and classical continued fractions.
Key knowledge
Shor's factoring algorithm reduces factoring to order finding and uses modular exponentiation, quantum phase/Fourier processing and classical continued fractions. Its asymptotic cost is polynomial in the integer's bit length under a uniform circuit and arithmetic model. This establishes an algorithmic threat to factoring-based cryptography with sufficiently reliable quantum resources; it does not establish that a present noisy device can factor cryptographically sized integers.
Conditions and scope
- Input is an integer in binary; success probability, repetitions and arithmetic circuit cost are stated.
- Fault-tolerant logical qubits, gate synthesis and error-correction overhead are separate from ideal asymptotic arithmetic.
Sources · 1
References
Sources retain their recorded scope. A source link alone does not establish verification of every statement.
Evidence and review
Author checked this English statement, displayed equation where present and stated hypotheses against these source locations: Quantum circuits, Grover query/amplitude analysis, Shor order-finding resource discussion. The check is bounded to the recorded claims; no complete proof reconstruction, software proof replay or universal literature completeness is claimed.
2026-10-10 · Author source-body/statement/equation/domain check, with graph associations scoped individually. Separate independent content/source/inventory review is required before branch closure.
Entry details
Permanent link to this entry ↗- Record identity
- research-info-shor-order-finding
- Revision
- research.1
- Structured reference record
- Postgraduate & research reference