出处已验证第 4 级
Shor算法
Shor算法在多项式时间O((log N)³)内分解大整数，威胁RSA密码。
这是什么意思
将因式分解归约为用量子傅里叶变换求解的周期寻找问题。推动后量子密码学研究。生活类比
像找到复杂乐曲的秘密节奏。
像找到保险箱的共振频率。
常见误解
- 不能立即破解所有加密。
- 当前量子计算机无法运行。
要点总结
- O((log N)³)因式分解。
- 归约为QFT周期寻找。
- 推动后量子密码学。
检验你的理解
Shor算法将因式分解归约为什么问题？
- A.矩阵乘法
- B.周期寻找
- C.图着色
- D.排序
查看答案
答案: B. 周期寻找
原因: 归约为周期寻找问题。
先修概念
一次文献: Shor, SIAM J. Comput. 26, 1484 (1997), doi:10.1137/S0097539795293172
Hardware-status sentences ('current quantum computers cannot factor...') are explicitly era-qualified honesty statements protecting against hype; algorithm itself is established mathematics.