Reducing base range from N to N/2.
This repository contains my preprint “Shor’s Algorithm Base Range Reduction: Symmetry of Successful Bases.”
The note proves a structural property of Shor’s algorithm: if a base a is successful, then its mirror N − a is always also successful with the exact same order. This symmetry implies that successful bases occur in pairs, and the effective search range for bases can be reduced to 1 < a < N/2 without any loss of probability.
Quantum Computing Stack Exchange Discussion (Proof Validated by Craig Gidney - Quantum Software Engineer at Google)
This work is licensed under the Creative Commons Attribution 4.0 International (CC BY 4.0).
See the LICENSE file for details.
If you use or reference this work, please cite:
Bhatti, Muhammad Saad. Shor's Algorithm Base Range Reduction: Symmetry of Successful Bases. Preprint, 2025.
Available at: https://github.com/saadbhattii/Shors-Algorithm-Base-Range-Reduction