Shor 算法由 Peter Shor 于 1994 年提出，可以使用量子计算机在多项式时间 O((log N)³) 内分解一个整数 N。已知最佳的经典算法（普通数域筛法）以亚指数时间运行。这一点意义重大，因为 RSA 加密依赖于分解大数的困难性。Shor 算法使用量子傅里叶变换来求一个模幂函数的周期。虽然该算法在理论上非常强大，但在真实硬件上运行它以破解 RSA-2048 将需要数百万个纠错后的量子比特——远超当前 NISQ 的能力（其量子比特数最多约为 1000 个含噪量子比特）。Shor 算法是后量子密码学研究以及 NIST 后量子密码标准化工作的主要动因。
相关术语
QFT
Algorithms量子傅里叶变换（Quantum Fourier Transform）——离散傅里叶变换的量子对应物，速度呈指数级更快。
阅读更多
量子相位估计（Quantum Phase Estimation）
Algorithms一种估计幺正算符本征值相位的算法：是 Shor 算法和量子化学能量计算背后的核心子程序。
阅读更多
量子纠错（Quantum Error Correction）
Hardware在不测量（并坍缩）量子比特的情况下检测和纠正量子线路中错误的技术。
阅读更多
NISQ
Hardware含噪中等规模量子（Noisy Intermediate-Scale Quantum）——具有 50–1000 个量子比特但没有完整纠错的设备。
阅读更多