把一个数做质因数分解，为什么大一点就算不动了？

4 个讲解板块 · 关联 3 款站内工具 · 内容最后核对 2026-10-09

最朴素的试除法要试到根号那么多，位数一涨工作量就指数上升——这正是现代公钥密码的地基。

直接答案

因为朴素的试除法要试到根号那么大。一个 n 位的数，根号大致相当于 2 的 n/2 次方，所以工作量随位数指数上升。对一个 2048 位的数，这意味着 2 的 1024 次方量级的尝试——不是慢一点，是任何可预见的计算机都做不完。

更聪明的算法确实存在：Pollard 的 rho 方法用伪随机序列找因子，期望量级降到四次方根；二次筛法和数域筛法进一步压到亚指数。但对精心挑选的大数，它们依然不可行。乘法容易、分解难，这个不对称正好可以用来造锁。

一个数乘起来很快，拆回去可能极慢。小学生都知道 15 等于 3 乘 5，但换成一个几百位的数，目前人类最快的算法也要天文时间。

算术基本定理保证了每个合数都能分解，它没有保证分解很快。这个缝隙就是公钥密码学站住的地方。

每一代算法都是在用更聪明的办法减少尝试次数。

算法	思路	量级	2048 位可行吗
试除法	从 2 试到根号，逐个除	根号 N，约位数的二分之一次方	不可行
Pollard rho	伪随机序列找循环，用最大公约数提因子	N 的四分之一次方	不可行
二次筛法	找平方同余的数对，从差里提出因子	亚指数	实用上限约几百位，再大不可行
数域筛法	当前最强的经典算法	亚指数	不可行

注意亚指数的意思：指数虽然仍比线性慢得多，但已经比纯指数好很多，这让几百位的数变得可以挑战、上千位依然安全。

关键是位数，而不是数值大小给人的直觉。

位数在指数位置上: 工作量的公式里，位数出现在指数里。所以每多一位，难度不是加一点，而是乘一档。
历史纪录就是标尺: 一个四百多位的挑战数在九十年代动用上千台机器跑了几个月；六百多位用了两年；再往上只在学术团队手里偶尔被攻破。
安全参数按年份留余量: 当前的共识是 2048 位属于可接受的下限，十年以上寿命的系统建议用 3072 位，最敏感的场景用 4096 位。1024 位已经不再推荐。
真正难的是两个大素数的积: 对随机的大合数，它的因子可能很小、很容易被试除出来；而密码学用的是两个大小相当的素数相乘，这种数最难拆。

所以「大数分解难」这句话要精确成：对特定结构的大合数难，而不是对所有大数都难。

不对称性本身就是可以拿来用的资源。