在前端网页里写一个质因数分解计算器，听起来像是一道大一编程初学者的随堂作业题：一个循环从 2 走到 n\sqrt{n}，能整除就除尽，除不尽就递增。

但如果这个工具面向真实用户开放，允许输入高达 20 位的整数（2≤n≤264−12 \le n \le 2^{64}-1），朴素的写法会在第一个大数面前彻底翻车：在单线程的 JavaScript 浏览器主线程中，一个略小于 2532^{53} 的素数试除需要近 1 亿次循环和模运算，直接把页面冻结 3 秒以上，甚至触发浏览器的“网页无响应”崩溃弹窗。

这篇文章复盘我们把这个工具从最原始的试除死循环，一路重构到确定性 7 基数 Miller–Rabin、Pollard–Brent 周期检测、128 步批量 GCD 及因数 2 位运算剥离的完整流水线。

1. 朴素试除法在 Web 端的三个致命硬伤

最初的质因数分解逻辑是典型的教科书朴素写法：

// 早期朴素试除逻辑
let rest = n;
let div = 2;
while (div * div <= rest) {
	let count = 0;
	while (rest % div === 0) {
		rest /= div;
		count++;
	}
	if (count === 1) parts.push(String(div));
	else if (count > 1) parts.push(`${div}^${count}`);
	div++;
}
if (rest > 1) parts.push(String(rest));

// 算约数个数：居然又拿原数做了一次一模一样的循环！
let divisors = 1;
let r2 = n;
for (let i = 2; i * i <= n; i++) {
	let c = 0;
	while (r2 % i === 0) {
		r2 /= i;
		c++;
	}
	if (c) divisors *= c + 1;
}
if (r2 > 1) divisors *= 2;

这段代码在小数字下看起来一切正常，但在工程和算法上有三个严重的缺陷：

缺陷一：连偶数都没有跳过

循环每次仅仅是 div++（2, 3, 4, 5, 6, 7…）。在 2 被除尽之后，所有后续偶数（4, 6, 8, 10…）都不可能再整除，但代码依然忠实地对每一个偶数执行了昂贵的模运算。

缺陷二：低级的二次冗余计算

根据约数个数定理，若整数的标准分解式为：

n=p1e1⋅p2e2⋯pkekn = p_1^{e_1} \cdot p_2^{e_2} \cdots p_k^{e_k}

则正约数个数为：

τ(n)=(e1+1)(e2+1)⋯(ek+1)\tau(n) = (e_1 + 1)(e_2 + 1)\cdots(e_k + 1)

第一段循环已经求出了所有质因子及其指数 eie_i，只需在分解时累乘 divisors *= (count + 1) 即可。但原代码在后面硬生生又拿 nn 重新跑了一次一模一样的试除分解；更糟的是条件写成了 i * i <= n 而非 i * i <= r2，哪怕数字早就除成 1，循环也会死死空转到 n\sqrt{n}。

缺陷三：大数下的主线程假死（UI DoS）

当用户输入一个接近 2532^{53} 的质数（如 9007199254740881）：

  • n≈94,906,265\sqrt{n} \approx 94,906,265（近 1 亿次迭代）；
  • 加上第二段重复循环，总计近 2 亿次迭代与模运算；
  • 在低功耗 CPU（如本站所在的 Intel J1900 机器）上，耗时超过 3.4 秒，页面彻底卡死，滚动条和按钮全部失去响应。

2. 质数判定不需要质数表：确定性 Miller–Rabin 测试

要打破试除法的瓶颈，首要解决的是大质数拦截：如果一个数本身就是质数，我们能不能不去找因数，直接在 0.1 毫秒内断定它是质数并立即返回？

很多人直觉上认为：要判定一个数是不是质数，难道不也得拿一张质数表挨个试除吗？

不需要。现代计算数论的核心突破是：证明一个数“是合数”，根本不需要知道它的因子是谁。

费马小定理与二次探测

  1. 费马小定理：若 pp 为质数且 gcd⁡(a,p)=1\gcd(a, p) = 1，则必有 ap−1≡1(modp)a^{p-1} \equiv 1 \pmod p。 若随机选取底数 aa 发现 an−1a^{n-1} ≢ 1(modn)1 \pmod n，则 nn 必定是合数。
  2. 二次探测定理：若 pp 为质数，方程 x2≡1(modp)x^2 \equiv 1 \pmod p 在模质数下只有两个平凡解：x≡1x \equiv 1 或 x≡p−1x \equiv p - 1。如果在平方得到 1 的前一步，值既不是 1 也不是 n−1n-1，则发现了非平凡平方根，nn 必定是合数。

