Cantor–Zassenhaus 因式分解算法

distinct-degree 阶段像先按“扩域尺寸”整理未知因子。所有次数为 $d$ 的不可约因子都在 ${\mathbb{F}}_{q^d}$ 中完全分裂，而较大次数因子不会被 $x^{q^d}-x$ 捕获。得到等次数块后，每个未知因子对应商环直积中的一个同型域分量，随机选取的 $a$ 在这些分量里近似独立。

奇特征的指数 $(q^d-1)/2$ 把每个非零分量压成二值标签 $\pm 1$。只要不同因子没有全落到同一标签，GCD 就一次抽出一个非空真子集；$r\ge 2$ 时一次成功概率有常数下界，重复次数的期望受控。偶特征用迹把分量压到 ${\mathbb{F}}_2$，扮演同样的随机二分器。随机性只负责寻找好切分，不负责相信一个未经验证的答案。

在 ${\mathbb{F}}_5[x]$ 中取等次数块

这里 $d=1,r=2$。选 $a=x+1$，则

计算

得到真因子，另一个商为 $x-2$。若选 $a=x$，则 $h=x^2\equiv -1$ 在两个分量上相同，$gcd(F,h-1)=1$、$gcd(F,h+1)=F$，本轮没有信息；算法重抽即可，不能把这次失败误报为 $F$ 不可约。

等次数前提不能省略。若一个块同时含一次与二次不可约因子，统一使用 $(q^d-1)/2$ 不再在所有分量上产生预期二值标签，成功概率论证也失去对象。奇特征公式更不能照搬到 $q$ 为偶数，因为 $+1=-1$；显式迹算法的指数项数与 $q=2^s$、扩张次数 $d$ 有关，实际实现常用重复平方而不是构造天文大的指数。

“期望多项式”还依赖随机元素近似均匀和域运算成本。每轮模幂按 $\log \left(q^d\right)$ 次平方乘计量，若 $q$ 本身很大，应按 $\log q$ 而非把一个域元素操作当无条件常数。小输入上随机数生成和多次 GCD 可能超过确定性方法；输出顺序也不是确定的，但将因子首一化并排序可获得规范结果。

标准有限域因式分解流水线由平方自由分解、distinct-degree factorization 与 equal-degree factorization 三段组成。分段使每个定理只承担一个条件：第一段处理重数，第二段确定次数类别，Cantor–Zassenhaus 的第三段只负责在同次数块内切分。由此既能单独替换更快的 Frobenius 计算，也能为每阶段留下乘积与整除证书。

与Berlekamp 算法公理库Berlekamp 多项式因式分解算法Berlekamp factorization algorithm · Berlekamp polynomial factorization计算有限域商代数的 Frobenius 不动子空间，并以 GCD 从中确定性分离不可约因子。相比，本算法不先求整个 $n\times n$ Frobenius 不动空间，也不确定性枚举所有 $q$ 个常数；其大域依赖通常更好，代价是随机运行时间。现代系统会按 $q$、次数、稀疏度与可用线性代数选择混合方案。无论选择哪条路线，不能把 Las Vegas 说成“有小概率给错答案”：可以失败重试的是切分尝试，最终交付的每个因子都经过精确验证。