王座上的算法：Shor I（问题与思路）

先备导航：你需要 036（QFT 与相位估计的预告）、033/034（模板与谱系）、021/022（H、CNOT）、015（多比特账本）。

下一篇预告：038《王座上的算法：Shor II（电路与成本）》。

王座上的算法：Shor I（问题与思路）

1994 年 4 月，一则消息在密码学界炸开：有人证明，如果造出足够大的量子计算机，RSA 这类"现代密码地基"级别的问题会被高效破解。这台还没影子的假想机器，一夜之间成了全世界实验室的立项理由——量子计算这个领域此后三十年的经费曲线，很多就从那条消息起跳。

本篇讲清两件事：RSA 的地基为什么偏偏压在"分解大数"上，以及量子的思路为什么偏偏挑得动它。电路与成本账留到 038 篇。

先看地基：分解与密码的联姻

把两个大质数相乘，得到一个大数 N——这是乘法，任何计算器瞬间完成。反过来，只给你 N，找出它的两个质因数——这是分解，对经典计算机是出了名的苦役：几百位的 N，把全世界算力捆起来跑，宇宙年龄过去也跑不完。

"乘起来容易、拆回去极难"——这个不对称就是 RSA 密码的地基：公钥用 N（谁都能加密），私钥藏着两个质因数（只有主人能解密）。窃听者拿到 N 想解密？先把 N 分解了再说——而分解是苦役，所以安全。

注意一个精妙处：解密所需的全部信息并没有消失——它就"卷"在 N 里面（N 是两个质数的乘积，账目上是守恒的），经典世界读不出，只是因为拆开它的代价是天文数字。这与量子信息的老熟人"信息没丢、只是读不到"（018 篇）神似——但别急着类比，量子的破法走的不是"暴力拆"，是一条谁也想不到的绕行路线。

绕行路线：把分解变成找周期

思路的转折点是数学里一件漂亮的旧家当（三百年前就有人证明，名字不必记）：分解 N，可以完全化归为"找周期"。

构造如下。随机挑一个数 a（与 N 无公因数），写下幂序列：

a、a²、a³、a⁴…… 除以 N 的余数

这个序列迟早开始循环：存在一个周期 r，使得 a^(x+r) 的余数总等于 a^x 的余数（序列每隔 r 步重演）。三百年前的定理保证：拿到这个 r，分解 N 就只剩几步加减乘除（概要：r 是偶数且 a^(r/2) ± 1 与 N 有公因数——求公因数是经典计算机的快活事）。

举例感受一下（小数字版）：N=15，取 a=7，余数序列 7、4、13、1、7、4、13、1……周期 r=4；a^(r/2)−1=48、a^(r/2)+1=50，与 15 的公因数分别是 3 和 5——分解完成。真实的 N 有几百位，道理不变，唯一的天堑只剩一处：

r 有多大？序列多久开始重演？经典计算机不知道，只能一步步算余数——而这一算就是指数级。

于是整场战役缩成一个纯技术问题：怎么在一个"周期隐藏在幂序列里"的问题上，快速找到周期 r？

而你恰好知道答案的形状——036 篇刚立过传的那台机器，专吃周期，吐出频率。

装配：四件零件拧成一台机器

Shor 算法 = 把本章前四篇的零件按说明书拧起来（概念版流程，电路细节 038 篇）：

零件一：造幂序列的量子版（015 篇的多比特账本 + 模运算黑箱）。用两组寄存器：x 寄存器铺开全部指数（H 门，021 篇），y 寄存器吃进 a^x mod N——黑箱一次调用，所有指数的余数同场（031 篇宪法：叠加让全部输入同时过门）。

零件二：QFT 换轴（036 篇）。y 寄存器此时可以扔了（测一下或直接忽略），x 寄存器上的振幅分布带着周期 r 的花纹——QFT 进，频率峰出。

零件三：测量取样本（036 篇的"瞥一眼"）。对 x 寄存器测量一次，高概率落在接近 k/r 的分数位置上（k 是某个未知的小整数——频率总是周期的整数倍，036 篇讲过）。

零件四：经典收尾。重复跑几遍，收几个"接近 k/r 的分数"，用经典的连分数技巧从分数里反推出 r——然后套三百年前的定理，几步经典算术拆出质因数。量子只干一件事：找 r。其余全是经典世界自己的熟练工。

核算总账：量子部分的调用与门数是 n 的多项式（n 是 N 的比特数）——对比经典分解的指数级，这是指数加速，034 篇谱系规律的顶格兑现。承诺是什么？"周期性"——而幂序列的周期性不是人造的黑箱怪癖，是数论的固有结构：这就是它比 BV/Simon 的"承诺问题"值钱得多的原因——这次，问题本身是人间刚需。

王座的意义与天堑的位置

Shor 算法的历史地位不用吹：它证明了量子计算机（若造得出）不是"更快的计算器"，而是"另一种机器"——某些经典世界的天堑，在量子账本上只是缓坡。RSA、椭圆曲线等一大类公钥密码的"地基不可拆"假设，从数学定理变成了有条件的工程问题。

但天堑的位置必须摆准（039 篇专讲）：拆一个真实世界几百位的 N，需要几百万个物理量子比特、纠错齐备的容错机器——今天的机器（几百到上千个含噪比特）离它还有量级的距离。"原理上可行"与"今天可拆"之间，隔着第六批要讲的全部纠错工程。理论王座早已铸好，登基日期未定——这个诚实的句读，是谈论"量子威胁论"时唯一的清醒姿势。

把类比拆掉

"绕行路线"类比借了哪里：

• 不像之一：绕行通常意味着绕远、更慢；Shor 的绕行更短——量子调用次数是多项式，比经典的指数"直路"短得多。类比借的是"不正面攻城、找隐藏通道"，不借"远"。
• 不像之二："找周期"听起来像找模式、可能失手；量子找周期是概率放大到近乎确定——QFT 的峰把成功率顶到接近 1，剩下的小失败概率重跑几遍即指数压低。算法是"高概率正确"，不是"碰运气"。

带走的行李

1. RSA 的地基是"乘易拆难"；分解可以化归为找幂序列的周期 r（三百年的数论家当），拿到 r 只剩经典快活算术——整场战役的关键点收敛到一个词：周期。 2. Shor=四件套装配：模运算黑箱铺开全部指数 → QFT 把周期变频率峰 → 测量取一个样本 → 经典连分数反推 r；量子调用次数是多项式级——指数加速，承诺是数论的固有周期性。 3. 王座与天堑并存：原理上公钥密码的地基可拆；现实需要容错级的大机器（百万比特），今天没有——"威胁"是数学的，不是日程表的（039 篇展开）。

下一站的钩子：流程图四步走完了，"模运算黑箱"这台唯一的自定义零件怎么造？电路长什么样、要多少门、账单贵在哪？038《王座上的算法：Shor II（电路与成本）》。

#量子计算 #从硬币到纠错 #Shor算法 #RSA