Shor 算法通过将因式分解简化为周期查找问题，并利用量子计算技术（如叠加态和量子傅里叶变换 (QFT)），以指数级的速度解决因式分解问题，比传统方法更快。传统的因式分解算法，如一般数域筛法，所需时间随输入数字的位数呈指数增长，这使得它们在处理大数时变得不切实际。相比之下，Shor 算法以多项式时间运行，因为它用一个量子子程序代替了穷举搜索，该子程序可以有效地识别模运算中的模式。
该算法首先选择一个与要分解的数 *N* 互质的随机整数 *a*。如果 *a* 与 *N* 共享一个因子，问题就立即解决了。否则，Shor 算法寻找最小的整数 *r*（称为周期），使得 *aʳ ≡ 1 mod N*。用经典方法找到这个周期需要计算 *aˣ mod N*，对于递增的 *x*，直到检测到重复——这个过程随着 *N* 的大小呈指数增长。量子计算机通过使用叠加态避免了这个瓶颈：一个量子寄存器同时计算所有 *x* 的 *aˣ mod N*。然后，QFT 通过放大正确的频率从这个叠加态中提取周期 *r*，这个步骤随着 *N* 的位数呈多项式增长。
例如，要分解 *N=15*，Shor 算法可能会选择 *a=7*。序列 *7¹ mod 15=7*，*7²=49 mod 15=4*，*7³=28 mod 15=13*，*7⁴=91 mod 15=1* 显示周期 *r=4*。使用 *r*，经典步骤计算 *gcd(7^(4/2)±1, 15)*，得出因子 3 和 5。量子加速来自在 *O((log N)³) * 时间内找到 *r*，而经典方法需要 *O(exp((log N)^(1/3)))* 时间。对于更大的 *N*，这种效率差距呈指数增长，使得 Shor 算法对于密码学具有变革性意义，其中大素数是基础。该算法的结构——量子周期查找后接经典后处理——演示了混合量子-经典方法如何解决其他方法难以解决的问题。