有限域上多项式因子分解

隐藏目录

不同次数因子分解

有限域 $F_p$ 和 $F_{p^d}$
不同次因子分解算法

同次因子分解

特征为奇素数的有限域
特征为2的有限域

一个完整的因子分解算法

无平方因子分解

特征为零的域上无平方分解
特征有限的域上无平方分解

Berlekamp 算法

Frobenius映射和Berlekamp子代数
Berlekamp算法的实现

素性检测和不可约多项式的构造

多项式因子分解问题比最大公因子问题要复杂，因而也更困难一些。然而令人惊喜的是在有限域上，多项式的因子分解问题却变得十分简单，这给我们提供了一种将整数环或有理数域上的多项式因子分解问题转化到较简单的有限域情况上来解决的可能性。

这一部分我们首先解决 $\mathbb{F}_p$ 域上的多项式因子分解问题。这些内容是 $\mathbb{Z}[x]$ , $\mathbb{Q}[x]$ , $\mathbb{Z}_m[x]$ 乃至 $\mathbb{R}[x]$ , $\mathbb{C}[x]$ 和多元多项式因子分解的基础.

在有限域上进行因子分解的方法很多，一般来说,有限域上多项式因子分解要经过下面三个步骤：

无平方因子分解(squarefree factorization)
不同次数因子分解(distinct-degree factorization)
同次因子分解(equal-degree factorization)

这一章首先将从上面三个方面介绍有限域上的因子分解问题，然后讨论其他算法([1]Chapter 14).

不同次数因子分解

