按年被提到
19952016 · 1 次2026
物理与量子›量子计算·arXiv:quant-ph/9508027 · quant-ph

Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer

量子计算机上素因数分解与离散对数的多项式时间算法
Peter W. Shor · 1995

量子计算机上多项式时间的整数分解与离散对数算法

开始阅读 ↗PDFalphaXiv 讨论
被推荐 · 3 人首次 2016-08-25 · 最近 2023-01-03
3不同的人
3活跃月份
3讨论串
8,537被引(OpenAlex)

论文指出,若考虑量子力学,数字计算机未必能以多项式因子的开销模拟任何物理计算设备。作者针对整数分解和离散对数这两个被认为在经典计算机上很难、且是多种密码系统基础的问题,给出了假想量子计算机上的高效随机算法,所需步数是输入规模(如待分解整数的位数)的多项式。

HN 为什么提它

HN 评论者在谈量子计算对密码学的影响时引用它,称赞 Shor 的分析极为严谨,并指出原文讨论了需要多次运行及时间复杂度。

奠基之作难度 4 / 5约 100 分钟经得起时间
读之前最好知道
1量子计算基础(qubit、量子门)
2量子傅里叶变换(quantum Fourier transform)
3数论基础(模运算、阶、连分数)
4RSA 与离散对数密码学
5计算复杂性(多项式时间)

学习路径

读这篇之前,按顺序读书架上的 1 篇 · 参考文献来自 OpenAlex,顺序和要点由 Claude Code 排出

候选只有一篇与量子计算能力边界相关的论文,它是目标论文之后的回顾性材料,帮助判断量子算法究竟强在哪里。

  1. 1

    讨论量子计算能解决什么、不能解决什么,可以带着它回头衡量 Shor 算法的意义与边界。

    读量子计算在黑箱搜索等问题上的上下界,以及为何不能期待量子计算机轻易解决 NP 完全问题。

  2. 2
    Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer量子计算机上素因数分解与离散对数的多项式时间算法 · 1995 · 就是这篇

    目标论文:给出量子计算机上整数分解与离散对数的多项式时间算法。

    读把分解归约为求周期,量子傅里叶变换如何提取周期,以及离散对数的处理思路;物理模型细节可略读。

HN 书评

推荐在前,同类按时间 · 每篇最多保留 20 条,统计用全部提及
推荐Strilanc · 2023-01

“One of the things that stands out to me about Shor's paper is how meticulous he is.”

称赞 Shor 这篇论文非常严谨,细致分析了量子分解的失败情形
Breaking RSA with a Quantum Computer原评论 ↗
引用Cieplak · 2016-08

“Supposedly his proof is valid, predicated on the existence of quantum computers.”

指出据说他的证明有效,但以量子计算机存在为前提
Factoring may be easier than we think原评论 ↗
引用kirrent · 2018-02

“Shor's original paper discusses the fundamental need for several runs and gives the time complexity.”

指出 Shor 原论文讨论了需要多次运行的必要性并给出时间复杂度
An Argument Against Quantum Computers原评论 ↗