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

Peter W. Shor · 1994 / 1997 / 1999 · LNCS（ANTS 1994）；SIAM J. Comput. 26:1484–1509；SIAM Review 41:303–332

| 编号 QQFT028 | 主题 量子傅里叶变换 | 链接 DOI 10.1137/S0097539795293172 |

摘要

摘要保留原文（英文）

摘要取自 Crossref 出版方元数据（SIAM J. Comput. 版），未作翻译，以保证与原文一致。

A digital computer is generally believed to be an efficient universal computing device; that is, it is believed able to simulate any physical computing device with an increase in computation time by at most a polynomial factor. This may not be true when quantum mechanics is taken into consideration. This paper considers factoring integers and finding discrete logarithms, two problems which are generally thought to be hard on a classical computer and which have been used as the basis of several proposed cryptosystems. Efficient randomized algorithms are given for these two problems on a hypothetical quantum computer. These algorithms take a number of steps polynomial in the input size, e.g., the number of digits of the integer to be factored.

读法提示

摘要是 SIAM J. Comput. 版的前言部分，不是全文摘要。本站引用本条目只用它一件事：QFT 在因数分解中用于读出周期。线路层面的四段结构见Shor 线路路线图，QFT 本身的实现取舍见近似与截断 QFT。

本站词条在引用该文献时，会以 wikilink（sources/QQFT028）链接到本页；右侧「反向链接」面板自动列出所有引用它的词条。