64 位整数的 7 个固定基数

在密码学中测试几百位大数时通常随机取 40 个底数，属于概率测试；但在我们工具声明的 2≤n≤264−12 \le n \le 2^{64}-1 范围内，数论学者 Jim Sinclair 证明了确定性基数集合： 对于任意 <264< 2^{64} 的整数，只需固定测试以下 7 个底数：

const MR_BASES = [2n, 325n, 9375n, 28178n, 450775n, 9780504n, 1795265022n];

只要通过这 7 个基数的二次探测检验，在数学上 100% 是质数，绝无任何反例与强伪素数。

通过快速幂模运算，判定任意一个 20 位以内的超级大质数仅需几十次模平方，耗时从 3.4 秒直接降到 0.2 ~ 0.5 毫秒（提速数千倍）。

3. 大合数分解的降维打击：Pollard’s rho 与生日悖论

排除大质数后，剩下的难题是：如果数字是由两个很大的质数相乘构成的大合数（半素数，Semiprime），如何快速拆出它的因子？

试除法的复杂度是 O(n)O(\sqrt{n})。对于 64 位数，n≈4×109\sqrt{n} \approx 4 \times 10^9（40 亿次循环，依然无法接受）。此时必须使用 Pollard’s rho 算法。

生日悖论与 O(n¹/⁴) 复杂度

设 nn 的未知较小质因数为 pp。我们用伪随机多项式 f(x)=(x2+c)(modn)f(x) = (x^2 + c) \pmod n 生成伪随机序列 x0,x1,x2,…x_0, x_1, x_2, \dots。

根据生日悖论：在一个模 pp 的空间里，随机抽取大约 p\sqrt{p} 个数就会以极高概率出现两个模 pp 相同的数（即发生碰撞）：

xi≡xj(modp)  ⟺  p∣∣xi−xj∣x_i \equiv x_j \pmod p \iff p \mid |x_i - x_j|

此时只要计算 gcd⁡(∣xi−xj∣,n)\gcd(|x_i - x_j|, n)，就能以极大概率直接提取出非平凡因子 pp！ 因为 p≤np \le \sqrt{n}，所以寻找因子的期望步数仅为：

O(p)≤O(n1/4)O(\sqrt{p}) \le O(n^{1/4})

对于 64 位数，n1/4≤65536n^{1/4} \le 65536 步。从试除法的 40 亿步骤降到几万步内！

优化一：Brent 周期查找替代 Floyd 龟兔

传统实现使用 Floyd 龟兔判环（乌龟走 1 步，兔子走 2 步）。我们升级为 Richard Brent 提出的倍增步长算法： 以 20,21,22,23,…2^0, 2^1, 2^2, 2^3, \dots 的区间长度推进，固定点 xx，让 yy 在区间内前进。相比 Floyd 算法，迭代步数直接减少了约 25% ~ 30%。

优化二：128 步批量 GCD 累模（Batch GCD）

在循环内部，计算大整数公约数 bigGcd 是相对昂贵的运算。我们引入批次大小 M=128M = 128： 在循环内只做极速的模乘累积：

q=(q×∣x−y∣)(modn)q = \big(q \times |x - y|\big) \pmod n

每 128 步或一个区间结束时，才统一调用一次 bigGcd(q, n)。若命中因子（d>1d > 1），再从这 128 步的起点单步回退定位出确切的因数。

这一项优化将整个分解过程中高开销的 GCD 调用频次直接降低了 95% 以上！

4. 人脑十进制直觉 vs 计算机二进制本质

在讨论算法时，一个非常自然的直觉是：

“比如数字 140 是 0 结尾的，根据十进制规则，已知至少含有一个 2 和一个 5，为什么不先除以 10 剩下 14，再看 14 是偶数除以 2 剩下 7？”

这在草稿纸心算上非常省力，但在计算机底层实现中，情况完全不同：

“知道至少有” ≠ “完成了质因数分解”

