Berlekamp 多项式因式分解算法

Berlekamp 算法没有逐个试除不可约多项式，而是寻找在 Frobenius 下不动的“标签函数”。在每个不可约因子对应的扩域分量中，满足 $z^q=z$ 的元素恰是基域 ${\mathbb{F}}_q$；所以一个不动元素相当于给每个未知因子贴上一个域元素标签。计算 $gcd(f,h-a)$ 就把标签为 $a$ 的分量一次取出。

关键工作由有限维线性代数完成。模 $f$ 把任意幂压回 $n$ 维空间，Frobenius 的不动条件变成齐次线性方程；零空间维数不仅指导分裂，还直接告诉算法共有多少个互异不可约因子。这种结构尤其适合 $q$ 固定而 $n$ 增长的场景，因为所有域元素都可枚举，确定性地尝试 $a$ 不会改变关于 $n$ 的多项式性。

在 ${\mathbb{F}}_2[x]$ 中取

$f^{\prime }=x^2$，与 $f$ 互素，所以输入平方自由。以 $(1,x,x^2)$ 为基，平方映射给出

因此

$\ker (Q-I)$ 由 $1$ 与 $h=x+x^2$ 张成，维数 $2$ 预告两个因子。实际计算

商即 $x^2+x+1$。每个输出都通过精确除法验证，零空间本身没有“猜中因子”的概率。

复杂度声明必须保留 $q$。经典确定性版本需枚举 $a\in {\mathbb{F}}_q$ 并做稠密 $n\times n$ 线性代数；在固定 $q$ 时它关于 $n$ 为多项式时间，朴素界常写成 $O(n^3+q{n}^2)$ 量级的域运算，但 $q$ 若以 $\log q$ bit 输入，这个枚举对输入长度是指数依赖。不能把“有限域上的多项式时间”省略成对 $n,\log q$ 都多项式。

构造 $Q$ 也有成本：必须计算 $x^q,x^{2q},\dots$ 模 $f$，扩域表示、模乘与内存布局都会影响常数。大 $n$ 时矩阵可稀疏开始却在消元中变稠密；非首一输入需先除首项，首项为零或底环不是域时则没有这一操作。零空间维数为 $1$ 只在输入已平方自由的前提下才证明 $f$ 不可约。

Berlekamp 不动子空间给出了一个很强的可检验证书：零空间基、各次 GCD 与最终乘积足以复核分解。算法还展示 Frobenius、Chinese remainder 与线性代数如何协作，把非线性的“找因子”问题转成求核再分组。编码理论和有限域构造中的小特征多项式因此常直接采用此路线。

Cantor–Zassenhaus 算法公理库Cantor–Zassenhaus 因式分解算法Cantor–Zassenhaus algorithm · Cantor-Zassenhaus factorization先按不可约因子次数分组，再以随机幂、迹映射和 GCD 做 Las Vegas 等次数分裂。通常先按不可约因子次数分组，再用随机幂与 GCD 做等次数分裂；它是 Las Vegas 算法，避免经典 Berlekamp 对全部 $q$ 个常数的确定性扫描，在大域上更合适。两者不是“一个永远更快”：小固定域、需要完全确定性或已有高效线性代数时，Berlekamp 仍然自然；大 $q$ 和高次数时，随机分裂及其现代变体往往占优。比较时应同时报告域大小编码、矩阵算法与随机性口径。