Cantor–Zassenhaus 因式分解算法

形式陈述

输入为有限域 $\mathbb F_q$ 上首一、平方自由多项式 $f$ ，次数 $n\ge1$ ；常数 $1$ 返回空列表，零多项式排除。先做按不可约因子次数分组的 distinct-degree factorization：

text

G = f; v = x mod G; d = 1
while G != 1 and 2*d <= degree(G):
    v = v^q mod G
    H = gcd(G, v-x)
    if H != 1: output block (H, d); G = G/H
    if G != 1: v = v mod G
    d = d+1
if G != 1: output block (G, degree(G))

循环开始时， $G$ 只含次数至少 $d$ 的因子；本轮 $v\equiv x^{q^d}\pmod G$ 。次数为 $e$ 的首一不可约因子整除 $x^{q^d}-x$ 当且仅当 $e\mid d$ ，所以在较小次数已经移除后， $H$ 恰好收集次数为 $d$ 的因子。若结束时 $G\ne1$ ，其所有因子次数至少 $d$ 、总次数却小于 $2d$ ，故只剩一个不可约因子。这同时给出分组正确性与有限终止条件。

对一个由 $r\ge2$ 个次数均为 $d$ 的不可约因子组成的块 $F$ ，通过逐系数独立、精确均匀抽样，选取次数小于 $\deg F$ 的 $a$ ；每次重抽使用新的独立随机数。若 $q$ 为奇数，先算 $\gcd(F,a)$ ：若它已经是真因子就直接切分，若为 $F$ 就重抽；只有在 $a$ 模每个不可约因子都非零时，才计算

h=a^{(q^d-1)/2}\bmod F.

在每个因子商域 $\mathbb F_{q^d}$ 中，非零 $a$ 的该幂为 $1$ 或 $-1$ 。因此 $\gcd(F,h-1)$ 与 $\gcd(F,h+1)$ 按二次剩余标签分组；若得到 $1$ 或 $F$ 就重抽，得到真因子则递归。若 $q=2^s$ ，则 $1=-1$ ，改用绝对迹 $h=\sum_{j=0}^{sd-1}a^{2^j}\bmod F$ ，以 $\gcd(F,h)$ 分裂；它为 $1$ 或 $F$ 时重抽。两个分支都在块次数等于 $d$ 时停止并输出该块，此时它已不可约。

每次候选因子都用 GCD 和精确除法验证，失败只导致重试，所以这是Las Vegas 随机算法：输出永远正确，运行时间随机且期望为多项式。开始前的平方自由分解保证各分量互异；底层有限域保证 Frobenius 周期、二次剩余或迹映射的计数成立。

直觉

distinct-degree 阶段像先按“扩域尺寸”整理未知因子。所有次数为 $d$ 的不可约因子都在 $\mathbb F_{q^d}$ 中完全分裂，而较大次数因子不会被 $x^{q^d}-x$ 捕获。得到等次数块后，每个未知因子对应商环直积中的一个同型域分量，中国剩余定理给出的双射，把均匀的 $a$ 精确变成各域分量上相互独立的均匀元素。

奇特征的指数 $(q^d-1)/2$ 把每个非零分量压成二值标签 $\pm1$ 。只要不同因子没有全落到同一标签，GCD 就一次抽出一个非空真子集；令 $Q=q^d$ 。每个分量的三个标签 $0,+1,-1$ 的概率分别是 $1/Q,(Q-1)/(2Q),(Q-1)/(2Q)$ ；一次失败恰好是所有标签相同，所以概率为 $Q^{-r}+2((Q-1)/(2Q))^r\le1/2$ 。偶特征的绝对迹是到 $\mathbb F_2$ 的非零线性映射：迹的平方等于自身，而定义它的非零多项式次数为 $2^{sd-1}<2^{sd}$ ，不可能在整个分量域上恒为零。因此其两个纤维等大，均匀输入给出公平比特；失败概率为 $2^{1-r}\le1/2$ 。故每次真分裂平均至多两次尝试，最终真分裂次数为 $r-1$ 。随机性只负责寻找好切分，不负责相信一个未经验证的答案。

Cantor–Zassenhaus 算法：奇特征下通过非零分量的二次剩余标签切分等次数块 — 随机等次数分裂

图中展示奇特征且已确认 $\gcd(F,a)=1$ 后的幂运算分支；图里的 $h$ 记为 $a^{(q^d-1)/2}-1$ 。完整的一次尝试先检查 $\gcd(F,a)$ ，它也可能直接给出真因子；上面的无条件失败概率同时计入零标签与两个非零标签。

例子与边界

在 $\mathbb F_5[x]$ 中取等次数块

F=x^2+1=(x-2)(x-3),

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

h=a^{(5^1-1)/2}=(x+1)^2 \equiv 2x\pmod{x^2+1}.

计算

\gcd(F,h-1)=\gcd(x^2+1,2x-1)=x-3,

得到真因子，另一个商为 $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(q^d)$ 次平方乘计量，若 $q$ 本身很大，应按 $\log q$ 而非把一个域元素操作当无条件常数。小输入上随机数生成和多次 GCD 可能超过确定性方法；输出顺序也不是确定的，但将因子首一化并排序可获得规范结果。

推论与应用

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

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

采用普通平方成本的多项式乘法、除余与 GCD 时，这份直接 DDF＋EDF 实现可取保守的期望 $O(n^3\log q)$ 次域运算上界，不含平方自由预处理和精确均匀抽样的成本。DDF 至多 $n$ 轮；EDF 中度为 $m$ 、不可约因子次数为 $d$ 的节点，每次尝试需 $O(m^2d\log q)$ 次域运算，真分裂平均至多两次尝试，对递归树求和得到上述界。按深度优先顺序拆分并复用工作数组，可用 $O(n)$ 个系数槽位；指数、调用控制信息及域元素的 bit 表示另计。这个直接实现界不声称达到优化算法的复杂度。

参考资料

David G. Cantor and Hans Zassenhaus, “A New Algorithm for Factoring Polynomials over Finite Fields,” Mathematics of Computation 36(154), 1981, pp. 587–592.
Joachim von zur Gathen and Daniel Panario, “Factoring Polynomials over Finite Fields: A Survey,” Journal of Symbolic Computation 31(1–2), 2001, pp. 3–17.
Joachim von zur Gathen and Jürgen Gerhard, Modern Computer Algebra, 3rd ed., Cambridge University Press, 2013, chapter on factoring polynomials over finite fields.
Markus Bläser、Chandan Saha, Computational Number Theory and Algebra, Lecture 8，2012-05-14，§1：CRT 下的独立均匀分量、奇特征等次数分裂。本页另外保留零抽样和偶特征绝对迹的分支。

形式陈述 ​

反向链接

形式陈述