量子计算机Shor算法如何破解现代互联网加密系统

作者toby，文章来源量子计算机Shor算法如何破解现代互联网加密系统

现代密码的安全，建立在一个朴素的信念上：把两个大质数乘起来很容易，但想从乘积倒推回那两个质数，难如登天。Shor 算法之所以震撼，是它没有"更快地尝试"，而是换了一条路——把质因数分解，变成了量子计算机极其擅长的"找周期"问题

01 · 加密的地基

为什么"大数分解"是一座堡垒

先看一个小例子：383 × 401 = 153583。乘法这一步，小学生都能算。但反过来——只告诉你153583，让你找出它是哪两个质数相乘——你就得从头试除。

用最朴素的试除法，要从 2 一直试到 √153583 ≈ 392，大约 400 次尝试。对这个玩具数字，眨眼就完。但现实中的 RSA 密钥，那个大数是2048 位二进制起步的庞然大物：

这不是"慢"，而是物理上不可能——把地球上所有超级计算机连起来算到太阳熄灭，也分解不了一个 2048 位的 RSA 大数。这道"易正难反"的数学鸿沟，就是 RSA、以及你每天用的 HTTPS、网银、数字签名的安全地基。

02 · 量子比特

量子比特：同时是 0 和 1

经典比特非 0 即 1，像一枚正面或反面朝上、已经落定的硬币。量子比特（qubit）则像一枚正在高速旋转的硬币：在你观测它之前，它处于 0 和 1 的叠加态——同时携带两种可能。

威力在于叠加会指数级放大：1 个 qubit 承载 2 种状态，20 个 qubit 就能同时代表 2²⁰ ≈ 100 万个数字。我们例子里的 153583，只需 20 个量子比特构造叠加态，就能"一次性装下"从 0 到 153583 的所有数。

关键澄清：叠加≠"同时算完所有答案再挑一个"。如果直接观测，叠加态会随机坍缩，其余信息全部丢失。Shor 的精妙在于它不直接观测，而是先用巧妙的量子电路让"有用的信息"浮现出来。

03 · 核心转折

把"分解"翻译成"找周期"

这是整个算法最天才的一步。Shor 没有硬碰硬去分解 N，而是随便挑一个和 N 互质的数——比如a = 17——去研究这样一个序列：

"某数的幂除以 N 取余数"的序列，一定会循环——转一圈后余数会回到 1。这个循环长度就叫周期 r，即满足 aʳ mod N = 1 的最小正整数。

为什么找到周期 r 就能分解 N？数论给出了一座桥：只要 r 是偶数，那么下面两个数极大概率各自与 N 共享一个真实的质因数：

分解完成。整个难题就此坍缩成一句话：只要能找到周期 r，RSA 就破了。用经典计算机找这个周期，仍要试约 N 次——真正的救兵，是量子计算机。

04 · 量子加速

量子计算机如何"一眼"看出周期

量子机器的杀手锏分两步：先用叠加态一次性算出所有余数，再用量子傅里叶变换（QFT）把藏在其中的周期"共振"出来。

为什么只需很少几次测量？因为量子系统的坍缩是真随机的——每次观测都独立地落在某个波峰上。测几次，就能从这些峰的位置反推出它们共同的"间距"，也就是周期 r。经典机器要跑约 N 次的活，量子机器用寥寥几次测量搞定。

05 · 加密的终局

经典 vs 量子：一张表看懂差距

⚠ "先窃取，后解密"：威胁已经发生

足够大、足够稳定的通用量子计算机尚未造出，但威胁并非未来时。攻击者可以今天就截获并囤积大量加密数据（网银流水、政务档案、商业机密），等量子计算机成熟后再统一解密——

"Harvest Now, Decrypt Later" · 先收割，后解密

今天用 RSA 加密的长期敏感数据，其保质期正在被量子时代倒计时。这正是全球密码学界紧急推动后量子密码（Post-Quantum Cryptography）的根本原因。

06 · 尾声

数学，从来都是最锋利的武器

Shor 算法的美，不在于"算得更快"，而在于它换了一个提问方式：把守护整个数字世界的"大数分解"难题，悄悄翻译成量子计算机天生擅长的"找周期"游戏。那道曾被认为固若金汤的堡垒，就此从内部被瓦解。

从图灵用逻辑破译 Enigma，到 Shor 用周期动摇 RSA，历史反复证明同一件事：真正决定攻防胜负的，往往不是更强的算力，而是更深刻的数学洞察。量子时代的密码战，才刚刚开始。

"数学不是冰冷的符号，它曾经是枪炮，是情报，是决定国家命运的力量。"

版权声明：文章来自公众号(python风控模型),未经许可，不得抄袭。遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。