这里我们假定多项式是无平方因子的(squarefree)，即无重因子。这一点很容易做到，比如 $f$ 含重因子，那么取 $f/\gcd(f,f')$ ，则可消去重因子，得到无重因子的多项式。不同次因子分解(Distinct-degree factorization)即是在无平方因子分解的基础上，将多项式中各不同次数因子的乘积逐一剥离出来。

首先我们介绍一些有限域的知识.

有限域 $F_p$ 和 $F_{p^d}$

定理1(Fermat小定理) 对于非零元 $a\in\mathbb{F}_p$ ,我们有 $a^{p-1}=1$ 且 $\forall a\in\mathbb{F}_p$ ，有 $a^p=a$ 且 $x^p-x=\prod_{a\in\mathbb{F}_p}(x-a).$

有限域的阶数只可能是素数以及素数的幂，对于 $d\ge 1\in\mathbb{N}$ ,可以构造 $p^d$ 阶的域如下： $\mathbb{F}_{p^d}=\mathbb{F}_p[x]/\langle f\rangle,$ 其中 $f\in\mathbb{F}_p[x]$ 是 $d$ 次不可约多项式。

Fermat小定理 $p$ 对于素数以及素数的幂均成立，素数的幂情况证明同素数情况。

下面的定理是Fermat小定理的推广，Fermat小定理是其 $d=1$ 的特殊情形。

定理2(Fermat小定理推广) 对于任何 $d\ge 1$ , $x^{p^d}-x\in\mathbb{F}_p[x]$ 是 $\mathbb{F}_p[x]$ 中所有次数整除 $d$ 的不可约首一多项式的乘积。其中 $p$ 是素数或素数幂.

证明由Fermat小定理知 $h=x^{p^d}-x$ 是所有的一次因子 $x-a$ 的乘积，其中 $a$ 取遍 $\mathbb{F}_{p^d}$ 中的元素。因此， $h$ 是无平方因子的，于是我们只须证明对任何 $\mathbb{F}_p[x]$ 中首一不可约 $n$ 次多项式 $f$ : $f|x^{p^d}-x\Leftrightarrow n|d.$

若 $f|x^{p^d}-x$ ,则由Fermat小定理，可以取 $\mathbb{F}_{p^d}$ 的子集 $A$ 使得 $f=\prod_{a\in A}(x-a)$ .任取 $a\in A$ ,令 $\mathbb{F}_p[x]/\langle f\rangle\cong\mathbb{F}_p(a)\subset\mathbb{F}_{p^d}$ ,其中 $\mathbb{F}_p(a)$ 是 $\mathbb{F}_{p^d}$ 中包含 $a$ 的最小子域，有 $p^n$ 个元素， $\mathbb{F}_{p^d}$ 是它的扩域，因此 $p^d=(p^n)^e\Rightarrow n|d$ .

若 $n|d$ ,令 $\mathbb{F}_{p^d}=\mathbb{F}_p[x]/\langle f\rangle$ ,且 $a=(x \bmod f)\in\mathbb{F}_{p^n}$ 为 $f$ 的一个根。而 $a^{p^n}=a$ ,由于 $p^n-1|p^d-1$ ，设 $p^d-1=(p^n-1)e=(p^n-1)(p^{d-n}+p^{d-2n}+\cdots+1),$ 则 $x^{p^d-1}-1=(x^{p^n-1}-1)(x^{(p^n-1)(e-1)}+\cdots+1).$ 将上式乘以 $x$ 则可得 $(x-a)|(x^{p^n}-x)|(x^{p^d}-x)$ .因此在 $\mathbb{F}_{p^n}[x]$ 中 $(x-a)|\gcd(f,x^{p^d}-x)$ ,由于 $\mathbb{F}_p[x]$ 中多项式的最大公因子应该也在 $\mathbb{F}_p[x]$ 中，于是由其非平凡可推出 $\gcd(f,x^{p^d}-x)=f$ ,即 $f|x^{p^d}-x$ . □

不同次因子分解算法

不同次因子分解算法即是要求出多项式的不同次因子序列,其定义如下:

定义1(不同次因子序列) $\mathbb{F}_p[x]$ 中非平凡多项式 $f$ 的不同次因子分解是指得到如下的不同次因子序列 $(g_1,\ldots,g_s)$ ,其中 $g_i$ 是 $f$ 在 $\mathbb{F}_p[x]$ 中所有首一不可约 $i$ 次多项式的乘积,且 $g_s\neq 1$ .

算法1(不同次因子分解)

输入：无平方因子 $n(>0)$ 次首一多项式 $f\in\mathbb{F}_p[x]$ ,

输出： $f$ 的不同次因子序列 $(g_1,\ldots,g_s)$ .

$h_0=x$ , $f_0=f$ , $i=0$ ,
$i=i+1$ ,在环 $R=\mathbb{F}_p[x]/\langle f\rangle$ 中调用快速求幂算法计算 $h_i=h_{i-1}^p \bmod f$ ,
$g_i=\gcd(h_i-x,f_{i-1})$ , $f_i=\displaystyle\frac{f_{i-1}}{g_i}$ ,
若 $f_i\neq 1$ 则转到2步,
$s=i$ ,输出 $(g_1,\ldots,g_s)$ .

证明(算法有效性) 不妨设 $(G_1,\ldots,G_t)$ 是 $f$ 的不同次因子序列，则考虑命题 $P_i:h_i\equiv x^{p^i}\pmod{f},\quad f_i=G_{i+1}\cdots G_t,\quad g_i=G_i(\text{若}i>0).$

显然 $P_0$ 成立，设 $P_0,\ldots,P_{i-1}$ 均成立，则对 $i\ge 1$ ,有 $h_i\equiv h_{i-1}^p\equiv x^{p^i}\pmod{f}$ 且 $g_i=\gcd(h_i-x,f_{i-1})=\gcd(x^{p^i}-x,f_{i-1}).$

由Fermat小定理推广， $g_i$ 是 $\mathbb{F}_p[x]$ 中所有首一不可约且次数整除 $i$ 的多项式的乘积且能整除 $f_{i-1}=G_i\cdots G_t$ ,因此 $g_i=G_i$ (低于 $i$ 次的因子已在前面提出了).于是归纳证明了 $P_i(0\le i\le s)$ 成立，也同时可得 $s=t$ . □

算法1可在 $\deg f_i<2(i+1)$ 时即终止，因为 $f_i$ 所有不可约因子次数至少为 $i+1$ ,因此 $f_i$ 即已经是不可约的了。

例1 考虑多项式 $f=x^5+x^3+x^2+x-1\in\mathbb{F}_3[x]$ . ◇

解我们将单步执行算法1的步骤列于下： $f_0=f=x^5+x^3+x^2+x-1,h_0=x,$ $h_1=h_0^3\bmod f=x^3\bmod f=x^3,$ $g_1=\gcd(h_1-x,f_0)=x^2-1,f_1=\frac{f_0}{g_1}=x^3-x+1,$ $h_2=h_1^3\bmod f=x^9\bmod f=-x^3-x,$ $g_2=\gcd(h_2-x,f_1)=1,f_2=x^3-x+1.$ 此时已可以结束，得到不同次因子序列为 $(x^2-1,1,x^3-x+1)$ .

同次因子分解

本节基于上一节不同次因子分解的结果继续对其进行同次因子分解(Equal-degree factorization)，或者Cantor-Zassenhaus算法，直到将 $f$ 完全分解为不可约多项式的积。但是由于奇素数与2在下面的处理技术中有一点微小的区别，因此本节分成两部分来讨论.

特征为奇素数的有限域

引理1 设 $q$ 为一素数幂, $k$ 为 $q-1$ 的因子， $S=\{b^k|b\in\mathbb{F}_q^*\}$ 为 $\mathbb{F}_q^*$ 中的 $k$ 次幂集合。则：

$S$ 为 $(q-1)/k$ 阶子群。
$S=\{a\in\mathbb{F}_q^*|a^{(q-1)/k}=1\}$ .

证明 $S$ 为 $k$ 次幂同态(homomorphism)映射 $\sigma_k:\mathbb{F}_q^*\rightarrow\mathbb{F}_q^*$ 的象，易证其为 $\mathbb{F}_q^*$ 的子群。 $\sigma_k$ 的核为 $k$ 次单位根： $\ker\sigma_k=\{a\in\mathbb{F}_q^*|\sigma_k(a)=1\}.$ 由于 $\mathbb{F}_q$ 为域，则多项式 $x^k-1\in\mathbb{F}_q[x]$ 的根至多有 $k$ 个，于是 $\#\ker\sigma_k\le k$ .

$(b^k)^{(q-1)/k}=b^{q-1}=1$ 对于任何 $b\in\mathbb{F}_q^*$ 均成立，由Fermat小定理得 $S\subset\ker\sigma_{(q-1)/k}$ ,则 $\# S\le (q-1)/k$ .于是由群同态定理 $q-1=\# \mathbb{F}_q^*=\#\ker\sigma_k\cdot \#\mathrm{im}\sigma_k=\#\ker\sigma_k\cdot \# S\le k(q-1)/k=q-1,$ 则 $\#\ker\sigma_k=k$ 且 $\# S=(q-1)/k$ , $S=\ker\sigma_{(q-1)/k}$ . □

作为上面引理的推论，我们有

引理2 $q$ 为一奇素数幂, $S=\{a\in\mathbb{F}_q^*|\exists b\in\mathbb{F}_q^*(a=b^2)\}$ ,则

$S\subset\mathbb{F}_q^*$ 是 $(q-1)/2$ 阶子群。
$S=\{a\in\mathbb{F}_q^*|a^{(q-1)/2}=1\}$ .
$\forall a\in\mathbb{F}_q^*,a^{(q-1)/2}\in\{1,-1\}$ .

下面的概率性算法给出 $f$ 的可能因子，其中 $f$ 是经上节算法给出的无平方首一同次因子乘积，即存在 $n=\deg f$ 的一个因子 $d$ 使得 $f$ 可分解为 $n/d$ 个 $d$ 次首一不可约因子.

算法2(同次因子分解概率算法)

输入： $f$ , $d$ ,

输出： $f$ 的首一因子 $g$ ,或者failure.

(随机)任取 $a\in\mathbb{F}_q[x]$ 使得 $\deg a<n$ .若 $a\in\mathbb{F}_q$ 则输出failure,
$g_1=\gcd(a,f)$ ,若 $g_1\neq 1$ 且 $g_1\neq f$ 则输出 $g_1$ ,
调用快速求幂算法在环 $R=\mathbb{F}_q[x]/\langle f\rangle$ 中计算 $b=a^{(q^d-1)/2} \bmod f$ ,
$g_2=\gcd(b-1,f)$ ,若 $g_2\neq 1$ 且 $g_2\neq f$ 则输出 $g_2$ ,否则输出failure.

若设 $f=f_1f_2\cdots f_r$ ,则由中国剩余定理有如下的环同构： $\chi:R=\mathbb{F}_q[x]/\langle f\rangle\rightarrow\mathbb{F}_q[x]/\langle f_1\rangle\times\cdots\times\mathbb{F}_q[x]/\langle f_r\rangle=R_1\times\cdots\times R_r,$ 其中 $\mathbb{F}_{q^d}\cong R_i=\mathbb{F}_q[x]/\langle f_i\rangle\supset\mathbb{F}_q$ . 引入下面记号： $\chi(a\bmod f)=(a\bmod f_1,\ldots,a\bmod f_r)=(\chi_1(a),\ldots,\chi_r(a))$ ,其中 $\chi_i(a)=a\bmod f_i$ .记 $e=(q^d-1)/2$ ,则对任意 $\beta\in R_i^*=\mathbb{F}_{q^d}^*$ ,我们有 $\beta^e\in\{-1,1\}$ ,且取两个值是等概率的.如果我们随机任意选取 $a\in\mathbb{F}_q[x]$ 使得 $\deg a<n$ 且 $\gcd(a,f)=1$ ，则 $\chi_1(a),\ldots,\chi_r(a)$ 是 $\mathbb{F}_{q^d}^*$ 中随机元素，且 $\varepsilon_i=\chi_i(a^e)\in R_i$ 等概率取 $1$ 或 $-1$ ,因此 $\chi(a^e-1)=(\varepsilon_1-1,\ldots,\varepsilon_r-1),$ 此时 $a^e-1$ 是 $f$ 的一个因子(不一定不可约),除非 $\varepsilon_1=\cdots=\varepsilon_r$ (若有 $\varepsilon_i=1$ 则 $\chi_i(a^e-1)=0$ ,则 $f_i|\gcd(a^e-1,f)$ .)，而后一种情况发生的概率为 $2\cdot(1/2)^r=2^{-r+1}\le 1/2$ .( $r\ge 2$ )

算法3(同次因子分解)

输入：同算法2,

输出： $f$ 在 $\mathbb{F}_q[x]$ 中的首一不可约因子.

若 $n=d$ 则输出 $f$ ,
调用算法2，输入 $f$ 和 $d$ ，直至复返回 $f$ 的一个因子 $g$ ,
递归调用算法2,输入 $g$ 和 $f/g$ ,输出所有的结果.

例2 我们讨论 $f=x^4+x^3+x-1$ , $d=2$ (这里我们之所以知道 $d=2$ ，是因为这样的问题很可能是上节因子算法已分解出的 $g_2$ ). ◇

解随机取 $a=x$ ,则 $g_1=\gcd(a,f)=1$ , $b=a^{(3^2-1)/2}\bmod f=a^4\bmod f=-x^3-x+1,$ $g_2=\gcd(b-1,f)=x^2+1,$ 因而找到了一个因子 $x^2+1$ ,另一个因子为 $f/(x^2+1)=x^2+x+2$ .

特征为2的有限域

以下设 $\field{q}$ 是一特征为2的域，且 $q=2^k$ , $k$ 是一正整数. $\field{q}$ 上多项式 $f$ 是无平方因子 $n$ 次多项式,且是 $r$ 个 $d$ 次不可约多项式之积.

定义2 对于正整数 $m$ ，定义 $\field{2}$ 上 $m$ 阶迹多项式( $m$ th trace polynomial) $T_m$ 为 $T_m=x^{2^{m-1}}+x^{2^{m-2}}+\cdots+x^4+x^2+x.$

注1 $x^{2m}+x=T_m(T_m+1)$ .此式可直接验证.

注2 $\forall\alpha\in\field{2^m}$ , $T_m(\alpha)=0\vee 1$ ,且各有一半概率.此事是因为 $\alpha$ 一定是 $x^{2m}+x$ 的根，因而 $T_m(\alpha)=0\vee T_m(\alpha)+1=0$ ,且二者次数均为 $2^{m-1}$ ，因此各有 $2^{m-1}$ 个根.

引理3 设 $a$ 是 $R=\field{q}[x]/\idea{f}$ 上随机选取的一个多项式, $b=T_{kd}(a)$ ,则 $\gcd(b-1,f)$ 可能给出 $f$ 的一个非平凡因子,且否定概率不超过1/2.

证明首先, $\chi_i(b)=\chi_i(T_{kd}(a))=T_{kd}(\chi_i(a))=0\vee 1$ ,而由中国剩余定理所得到的环同构可知,当且仅当 $\chi_i(b)(1\le i\le r)$ 同时为0或1时, $b\in\field{2}$ ,此概率为 $2\times 2^{-r}=2^{1-r}\le\frac{1}{2}$ .而当 $b\not\in\field{2}$ 时，必有 $i$ 使 $\chi_i(b)=1$ ,此时 $\gcd(b-1,f)$ 至少将 $f$ 的一个非平凡因子分开. □

算法4(特征为2的域上同次因子分解) 算法基本同奇素数幂情况,只需将算法2中第3步改为计算 $b=T_{kd}(a)$ 即可.

例3 作为例子，我们计算 $f=(x^3+x^2+1)(x^3+x+1)=x^6+x^5+x^4+x^3+x^2+x+1\in\field{2}[x]$ 的同次因子分解,其中 $d=3$ , $k=1$ . ◇

解若取 $a=x$ ,则 $b=T_2(a)=x^4+x^2+x\bmod f=x^4+x^2+x$ ,而 $g=\gcd(b,f)=x^3+x+1,$ 则 $f_1=x^3+x+1$ , $f_2=f/f_1=x^3+x^2+1$ .

一个完整的因子分解算法

对于有重因子的多项式 $f\in\mathbb{F}_q[x]$ ，利用上两节的方法可以完全将其分解。如果设 $f$ 是首一的，并且 $f$ 的首一不可约因子分解为 $f=\prod_{i=1}^{m}g_i^{e_i}$ ,记 $U=\{(g_1,e_1),\ldots,(g_m,e_m)\}$ 表示它的分解，则可利用下面的算法给出此分解：

算法5(一个完整的分解算法)

输入：首一多项式 $f\in\mathbb{F}_q[x]$ , $q$ 为一素数幂.

输出： $f$ 的分解 $U$ .

$h_0=x,f_0=f,i=0,u=\emptyset$ ,
$i=i+1$ ,
不同次因子分解：利用快速求幂算法计算 $h_i=h_{i-1}^q\bmod f$ , $g=\gcd(h_i-x,f_{i-1})$ ,
若 $g\neq 1$ 则利用算法3求出 $g$ 的所有同次首一不可约因子 $g_1,g_2,\ldots,g_s$ ,
$f_i=f_{i-1}$ ,并不断除以 $g$ 的同次因子求出 $g_1,\ldots,g_s$ 的次数 $e_1,\ldots,e_s$ ,每求出一个 $e_i$ ,将 $(g_i,e_i)$ 添入 $u$ ,
直至 $f_i=1$ ,否则转第2步,
输出 $U$ .

注3 算法中每次循环的过程中，都会先利用不同次因子分解求出 $f$ 中所包含的 $i$ 次不可约因子，这些不可约因子的(一次）乘积即为 $g$ ,然后依次求出 $f$ 中包含 $g$ 的不可约因子的次数。

作为前面提过的诸多因子分解算法的应用，下面讨论多项式求根问题。设 $f$ 为 $\mathbb{F}_q[x]$ 上一非平凡多项式，则下面的算法给出其所有 $\mathbb{F}_q$ 中的根。

算法6( $\mathbb{F}_q$ 上多项式求根算法) 利用快速求幂算法求出 $h=x^q\bmod f$ ,令 $g=\gcd(h-x,f)$ ,若 $\deg g=0$ 则无根，否则利用同次因子分解算法3其出所有不可约因子 $x-u_1,\ldots,x-u_r$ ,则 $u_1,\ldots,u_r$ 即为其所有 $\mathbb{F}_q$ 上的根。

这样算法就避免了将 $f$ 完全分解，先将其与 $x^q-x$ 取最大公因子，使得结果只能含有形如 $x-u(u\in\mathbb{F}_q)$ 的因子。由此而衍生出下面的 $\mathbb{Z}[x]$ 中求整数根的算法，但在引入该算法之前，先有下面的：

引理4 对于 $\mathbb{Z}[x]$ 上非常数 $n$ 次多项式 $f$ ，设 $\|f\|_{\infty}=A$ ,且 $u\in\mathbb{Z}$ 是 $f$ 的非零根， $f=(x-u)g$ ,则 $\|g\|_{\infty}\le nA$ .

证明设 $g=\sum_{i=0}^{n-1}g_ix^i$ ,则 $f=(x-u)g=g_{n-1}x^n+(g_{n-2}-ug_{n-1})x^{n-1}+\cdots+(g_0-ug_1)x-ug_0$ .式中每项系数绝对值均不超过 $A$ ，于是 $|g_0|\le\frac{A}{|u|},$ $|g_1|\le\frac{A+|g_0|}{|u|}\le\frac{2A}{|u|},(|u|\ge 1)$ $\cdots$ $|g_{n-1}|\le\frac{nA}{|u|}.$

于是 $\|g\|_{\infty}\le nA$ . □

算法7(整数多项式整数根算法)

输入：非常数 $n$ 从多项式 $f\in\mathbb{Z}[x]$ ,且 $\|f\|_{\infty}=A$ .

输出： $\mathbb{Z}$ 中 $f$ 的不同的根.

$B=2n(A+A^2)$ ,任取奇素数 $p\in(B+1,2B]$ .
用算法6找出 $\mathbb{Z}_p[x]$ 上 $f\bmod p$ 的所有根 $\{u_1\bmod p,\ldots,u_r\bmod p\}$ ,其中 $u_i\in\mathbb{Z}$ 且 $|u_i|<p/2(1\le i\le r)$ .
对于每个 $i$ ，计算 $n-1$ 次多项式 $v_i\in\mathbb{Z}[x]$ 且 $\|v_i\|_{\infty}\le p/2$ 使得 $f\equiv (x-u_i)v_i\pmod{p}$ .
输出 $\{u_i|1\le i\le r\wedge |u_i|\le A\wedge\|v_i\|_{\infty}\le nA\}$ .

证明(算法有效性) 不妨设 $f$ 无零根，则对于其任何一个非零根 $u\in\mathbb{Z}$ ,其能整除 $f$ 的常数项，因而 $|u|\le A<p/2$ ,因此所有整数根都可以从其在模 $p$ 的象还原出来。现在我们只需证明 $f(u_i)=0$ 当且仅当 $|u_i|\le A\wedge\|v_i\|_{\infty}\le nA$ .

若 $f(u_i)=0$ ,则显然有 $|u_i|\le A$ .可设 $f/(x-u_i)=g$ ,则由引理4知 $\|f/(x-u_i)\|_{\infty}=\|g\|_{\infty}\le nA<p/2$ .但由于 $f/(x-u_i)\equiv v_i\pmod{p}$ ,且两边多项式系数均比 $p/2$ 小，则有 $f/(x-u_i)=v_i$ ,故也有 $\|v_i\|_{\infty}\le nA$ .

另一方面，若 $|u_i|\le A$ 且 $\|v_i\|_{\infty}\le nA$ ，则 $\|(x-u_i)v_i\|_{\infty}\le(1+A)nA<p/2$ ,因此 $f\equiv(x-u_i)v_i\pmod{p}\Rightarrow f=(x-u_i)v_i.$

证毕。 □

无平方因子分解

这一小节详细介绍无平方因子分解(Squarefree factorization).我们分两个部分进行.

特征为零的域上无平方分解

定义3 多项式 $f=\sum_{i=0}^nf_ix^i\in\mathbb{F}[x]$ ( $\mathbb{F}$ 可以是环、域等)的形式微商定义为： $f'=\sum_{i=0}^nif_ix^{i-1}.$

我们先假定 $\mathbb{F}$ 是一特征为零的域，那么我们已经知道若 $u\in\mathbb{F}$ 是 $f$ 的 $m$ 阶零点，则其是 $f'$ 的 $m-1$ 阶零点，于是 $f/f'$ 中将只含 $(x-u)$ 的一次因子。当然我们可以在 $\mathbb{F}$ 的代数扩域上证明若 $g$ 是 $f$ 的一个不可约因子，那么 $g|f/f'\wedge g^2\not |f/f'$ ,但我们也可以在任一域 $\mathbb{F}$ 内证明如下的命题：

定理3 $\mathbb{F}$ 是任一域，若 $g\in\mathbb{F}[x]$ 是 $f\in\mathbb{F}[x]$ 的一不可约因子，且 $f=g^eh$ , $h\in\mathbb{F}[x]$ , $g,h$ 互素，则 $g^{e-1}|f'$ ,并且 $g^e\not |f'$ 当且仅当 $eg'\neq 0$ .

证明由 $f$ 的表达式我们得到 $f'=ehg^{e-1}g'+g^eh',$ 则显然 $g^{e-1}|f'$ .另一方面 $g^e$ 对 $f'$ 的整除性等价于对 $ehg^{e-1}g'$ 的整除性，即 $g$ 是否能整除 $eg'$ ,由于 $\deg eg'<\deg g$ ，则 $g|eg'\Leftrightarrow eg'=0$ . □

注4 我们注意到，在特征为零的域中，当 $g$ 是一非平凡因子时， $g'\neq 0$ ,但在特征有限的域中，这一点并不一定正确，如 $g=x^3+1\in\mathbb{F}_3[x]$ 的形式微商 $g'$ $=$ $0$ .

有了上面的定理，则首先我们可以在特征为零的域上求出 $f$ 的无平方因子部分(squarefree part).

算法8(无平方因子部分)

对于输入的特征为零的域 $\mathbb{F}$ 上的 $n$ 次首一多项式 $f$ ，输出 $\displaystyle\frac{f}{\gcd(f,f')}$ .

还有一种无平方分解的算法，即若首一非平凡多项式 $f=g_1g_2^2\cdots g_m^m$ ,其中 $g_1,\ldots,g_m$ 两两互素且无平方因子， $g_m\neq 1$ ,则称 $(g_1,\ldots,g_m)$ 为 $f$ 的无平方分解(squarefree decompositon).在特征非零的域 $\mathbb{F}$ 上有如下一种较快的分解算法。

算法9(无平方分解)

$u=\gcd(f,f')$ , $v_1=f/u$ , $w_1=f'/u$ , $i=1$ ,
$h_i=\gcd(v_i,w_i-v_i')$ , $v_{i+1}=v_i/h_i$ , $w_{i+1}=(w_i-v_i')/h_i$ , $i=i+1$ ,
若 $v_i\neq 1$ 则转第2步,
输出 $(h_1,\ldots,h_{i-1})$ .

注5 该算法的思想是简单的,但要给出严格证明比较繁琐.其基本思想是利求导运算将不同次幂的不可约因子的次数变成某项前的系数，利用系数的不同将这些因子一层一层“剥离”出来.这个思想对于理解后面有限域上无平方分解算法的原理是很重要的.下面我们用一个例子来具体展示这一过程.

例4 $f=abc^2d^3$ 的无平方分解. ◇

解 $f'$ $=$ $a'bc^2d^3+ab'c^2d^3+2abcc'd^3+3abc^2d^2d'$ , $u=\gcd(f,f')=cd^2$ , $v_1=f/u=abcd$ ,

$w_1=f'/u=a'bcd+ab'cd+2abc'd+3abcd'$ , $w_1-v_1'$ $=$ $abc'd+2abcd'$ ,

$h_1=\gcd(abcd,abc'd+2abcd')=ab$ , $v_2=v_1/h_1=cd$ , $w_2=(w_1-v_1')/h_1=c'd+2cd'$ ,

$w_2-v_2'= cd'$ , $h_2=\gcd(cd,cd')=c$ , $v_3=v_2/h_2=d$ , $w_3=(w_2-v_2')/h_2=d'$ ,

$w_3-v_3' = 0$ , $h_3=\gcd(d,0)=d$ , $v_4=v_3/h_3=1$ , $w_4=(w_3-v_3')/h=0$ .

最后输出 $(ab,c,d)$ .

特征有限的域上无平方分解

我们再来考虑特征有限的域上无平方分解。我们已经看到在有限域上，例如素域 $\mathbb{F}_p$ 中，与特征为零的域的区别为对于一个非平凡的多项式 $f(\deg f\ge 1)$ ,它的形式微商仍然可能是零。下面探讨一下什么情况下形式微商为零，以及此时的多项式有什么特点。

考虑多项式 $f=\sum_{i=0}^nf_ix^i\in\mathbb{F}_p[x]$ , $p$ 是一素数.若其微商为零，则 $f'=\sum_{i=0}^nif_ix^{i-1}=0$ ,若 $f_i\neq 0$ ,则须有 $i\bmod p=0$ ,于是 $f$ 中所含的单项均是 $x$ 的 $p$ 的倍数的幂次项，亦即 $f=\sum_{i=0}^{n/p}f_ix^{ip}$ .于是： $f=\sum_{i=0}^{n/p}(f_ix^i)^p=\left(\sum_{i=0}^{n/p}f_ix^i\right)^p.$ 则 $f$ 是一个 $p$ 次幂，对于素幂阶的域 $\mathbb{F}_{q}(q=p^d)$ ,也有下面的结论：

定理4 若 $q$ 为素数 $p$ 的幂 $q=p^d$ ,非平凡多项式 $f\in\mathbb{F}_q[x]$ 且 $f'= 0$ ,那么 $f$ 为一 $p$ 次幂.

注6 该定理的证明要点在于注意到同 $\mathbb{F}_p$ 一样, $\mathbb{F}_q$ 中的元 $a$ 均有 $p$ 次根.

推论1 $\mathbb{F}$ 为任一域，则其上非平凡多项式 $f$ 是无平方因子的当且仅当 $\gcd(f,f')=1$ .

由上面的定理我们知道不可约非平凡多项式的形式微商一定非零。现在前面的算法唯一不可行之处即是对于 $p|e_i$ 的情形。设 $f=\prod_{i=1}^rf_i^{e_i}$ ,式中 $f_i$ 两两互素且不可约, $\deg f=n\ge 1$ , $e_1,\ldots,e_r$ 均是正整数.显然我们有 $f'= \prod_{p\not |e_i}e_i\frac{f}{f_i}f_i',$ 则 $u=\gcd(f,f')=\prod_{p\not |e_i}f_i^{e_i-1}\prod_{p|e_i}f_i^{e_i}$ ,于是 $v=\frac{f}{u}=\prod_{p\not |e_i}f_i,$ 其中缺少了某些项，这些项的次数均是 $p$ 的倍数.

我们注意到多项式 $u$ 中含有我们需要的这些幂次，且 $e_i\le n$ ,则有如下关系： $w=u/\gcd(u,v^n)=\prod_{p|e_i}f_i^{e_i},$ $w$ 为 $p$ 次幂。由此我们可以得到如下算法：

算法10(有限域无平方部分算法)

输入：有限域 $\mathbb{F}_q[x]$ 上首一非平凡多项式 $f$ , $\deg f=n$ .

输出： $f$ 的无平方部分 $g$ .

$u=\gcd(f,f')$ , $v=f/u$ , $w=u/\gcd(u,v^n)$ ,
若 $w=1$ ，则输出 $v$ ,否则递归调用本算法计算 $w^{1/p}$ 的无平方部分 $v_1$ .
输出 $vv_1$ .

例5 $f=a^2b^3c^6d^9\in\mathbb{F}_3[x]$ 的无平方部分,其中 $a,b,c,d$ 是互素且不可约首一多项式. ◇

解 $f'= 2aa'b^3c^6d^9$ , $u=\gcd(f,f')=ab^3c^6d^9$ , $v=f/u=a$ , $w=u/\gcd(u,v^n)=u/a=b^3c^6d^9$ ,

递归调用算法，计算 $f_1=w^{1/3}=bc^2d^3$ , $f_1'= b'c^2d^3+2bcc'd^3$ , $u_1=cd^3$ , $v_1=bc$ , $w_1=d^3$ ,

再次递归调用的结果为 $v_2=d$ .

故最后输出 $vv_1v_2=abcd$ .

上节中的例4给了我们对于算法9的理解： $v_i$ 序列包含了要处理的无平方部分， $g=v_1=g_1\cdots g_m$ , $w_1=\sum_{i=1}^{m}e_ig_i'g/g_i$ , $e_i$ 是 $g_i$ 在 $f$ 中的次数(在下面的说明中 $e_i=i$ )，每处理一次， $v_i$ 中去掉次数 $i$ 的项，如果是在有限域中，该算法就只能在 $m<p$ 时正确，因为它会将模 $p$ 相同的次数归于同一个次数（小于 $p$ 的那个）。即会有下面的结果： $h_i=\prod_{j\equiv i\pmod{p}}g_j\quad(1\le i<p),$ $h_i=1\quad(i\ge p).$

假设 $m>p$ , $f=\prod_{i=1}^mg_i^i$ ,则算出 $h_1,h_2,\ldots,h_{p-1}$ 后，令 $f_1=fh_1^{-1}h_2^{-2}\cdots h_{p-1}^{-p+1}$ ,则 $f_1=\prod_{i\ge p}g_i^{i-i\bmod p},$ 于是 $f_1^{\frac{1}{p}}=\prod_{i\ge p}g_i^{\left[\frac{i}{p}\right]}.$

如果我们能够构造递归算法以得到 $f_1^{1/p}$ 的无平方分解 $(s_1,\ldots,s_l)$ ,则显然有 $s_j=\prod_{[\frac{i}{p}]=j}g_i,$ 于是 $\gcd(h_i,s_j)=g_{jp+i}$ .

上面给我们提供了一种利用递归进行分解的想法：

算法11(有限域无平方分解) 输入：有限域 $\field{q}$ 上首一不可约多项式 $f$

输出: $f$ 的无平方分解 $(g_1,g_2,\ldots,g_m)$ .

调用算法9计算出 $h_k(1\le k<p)$ ,若 $f_1=\displaystyle\frac{f}{h_1h_2^2\cdots h_k^k}=1$ 则输出 $(h_1,\ldots,h_k)$ ,
递归调用本算法得到 $f_1^{1/p}$ 的无平方分解 $(s_1,s_2,\ldots,s_l)$ ,
令 $h_{k+1},\ldots,h_{p-1}=1$ ,
$g_{jp+i}=\gcd(h_i,s_j)\quad(1\le i<p,1\le j\le l)$ ,
$g_{jp}=\displaystyle\frac{s_j}{g_{jp+1}g_{jp+2}\cdots g_{(j+1)p-1}}\quad(1\le j\le l)$ ,
$g_i=\displaystyle\frac{h_i}{g_{p+i}g_{2p+i}\cdots g_{lp+i}}\quad(1\le i<p)$ ,
令 $m$ 为最大的使 $g_m\neq 1$ 的下标，则输出 $(g_1,\ldots,g_m)$ .

Berlekamp 算法

最早的多项式时间的算法是Berlekamp于1967至1970年间提出的.为了引入这个算法，我们有必要在此讨论一些代数问题.

Frobenius映射和Berlekamp子代数

定义4 $\field{q^n}$ 或 $\field{q}[x]$ 上( $q$ 为一素数幂)的映射 $\sigma:a\mapsto a^q$ 称为Frobenius映射.

注7 注意到Frobenius映射 $\sigma$ 是线性映射,且保持加法和乘法.

以下设 $f\in\field{q}[x]$ 是一首一无平方因子多项式, $\deg f=n$ 且 $f=\prod_{i=1}^{r}f_i$ , $f_i$ 为两两互素且不可约首一多项式.由中国剩余定理有下面的环同构： $R=\field{q}[x]/\idea{f}\cong\field{q}[x]/\idea{f_1}\times\cdots\times\field{q}[x]/\idea{f_r}=R_1\times\cdots\times R_r,$ 并定义同构映射： $\chi:a\in R\mapsto(a\bmod f_1,\ldots,a\bmod f_r).$

定理5 $\sigma$ 是 $R$ 上自同构.

证明由于 $\chi$ 是 $R$ 到 $\prod_{i=1}^rR_i$ 的同构,故可由 $\sigma$ 在 $R_i$ 上诱导出相应的线性映射 $\sigma_i:a_i\mapsto a_i^q(a_i\in R_i)$ ,于是 $\ker\sigma\cong\prod_{i=1}^r\ker\sigma_i$ .又由于 $R_i$ 为域，那么 $\sigma_i(a_i)=a_i^q=0$ 仅有 $q$ 重根 $0$ ,即 $\dim\ker\sigma_i=0$ ,因此 $\dim\ker\sigma=0$ , $\sigma$ 是单射.

又由于 $\dim R=\dim\mathrm{Im}\sigma+\dim\ker\sigma=\dim\mathrm{Im}\sigma$ ,则 $\sigma$ 是满射,因而是同构. □

定义5 记 $\mathcal{B}=\ker(\sigma-\mathrm{id})$ ,其是 $\field{q}$ 上 $R$ 的子代数，也被称为Frobenius子代数.

定理6 $\dim\mathcal{B}=r$ .

证明由于 $\chi$ 是 $R$ 到 $\prod_{i=1}^rR_i$ 上的同构，因此我们实际上将两者等同看待，则 $\sigma$ 可使 $(a\bmod f_1,\ldots,a\bmod f_r)\mapsto(a^q\bmod f_1,\ldots,a^q\bmod f_r).$ $\forall a\in\mathcal{B}$ ,记 $a_i=a\bmod f_i$ ,则 $a^q=a\Rightarrow a_i^q=a_i$ .但是 $a_i\in R_i=\field{q}[x]/\langle f_i\rangle$ , $R_i$ 实际上是一个域，其上的代数方程 $x^q-x=0$ 至多有 $q$ 个根，恰好是 $\field{q}$ 这个子域，即 $a_i\in\field{q}$ .

于是 $a\in\prod_{i=1}^r\field{q}\Rightarrow\mathcal{B}\subset\prod_{i=1}^r\field{q}$ .而显然后者也属于前者，于是有两者相等， $\dim\mathcal{B}=r$ . □

定义6 Frobenius映射在 $R$ 上自然基 $1,x,\ldots,x^{n-1}$ 下的表示矩阵记作 $Q\in\field{q}^{n\times n}$ ,称为Petr-Berlekamp矩阵.

推论2 $\field{q}$ 上无平方因子 $n$ 次多项式 $f$ 不可约当且仅当 $\rank(Q-I)=n-1$ .

推论3 $\field{q}$ 上无平方因子 $n$ 次多项式 $f$ 的不可约因子的个数为 $\ker\mathcal{B}=n-\rank(Q-I)$ .

取 $\mathcal{B}$ 的一组基 $b_1,b_2,\ldots,b_r$ ,因为 $\mathcal{B}=\prod_{i=1}^r\field{q}$ ,可设这组基在 $R_1\times R_2\times\cdots\times R_r$ 中的表示矩阵为 $B=(b_1,\ldots,b_r)=\begin{pmatrix} b_{11} &b_{21} &\cdots &b_{r1}\\ \vdots &\vdots & &\vdots\\ b_{1r} &b_{2r} &\cdots &b_{rr}\end{pmatrix}\in\field{q}^{n\times n}.$

此为一可逆矩阵，于是 $\forall 1\le i<j\le r$ , $\exists k(1\le k\le r)$ 使得 $b_{ik}\neq b_{jk}$ ,即 $b_k\bmod f_i\neq b_k\bmod f_j$ ,则对于 $b_k-b_{ik}$ 有 $f_i|(b_i-b_{ik}),\quad f_j\not |(b_i-b_{ik}).$

则 $b_i-b_{ik}$ 是可以分离 $f$ 的一个多项式.

推论4 任取 $\mathcal{B}$ 的一个基矢 $b_k$ ,任取 $a\in\field{q}$ ,则 $\gcd(b_k-a,f)$ 可能给出 $f$ 的一个非平凡因子.

Berlekamp算法的实现

有了上面的准备工作,下面我们可以来引入Berlekamp算法了.

算法12(Berlekamp算法1)

输入： $\field{q}$ 上无平方因子首一 $n$ 次非平凡多项式 $f$ ,

输出： $f$ 可能的非平凡因子，或者失败.

构作环 $R=\field{q}[x]/\idea{f}$ 上的Frobenius映射的表示矩阵 $Q$ ,即Petr-Berlekamp矩阵,
对 $Q-I$ 进行高斯消元法，求出 $\mathcal{B}=\ker(Q-I)$ 的 $r$ 个基矢， $b_1,\ldots,b_r$ ,
随机任取一个基矢 $b_k(1\le k\le r)$ ,任取 $a\in\field{q}$ ,对 $U$ 中任何一个元素 $u$ ,计算 $v=\gcd(b_k-a,u)$ ,若 $v\neq 1$ 且 $v\neq u$ ,则输出 $v$ ,否则输出失败.

注8 求Petr-Berlekamp矩阵时可先用快速求幂算法算出 $x^q\bmod f$ ,进而求出 $x^{qi}(1\le i\le n)$ .

下面是另外一种概率性的Berlekamp算法，能给出 $f$ 的可能因子.

算法13(Berlekamp算法2) 输入: $\field{q}$ 上无平方因子首一 $n$ 次非平凡多项式 $f$ ，其中 $q$ 是奇素数幂,

输出: $f$ 的可能非平凡因子,或者失败.

构作环 $R=\field{q}[x]/\idea{f}$ 上的Petr-Berlekamp矩阵Q,
对 $Q-I$ 进行高斯消元法，求出 $\mathcal{B}=\ker(Q-I)$ 的 $r$ 个基矢 $b_1,\ldots,b_r$ ,
随机任取互相独立的 $c_1,c_2,\ldots,c_r\in\field{q}$ ,计算 $a=\sum_{i=1}^rc_ib_i$ ,
$g_1=\gcd(b,f)$ ,若 $g_1\neq 1$ 且 $g_1\neq f$ 则输出 $g_1$ ,
$b=a^{(q-1)/2}\bmod f$ , $g_2=\gcd(b-1,f)$ ,
若 $g_2\neq 1$ 且 $g_2\neq f$ 则输出 $g_2$ ,否则输出失败.

该算法的正确性证明与奇素数幂同次因子分解类似,只须注意到 $\chi_i(a)\in\field{q}$ ,这样我们有 $a^{(q-1)/2}=0\vee 1$ ,两种取值等概率为 $1/2$ .

为了引入特征为2的域上与算法13对应的Berlekamp算法,我们先回忆定义2中对 $m$ 阶迹多项式(mth trace polynoial) $T_m$ 的定义.

引理5 设 $a$ 是 $\mathcal{B}=\ker(Q-I)$ 中任意一随机元素, $b=T_k(a)$ ,则 $\gcd(b-1,f)$ 可能给出 $f$ 的一个非平凡因子,且失败概率不超过 $1/2$ .

证明首先,由于 $\chi_i(a)\in\field{2^k}=\field{q}$ ,有 $\chi_i(T_k(a))=T_k(\chi_i(a))=0\vee 1$ ,且两值等概率.当且仅当 $\chi_i(b)$ 全为 $0$ 或 $1$ 时, $b=0\vee 1$ ,此概率为 $2^{1-r}\le 1/2$ .

易知,当且仅当 $b\not\in\field{2}$ 时, $\gcd(b-1,f)$ 含有 $f$ 的非平凡因子. □

于是对于特征为2的域 $\field{q}=\field{2^k}$ ,有如下的：

算法14(Berlekamp算法3) 将算法13中第5步改为计算 $b=T_k(a)$ ,其余不变.

有限域上的因子分解算法在近些年有很多进展,如1998年Kaltofen和Shoup的Subquadratic算法(见[2]),Huang和Pan的Fast rectangular matrix multiplication算法(见[3])等等.

素性检测和不可约多项式的构造

若要检测一个多项式的不可约性,前面的因子分解的方法当然也是适用的,只需相应修改算法终止即可,下面再介绍一个比较简单的检测方法.

推论5 $n$ 次非平凡多项式 $f\in\field{q}[x]$ 是不可约的当且仅当:

$f|x^{q^n}-x$ ,
$\forall$ 素数 $t(t|n)$ , $\gcd(x^{q^{n/t}}-x,f)=1$ .

证明由定理2知道上面两个条件是必要的.再设两个条件满足,则首先由条件1知 $f$ 的不可约因子次数均整除 $n$ ,不妨设有这样一个非平凡因子 $g$ 且 $\deg g=d<n$ ,则存在 $n$ 的素因子 $t$ 使 $d|(n/t)$ ,于是 $g|\gcd(x^{q^{n/t}}-x,f)$ ,矛盾,于是 $f$ 不可约. □

算法15(有限域上素性检测)

输入： $n$ 次多项式 $f\in\field{q}[x]$ ,

输出：不可约或可约.

调用快速求幂算法计算 $x^q\bmod f$ ,
调用模复合算法计算 $a=x^{q^n}\bmod f$ ,若 $a\neq x$ 则输出可约,
对于所有 $n$ 的素因子 $t$ ,调用模复合算法计算 $a=x^{q^{n/t}}\bmod f$ ,若 $\gcd(b-x,f)\neq 1$ 则输出可约,
输出不可约.

注9 模复合(Modular composition)算法是取自快速线性代数中的算法,这里不加证明地给出如下.

算法16(模复合算法)

输入： $f$ , $g$ , $h\in R[x]$ ,且 $\deg g$ , $\deg h<\deg f=n$ , $f$ 首一且不为零,

输出： $g(h)\bmod f\in R[x]$ .

$m=[n^{1/2}]$ ,并设 $g=\sum_{0\le i<m}g_ix^{mi}$ ,其中 $g_0,\ldots,g_{m-1}\in R[x]$ 的次数少于 $m$ ,
对于 $2\le i\le m$ ,计算 $h^i\bmod f$ ,
令 $A\in R^{m\times n}$ ,其行由 $1$ , $h\bmod f$ , $\cdots$ , $h^{m-1}\bmod f$ 的系数组成, $B\in R^{m\times m}$ ,其行由 $g_0,\ldots,g_{m-1}$ 的系数组成,计算 $BA\in R^{m\times n}$ ,
对于 $0\le i<m$ 循环,令 $r_i$ 为 $BA$ 第 $i$ 行作为系数构成的多项式,并计算 $b=\sum_{0\le i<m}r_i(h^m)^i\bmod f$ (利用Horner规则),
输出b.

构造一个不可约多项式的最基本的想法就是随机取一个多项式,再对其作素性检测。于是我们必须要对随机选取取到不可约多项式的概率进行估计。首先我们有下面的引理：

引理6 设 $q$ 是一素数幂, $n$ 是正整数,则 $\field{q}[x]$ 中 $n$ 次首一不可约多项式的个数 $I(n,q)$ 满足 $\frac{q^n-2q^{n/2}}{n}\le I(n,q)\le\frac{q^n}{n},$ 因此 $\field{q}[x]$ 中 $n$ 次首一多项式不可约的概率 $p_n$ 满足 $\frac{1}{n}(1-\frac{2}{q^{n/2}})\le p_n\le\frac{1}{n}.$

证明令 $f_n$ 为 $\field{q}[x]$ 中所有首一不可约 $n$ 次多项式的乘积，则 $\deg f_n=n\cdot I(n,q)$ ,由定理2知 $x^{q^n}-x=\prod_{d|n}f_d=f_n\cdot\prod_{d|n\wedge d<n}f_d.$

对上式取次数，有 $q^n=\deg f_n+\sum_{d|n\wedge d<n}\deg f_d,$ 因此 $q^n\ge\deg f_n=n\cdot I(n,q)\Rightarrow I(n,q)\le\frac{q^n}{n}.$

另外, $\sum_{d|n\wedge d<n}\deg f_d\le\sum_{1\le d\le n/2}\deg f_d\le\sum_{1\le d\le n/2}q^d<\frac{q^{n/2+1}-1}{q-1}\le 2q^{n/2},$ 因此 $n\cdot I(n,q)=\deg f_n=q^n-\sum_{d|n\wedge d<n}\deg f_d\ge q^n-2q^{n/2},$ 由此可得到关于 $I(n,q)$ 下界的估计.