无论心算怎么跳步，程序最终都必须精确算出：到底有几个 2？到底有几个 5？ 无论是除以 10 还是除以 2，底层都必须有 while (rest % p === 0) 把因子的幂次彻底数出来。

计算机内存里没有“十进制末尾 0”

人脑看的是十进制字符串 '1', '4', '0'，但计算机内部存储的是二进制 BigInt。对计算机而言，检测“末尾是不是十进制 0”需要做一次 n % 10n === 0n 除法。专门写这个特判非但省不了计算，反而让剩下 90% 不以 0 结尾的数凭空多了一次求模分支。

更关键的是：按质数从小到大（2, 3, 5, 7…）采用贪心策略一次性除尽，一旦因数 2 剥离完毕，后续数字绝对不可能再出现偶数，因数天然单调递增排列，状态永远单向收敛。

计算机真正能“一眼看穿”的是因数 2（位运算剥离）

计算机虽然看不出十进制的 0，但对二进制的 0 有硬件级支持。任何偶数在二进制下末位必定是 0，我们使用按位与和右移替代大数除法：

// 针对质因子 2 的极致位运算剥离
if ((rest & 1n) === 0n) {
	let c = 0;
	do {
		rest >>= 1n;
		c++;
	} while ((rest & 1n) === 0n);
	byFactor.set('2', c);
}

位移 >>= 1n 是底层的单周期指令，比大整数除法器快得多。对于 2622^{62} 这种纯偶数或 101810^{18} 这种超大数，所有的因数 2 仅需 20 ~ 30 微秒 就能瞬间全部落袋。

5. 四级流水线与真实空载性能实测

最终落地的质因数分解架构包含四级精密流水线：

  1. 第一级：首屏素性拦截：if (isPrime(n)) 确定性 7 基数 Miller–Rabin 判定，大质数 0 步试除，亚毫秒直接返回；
  2. 第二级：位运算剥离质因数 2：& 1n 与 >>= 1n 毫秒内清空偶数因子；
  3. 第三级：1000 以内静态素数表试除：168 个预置原生 bigint[]，动态 rest\sqrt{rest} 截断，绝大多数小合数在测到前几个质数时就已彻底分解并提前 break；
  4. 第四级：Pollard–Brent + 128 步批量 GCD：递归分治处理大合数，步数从 O(n)O(\sqrt{n}) 压至 O(n1/4)O(n^{1/4})。

在十年前的低功耗 Intel J1900 机器、系统空载环境下，实测 9 组典型特征数字的耗时账如下：

实例特征 / 测试数值 nn 质因数分解结果 约数个数 最快耗时 中位数耗时
小合数 (含 2 和 5)
140		 22×5×72^2 \times 5 \times 7 12 0.032 ms (32 μs) 0.045 ms
纯大偶数 (位移剥离)
262=46116860184273879042^{62} = 4611686018427387904		 2622^{62} 63 0.021 ms (21 μs) 0.033 ms
多零超大数 (101810^{18})
10000000000000000001000000000000000000		 218×5182^{18} \times 5^{18} 361 0.019 ms (19 μs) 0.033 ms
100 万质数 (首屏拦截)
999983		 999983 2 0.042 ms (42 μs) 0.047 ms
2532^{53} 临界大质数 (旧算法卡死点)
9007199254740881		 9007199254740881 2 0.216 ms 0.269 ms
2642^{64} 极限 20 位质数
18446744073709551557		 18446744073709551557 2 0.262 ms 0.343 ms
高度合成数 (1260个约数)
908107200		 26×34×52×72×11×132^6 \times 3^4 \times 5^2 \times 7^2 \times 11 \times 13 1260 0.030 ms (30 μs) 0.031 ms
两 10 位质数乘积 (Pollard-Brent)
109+7×109+910^9+7 \times 10^9+9		 1000000007×10000000091000000007 \times 1000000009 4 37.4 ms 45.2 ms
近 2642^{64} 最坏半素数平方
42949672912=184467440307598786814294967291^2 = 18446744030759878681		 429496729124294967291^2 3 74.1 ms 99.9 ms

从最初面对大数卡死 3 秒以上、浏览器濒临崩溃，到如今全范围 2…264−12 \dots 2^{64}-1 保证 100% 确定性正确且在数十微秒至百毫秒内完成响应，这笔算力账终于彻底理清。