按年被提到
20192019 · 7 次2026
物理与量子›量子计算·arXiv:1905.09749 · quant-ph

How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits

用 2000 万个含噪量子比特在 8 小时内分解 2048 位 RSA 整数
Craig Gidney, Martin Ekerå · 2019

估算:2000 万含噪量子比特 8 小时分解 RSA-2048

开始阅读 ↗PDFalphaXiv 讨论
被推荐 · 16 人首次 2019-05-24 · 最近 2026-03-31
16不同的人
14活跃月份
18讨论串
891被引(OpenAlex)

论文综合 Shor 等人的多项前人技术,在平面超导量子比特网格、10^-3 的物理门错误率、1 微秒表面码周期等较现实的假设下估算分解成本,并计入噪声、重复尝试和时空布局等通常被忽略的因素。分解 2048 位 RSA 整数的时空体积比早期估算小约一百倍,约需 2000 万物理量子比特和 8 小时;作者还量化了这一结果对 RSA 与有限域离散对数密码体系的影响。

HN 为什么提它

评论者在讨论量子计算何时能威胁 RSA 时,把它当作标准的资源估算(2000 万含噪量子比特、8 小时)来引用,后来也有人追溯其中 0.1% 错误率假设的来源。

方法难度 5 / 5约 90 分钟有时效性
读之前最好知道
1Shor 算法
2量子纠错与表面码(surface code)
3RSA 与离散对数密码学
4量子电路与 Toffoli 门

学习路径

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

先看 Shor 算法和表面码纠错的基础,再看超导量子比特的容错阈值和资源估算,最后读 RSA-2048 的成本估计。

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

    Shor 算法是被估算成本的对象。

    读理解分解整数如何归约为周期查找,以及量子部分的作用。

  2. 2
    Surface codes: Towards practical large-scale quantum computation表面码:迈向实用的大规模量子计算 · 2012

    表面码是本文成本估计所假设的纠错方案。

    读抓住稳定子、逻辑量子比特、码距与逻辑门的基本概念。

  3. 3
    Logic gates at the surface code threshold: Superconducting qubits poised for fault-tolerant quantum computing表面码阈值处的逻辑门:超导量子比特已为容错量子计算做好准备 · 2014

    给出超导量子比特接近表面码阈值的实验基础,支撑本文物理假设。

    读了解门保真度与表面码阈值的关系。

  4. 4

    同类的量子资源估算,是估算量子电路规模与成本的参考方法。

    读了解如何把算法拆成门电路并估算量子比特与门数量;细节略读。

  5. 5
    How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits用 2000 万个含噪量子比特在 8 小时内分解 2048 位 RSA 整数 · 2019 · 就是这篇

    综合多项优化技术,估算在合理物理假设下分解 RSA-2048 所需的量子比特数与时间。

    读抓住物理假设(门错误率、表面码周期)和资源估算的结果,以及主要的节省来源。

HN 书评

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

“That goes into a clear discussion of how to build a quantum computer and the associated thresholds that would allow you to do so.”

推荐它清楚讨论了如何构建量子计算机及所需门槛
Quantum Resistance and the Signal Protocol原评论 ↗
引用nabla9 · 2019-10

“Consider recent improvement in RSA factorization”

引用 RSA 分解的近期进展,即 2000 万含噪量子比特 8 小时分解 2048 位
Ask HN: How secure personal information is in Quantum Supremacy world?原评论 ↗
引用nabla9 · 2020-01

“How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits shows how to significantly”

引用它说明破解 2048 位 RSA 所需的量子比特资源估算
A Graduate Course in Applied Cryptography原评论 ↗
引用Strilanc · 2020-05

“Shor's algorithm uses this technique [4].”

指出 Shor 算法用了其中的进位填充技巧
The radix 2^51 trick (2017)原评论 ↗
引用bnjemian · 2021-11

“Gidney and Ekerå have you covered: How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits”

指出 Gidney 和 Ekerå 的论文已给出破解 RSA-2048 的估算
IBM unveils 127-qubit quantum processor原评论 ↗
引用reikonomusha · 2023-01

“More realistically [1], you'd have a factor of around 1,600 for a distance-27 code.”

引用它说明更现实的情况下距离 27 码的开销约 1,600 倍
Breaking RSA with a Quantum Computer原评论 ↗
看全部 12 条 →
引用amirhirsch · 2024-09

“this suggests the scale for RSA2048: How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits”

引用它说明破解 RSA2048 所需的规模
Qubit Transistors Reach Error Correction Benchmark原评论 ↗
引用qnleigh · 2024-12

“A paper from Google in 2019 estimates needing ~20 million physical qubits”

引用 Google 2019 年的论文,估计需要约 2000 万物理量子比特
Willow, Our Quantum Chip原评论 ↗
引用wzeng · 2025-01

“Details for how this could work for factoring are here: How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits”

贴出论文,说明纠错量子硬件如何用于分解的细节
Looking at some claims that quantum computers won't work原评论 ↗
引用ryao · 2025-04

“Coincidentally, the following paper claims that cracking a 2048-bit RSA key can be done in 8 hours with 20 million physical qubits:”

引用它声称 2000 万物理量子比特 8 小时可破解 2048 位 RSA 密钥
Fujitsu and RIKEN develop world-leading 256-qubit sup quantum computer原评论 ↗
引用Strilanc · 2025-11

“Even if the qubits are noisy [7].”

强调即使量子比特含噪,也引它给出破解 RSA-2048 的资源估算
Keeping the Internet fast and secure: introducing Merkle Tree Certificates原评论 ↗
引用upofadown · 2026-03

“That seems to have come from the "20 million noisy qubits to break RSA" scheme[1] from back in 2019.”

指出该说法源自 2019 年的 2000 万含噪量子比特破解 RSA 方案
Securing Elliptic Curve Cryptocurrencies Against Quantum Vulnerabilities [pdf]原评论 ↗
被提交为 story · 6 次