肖尔算法与 RSA
“量子”课程第 12 课，共 23 课。免费，有动画和小测验。
质数做的锁
你用 HTTPS 打开网站、签署文件、刷卡付款时，背后常常是 RSA 在工作，它诞生于 1977 年。思路很简单：两个大质数相乘很容易，把结果分解回去却非常难。61 × 53 你一分钟就能算出来，但要找出 3233 的因数就费劲多了。RSA-2048 用的是 617 位的数，经典计算机算到宇宙终结也分解不完。
肖尔的诀窍：把分解变成找节奏
1994 年，贝尔实验室的数学家彼得·肖尔发现：分解一个数可以转化成找节奏。取 N = 15 和数字 7。把 7 一次次乘方，取除以 15 的余数：得到 1、7、4、13，然后又是 1、7、4、13。节奏每 4 步重复一次。知道了节奏，用中学算术就能求出因数：3 和 5。小数字的节奏一眼就能看出来，几百位的大数节奏长得像天文数字，这时就需要量子计算机了。
量子计算机怎么“听”出节奏
第一步：同时造出所有乘方的叠加，振幅里藏着一个重复的图案。第二步：量子傅里叶变换，简称 QFT。它干的事跟播放器里的均衡器一样：把信号拆成不同频率。靠干涉，正确的频率被放大，其他的全部抵消。测量后得到一个数，用它就能算出周期。这就是指数级加速：几十亿年的任务变成几小时或几天。
需要多少量子比特，为什么这个数一直在降
纸面上，肖尔算法早就能破解 RSA，但它需要一台带纠错的大型量子计算机。估算数字降得很快。2019 年，克雷格·吉德尼和马丁·埃克罗算出大约要 2000 万个物理量子比特、8 小时。2025 年 5 月，吉德尼给出：不到 100 万个比特、不到一周。2026 年 2 月，初创公司 Iceberg Quantum 宣称一种方案不到 10 万个比特；3 月底，加州理工团队又估算，用中性原子也许 1 万到 2 万个就够。不过两种估算都假设了尚不存在的特殊架构。如今最好的芯片有几千个比特，质量还不够。但差距正在从两头缩小。
受威胁的不只是 RSA
同一个肖尔算法也能破解椭圆曲线。比特币和以太坊的签名、HTTPS 的密钥交换都建立在它上面。2026 年 3 月，谷歌团队与包括密码学家丹·博内在内的合著者估算：破解比特币的曲线不到 50 万个物理量子比特就够，公钥一旦暴露，大约 9 分钟就能破解。而 AES 这类对称加密和 SHA-256 这类哈希不怕肖尔，只受格罗弗“开根号”的影响。加密货币的细节在最后一级讲。
为什么现在就得开始防护
如果大型量子计算机还要好几年才出现，急什么？因为有“先收集，以后再解密”这一招。攻击者今天就能录下加密流量，一直存到能破解的那天。医疗数据、国家机密、私人聊天需要保密几十年。所以 2024 年 NIST 批准了第一批后量子标准，Signal、iMessage 和 Chrome 也已经为普通用户开启了这类保护。
自测一下
- 是什么让 RSA 怕量子计算机？
正确答案: 分解能转化为找周期，而 QFT 擅长找周期. 肖尔把分解变成找节奏，QFT 靠干涉把节奏挑出来。指数级加速就来自这里。 - Q-Day 还早，为什么现在就要保护数据？
正确答案: 流量现在就能录下，以后再解密. “先收集，以后再解密”让长期数据今天就面临威胁。 - 下面哪个肖尔算法破解不了？
正确答案: AES-256. AES 是对称加密，没有可供肖尔利用的“节奏”。只有格罗弗能影响它，而 256 位密钥扛得住。
← 格罗弗算法：量子搜索 模拟分子 →