Shor：动摇互联网根基的因式分解

前两篇是"开胃菜"。这一篇，我们讲那个真正让密码学家失眠的算法——Shor 算法。

它做的事听起来很朴素：把一个很大的数，分解成两个质数相乘。比如 15 = 3 × 5。可正是这件"朴素"的事，撑起了今天互联网大半的加密。Shor 证明：在足够大的量子计算机上，这件事可以快到可怕。

一、先搞懂：为什么"分解大数"这么难

你秒算得出 3 × 5 = 15。但反过来——给你 15，找出 3 和 5——也不难，因为数小。

可如果给你一个几百位的数，要找出它是哪两个质数相乘？经典电脑只能一个一个质数去试除。数字每多一位，要试的次数就暴涨。一个 2048 位的数字，用现有最快的电脑去硬算，所需时间比宇宙年龄还长（这正呼应第 1 篇的"指数爆炸"）。

而现代加密（比如 RSA）正是建立在这个信念上："相乘容易，分解极难"。信息公开锁着一把"大数锁"，只有知道那两个质数"钥匙"的人能开。

二、Shor 的"作弊"思路：把乘法难题，变成频率难题

Shor 的聪明，不在于硬试，而在于换问题。

它把"分解 N"这个乘法难题，转化成了一个"找周期"的难题：构造一个序列，它的重复规律（周期）里，藏着 N 的因子。而"找周期"这件事，恰好能用量子计算机叠加着一次性探测——这正是我们前几篇反复说的本事。

把流程画出来：

注意分工：真正"量子加速"的，只是"找周期"那一步；算出因子后的数学，普通电脑就能收尾。Shor 是"量子+经典"的组合拳。

三、它快到什么程度

给个关键对比：

• 经典最优算法分解 N：时间随位数指数级增长（位数翻倍，时间爆炸）；
• Shor 算法：时间只随位数多项式增长（约等于"算很多次乘法"的量级）。

这叫指数级加速——和 Grover 的"平方加速"完全不是一个量级。位数一大，经典要"宇宙年龄"，Shor 可能"几分钟"。

四、别急着 panic：三个现实刹车

讲完吓人的部分，必须踩三脚刹车，免得谣言四飞：

1. 它威胁的是"基于大数分解"的加密（RSA 一类）。银行、网站登录很多用它。但还有其他加密体系（如格密码）目前被认为抗量子； 2. Shor 需要很大的、很稳的量子计算机。今天最大的机器还远没到能分解 2048 位数的程度——这事儿是"未来威胁"，不是"今天已破"； 3. 行业早有准备。抗量子密码（PQC）已经在标准和产品里铺开。Shor 是"倒逼升级"的警钟，不是"世界末日"。

五、为什么它值得被记住

Shor 的意义，远超"破解密码"本身。它是第一个让人看清量子计算能做什么经典做不了的硬核证据：不是模糊的"更快"，而是对某一类问题结构性的降维。

也正是它，让各国和企业真金白银砸进量子研发——因为没人想在被"锁"住之前，才发现自己门上的锁早就锈了。

六、下一篇，聊聊"优势"这个词本身

Shor 这么猛，是不是说明量子已经全面超越了经典？未必。下一篇，我们冷静聊聊《量子优势到底是什么》——这个被炒烂的词，到底意味着什么、又常被怎么误读。

如果今天只记住一句话，那就是：Shor 把"分解大数"变成"找周期"，用量子叠加把指数级难题压成多项式级——这正是它让传统密码学紧张的根源。

下次见。