Shor 算法由 Peter Shor 于 1994 年提出，可以使用量子计算机在多项式时间 O((log N)³) 内分解一个整数 N。已知最佳的经典算法（普通数域筛法）以亚指数时间运行。这一点意义重大，因为 RSA 加密依赖于分解大数的困难性。Shor 算法使用量子傅里叶变换来求一个模幂函数的周期。虽然该算法在理论上非常强大，但在真实硬件上运行它以破解 RSA-2048 将需要数百万个纠错后的量子比特——远超当前 NISQ 的能力（其量子比特数最多约为 1000 个含噪量子比特）。Shor 算法是后量子密码学研究以及 NIST 后量子密码标准化工作的主要动因。