一元多项式的最大公因子

结式
子结式
Euclid算法计算子结式

Mignotte界
大素数模公因子算法(Big Prime Modular Gcd Algorithm)
小素数模公因子算法(Small Prime Modular Gcd Algorithm)

设 $D$ 为UFD(即唯一析因整环,例如 $\mathbb{Z}$ ), $F$ 为域(例如 $\mathbb{R}$ )，则 $D[x],F[x]$ 也是UFD，对其上两多项式可讨论GCD问题.最古典的方法即是Euclid算法。然而，在上世纪六十年代末一些试验中发现这种算法在 $D[x]$ 或 $F[x]$ 中的系数增长很快，甚至于指数式。

为了解决这一问题，1971年，Collins,Brown提出了UFD上的多项式模最大公因子算法。对于多元情形，Mozes和Yun于1973年提出了基于Hensel提升方法的模因子算法。下面对经典的Euclid算法和改进算法进行论述。

Euclid算法

在Euclid整环 $F[x]$ 中,我们有如下的Euclid除法:

定义1(Euclid除法) 设 $f,g\in F[x]$ ,其中 $g\neq 0$ ,则存在唯一的 $q,r\in F[x]$ 使得 $f=qg+r,$ 其中 $\deg r<\deg g$ .定义此除法过程为Euclid除法,并且记商 $q=f\quo g$ ,余式 $r=f\rem g$ .

$F[x]$ 是Euclid整环，因而有以下的扩展Euclid算法：

算法1(扩展Euclid算法)

输入： $F[x]$ 上多项式 $f$ , $g$ ,

输出： $f$ , $g$ 的最大公因子 $u$ ,Bezout等式中的系数 $S=(s,t)$ 使得 $sf+tg=u$ .

1. $u=f,v=g,S=(1,0),T=(0,1)$ ,

2.如果 $v=0$ ,则转到第4步,

3. $r=u\rem v,q=u\quo v,L=S-qT,u=v,v=r,S=T,T=L$ ,并转回第2步,

4.输出 $u$ ， $S$ .

实际上在计算机中进行的是 $\mathbb{Q}[x]$ 上的运算，我们总可以找到整数乘到该多项式上使其化为 $\mathbb{Z}[x]$ 上的多项式。

定义2(本原多项式) 容度 $\mathrm{cont}(f)$ 定义为： $\mathrm{cont}(f)=\mathrm{gcd}(a_0,a_1,\ldots,a_n),$ 其中 $f=\sum a_ix^i\in D[x]$ ，且gcd对单项的定义为 $\mathrm{gcd}(a_0)=\mathrm{normal}(a_0),$ $f$ 的本原部分(primitive part)定义为 $\mathrm{pp}(f)=f/\mathrm{cont}(f)$ ，若 $f=\mathrm{pp}(f)$ ,则称其为本原多项式。

注1 在UFD中,可逆的元素称为单位,若有两个元素 $a,b$ 满足 $a|b$ 且 $b|a$ ,则称二者相伴,易证这是一等价关系,且 $a$ 和 $b$ 相伴当且仅当存在一个单位 $e$ 使得 $a=be$ .在这个等价关系下将UFD分类,在每个等价类中可取一个代表元,并记 $a$ 所在类的代表元为 $\mathrm{normal}(a)$ .对于整数环,我们知道单位为 $\pm 1$ ,且可取 $\mathrm{normal}(a)=|a|$ .

定理1 $\forall f\in D[x],c\in D$ ,我们有 $\mathrm{cont}(cf)=\mathrm{cont}(c)\mathrm{cont}(f),\mathrm{pp}(cf)=\mathrm{pp}(c)\mathrm{pp}(f)$ .

定理2(Gauss引理) $\forall f,g\in D[x]$ ,若 $f,g$ 本原，则 $h=fg$ 也是本原的。

类似的结论还有以下一些命题，相关内容可参阅相关的高等代数学内容,如[1].

定理3 $\forall f,g\in D[x],\mathrm{cont}(fg)=\mathrm{cont}(f)\mathrm{cont}(g),\mathrm{pp}(fg)=\mathrm{pp}(f)\mathrm{pp}(g)$

定理4 设 $f,g\in D[x],h=\mathrm{gcd}(f,g)\in D[x]$ ,则 $\mathrm{cont}(h)=\mathrm{gcd}(\mathrm{cont}(f),\mathrm{cont}(g))\in D,$ $\mathrm{pp}(h)=\mathrm{gcd}(\mathrm{pp}(f),\mathrm{pp}(g))\in D[x].$

于是有下面的：

算法2(一个UFD上多项式的Euclid算法)

输入： $D[x]$ 上的多项式 $f$ , $g$ ,

输出： $f,g$ 在 $D[x]$ 上的最大公因子 $h$ .

$h=\mathrm{gcd}(f,g)\in F[x]$ ,

$b=\mathrm{gcd}(\plc{f},\plc{g})$ ,

输出 $bh$ .

尽管 $D[x]$ 不是Euclid整环，但我们可引入 $D[x]$ 上的伪除法，来构造类似Euclid余式序列。

定义3(伪除法) $D$ 是UFD, $f,g\in D[x]$ ,则存在 $\alpha,\beta\in D$ , $q,r\in D[x]$ 使得 $\alpha f=qg+\beta r,$ 其中 $\deg r<\deg g$ ,且 $r$ 是本原多项式,将此过程称为多项式的伪除法,并记伪商 $q=f\pquo g$ ,伪余式 $r=f\prem g$ .

定义4(多项式余式序列) 若 $f,g\in D[x]$ ,且 $\mathrm{deg}(f)\ge\mathrm{deg}(g)$ ，令 $R_0=f,R_1=g$ ,且对于 $i$ ，令 $\alpha_iR_{i-1}=Q_iR_i+\beta_iR_{i+1}$ ,最后使得 $R_{k-1}\prem R_k=0$ ,则 $R_0,R_1,\ldots,R_k$ 称为多项式余式序列.

在用伪除法求最大公因子时就会导致系数增长很快，在后面介绍素数模方法之前，我们可以用下面定义的几个多项式余式序列一定程度上减小系数增长速度。

定义5(几种多项式余式序列) 若记 $\delta_i=\mathrm{deg}(R_{i-1})-\mathrm{deg}(R_i)$ ,则有如下定义:

(1)通常的伪余式序列： $\alpha_i=(\plc{R_i})^{\delta_i+1},\beta_i=\mathrm{cont}(R_{i-1}\prem R_i)$ .

(2)子结式余式序列： $\alpha_i=(\plc{R_i})^{\delta_i+1},\beta_1=(-1)^{\delta_1+1},$ $\beta_i=-(\plc{R_{i-1}})\psi_i^{\delta_i},(2\le i\le k),$ $\psi_1=-1,\psi_i=(-\plc{R_{i-1}})^{\delta_{i-1}}\psi_{i-1}^{1-\delta_{i-1}},(2\le i\le k),$

此方法计算量最小。

(3)约化多项式余式序列： $\alpha_i=(\plc{R_{i-1}})^{\delta_i+1},$ $\beta_1=1,\beta_i=\alpha_{i-1},(2\le i\le k).$

域上多项式的快速Euclid算法

1938年Lehmer最先提出了快速Euclid算法，后来Knuth(1970)，Schoenhage(1971),Moenck(1973),Aho,Hopcroft,UUman(1978),Schwartz(1980),Brent,Gustavson,Yun(1980),Strassen(1983)对这些算法也有论述。

在域(例如 $\mathbb{Z}_p$ )中，Euclid算法可表示为（各 $r_i$ 均为首一的）: $r_0=f,\quad r_1=g,\quad s_0=t_1=1,\quad s_1=t_0=0,$ $\begin{align*} &\rho_2r_2=r_0-q_1r_1,&&\rho_2s_2=s_0-q_1s_1,&&\rho_2t_2=t_0-q_1t_1,\\ &\cdots &&\cdots &&\cdots\\ &0=r_{l-1}-q_lr_l, &&\rho_{l+1}s_{l+1}=s_{l-1}-q_ls_l, &&\rho_{l+1}t_{l+1}=t_{l-1}-q_lt_l, \end{align*}$

若设 $\rho_{l+1}=1,r_{l+1}=0$ ，还可记 $Q_i=\begin{pmatrix}0 &1\\ \rho_{i+1}^{-1} &-q_i\rho_{i+1}^{-1}\end{pmatrix},$ 则 $R_i=Q_iQ_{i-1}\cdots Q_1=\begin{pmatrix}s_i &t_i\\ s_{i+1} &t_{i+1}\end{pmatrix}.$

易知 $\displaystyle\begin{pmatrix}r_i\\r_{i+1}\end{pmatrix}=R_i\begin{pmatrix}r_0\\r_1\end{pmatrix}.$

在随机情况下，可证明域 $\mathbb{F}_p$ 中 $\deg r_2<\deg r_1-1$ 的概率 $\mathrm{P}(\mathrm{deg}r_2<\mathrm{deg}r_1 - 1)=\displaystyle\frac{1}{p}$ ，当素数 $p$ 很大时，可认为 $r_i$ 序列的下降速度很慢。为了说明快速Euclid算法，我们先引入下面一些定义和定理。该算法的基本原理在于利用多项式的前某些系数来计算余式序列.

定义6(截式) 对于 $f=\sum_{i=0}^{n} f_ix^i\in\mathrm{Z}_p[x],k\in\mathrm{Z},k$ -截式(k-truncated polynomial)定义为 $f \upharpoonright k=f_nx^k+f_{n-1}x^{k-1}+\cdots+f_{n-k},$ 若 $i<0$ 则定义 $f_i=0$ ，若 $k<0$ 则令 $f\upharpoonright k=0$ ，即取 $f$ 的前 $k$ 个系数作一个新的多项式。

注2 当 $k\le n$ 时,有 $f\upharpoonright k=f \quo x^{n-k}$ ,反之有 $f\upharpoonright k=fx^{k-n}$ .

定理5 $\forall i\ge 0,(fx^i)\upharpoonright k=f\upharpoonright k$ .

定义7(k-度重合) 对于 $f,g,f^*,g^*\in\mathrm{Z}_p[x]\setminus\{0\}$ ,且 $\mathrm{deg}f\ge\mathrm{deg}g,\mathrm{deg}f^*\ge\mathrm{deg}g^*,k\in\mathrm{Z}$ ，则称 $(f,g)$ 与 $(f^*,g^*)k$ -度重合(coincide up to k)，如果 $f\upharpoonright k=f^*\upharpoonright k\wedge g\upharpoonright(k-\mathrm{deg}f+\mathrm{deg}g)=g^*\upharpoonright(k-\mathrm{deg}f^*+\mathrm{deg}g^*),$ 记为 $(f,g)\overset{k}{\sim}(f^*,g^*)$ ,此为一等价关系。

易知该等价关系有如下性质：

定理6 若 $(f,g)\overset{k}{\sim}(f^*,g^*)$ 且 $k\ge\mathrm{deg}f-\mathrm{deg}g$ ,则 $\mathrm{deg}f-\mathrm{deg}g=\mathrm{deg}f^*-\mathrm{deg}g^*$ .

关于 $k$ -度重合，有如下重要的命题：

定理7 对于 $k\in\mathbb{Z}$ ，若非零式 $f,g,f^*,g^*$ 满足 $(f,g)\overset{2k}{\sim}(f^*,g^*)$ ,且 $k\ge\mathrm{deg}f-\mathrm{deg}g\ge 0$ ,若有Euclid除法： $f=qg+r,\quad f^*=q^*g^*+r^*,$ 则

$q=q^*$ ,
$(g,r)\overset{2(k-\mathrm{deg}q)}{\sim}(g^*,r^*)\vee r=0\vee k-\mathrm{deg}q<\mathrm{deg}g-\mathrm{deg}r$ .

证明乘以 $x$ 的适当幂次后，可使 $\mathrm{deg}f=\mathrm{deg}f^*\ge k$ 成立，不妨设命题中的多项式已满足此式，则由定理6有 $\mathrm{deg}g=\mathrm{deg}g^*$ .下面分两部分证明本定理。

(1)首先我们有如下四个不等式:

$k\ge\mathrm{deg}q=\mathrm{deg}f-\mathrm{deg}g=\mathrm{deg}f^*-\mathrm{deg}g^*=\mathrm{deg}q^*$ ,

$\mathrm{deg}(f-f^*)<\mathrm{deg}f-2k\le\mathrm{deg}g-k$ (注意 $k$ -截式取多项式的前 $k+1$ 项),

$\mathrm{deg}(g-g^*)<\mathrm{deg}g-(2k-(\mathrm{deg}f-\mathrm{deg}g))=\mathrm{deg}f-2k\le\mathrm{deg}g-k\le\mathrm{deg}g-\mathrm{deg}q$ ,

$\mathrm{deg}(r-r^*)\le\max\{\mathrm{deg}r,\mathrm{deg}r^*\}<\mathrm{deg}g$ ,

根据上面的不等式,由 $f-f^*=q(g-g^*)+(q-q^*)g^*+(r-r^*)$ 可知 $\mathrm{deg}[(q-q^*)g^*]<\mathrm{deg}g$ ,故 $q=q^*$ .

(2)假定 $r\neq 0$ 且 $k-\mathrm{deg}q\ge\mathrm{deg}g-\mathrm{deg}r$ ，则首先显然有 $g\upharpoonright 2(k-\mathrm{deg}q)=g^*\upharpoonright 2(k-\mathrm{deg}q),$

另外， $\begin{align*} \mathrm{deg}(r-r^*)&\le\max\{\mathrm{deg}(f-f^*),\mathrm{deg}q+\mathrm{deg}(g-g^*)\}\notag\\ &<\mathrm{deg}q+\mathrm{deg}f-2k\notag\\ &=\mathrm{deg}g-2(k-\mathrm{deg}q)\notag\\ &=\mathrm{deg}r-[2(k-\mathrm{deg}q)-(\mathrm{deg}g-\mathrm{deg}r)],\notag \end{align*}$

又由假设有 $\mathrm{deg}r\ge\mathrm{deg}q+\mathrm{deg}g-k\ge\mathrm{deg}q+\mathrm{deg}f-2k\Rightarrow\mathrm{deg}r=\mathrm{deg}r^*$ ,

于是 $r\upharpoonright[2(k-\mathrm{deg}q)-(\mathrm{deg}g-\mathrm{deg}r)]=r^*\upharpoonright[2(k-\mathrm{deg}q)-(\mathrm{deg}g^*-\mathrm{deg}r^*)]$ ,

故 $(g,r)\overset{2(k-\mathrm{deg}q)}{\sim}(g^*,r^*)$ . □

下面考虑两个首一的多项式Euclid余式序列：

$\begin{align*} &r_0=q_1r_1+\rho_2r_2\qquad &r_0^*=q_1^*r_1^*+\rho_2^*r_2^*\notag\\ &\vdots &\vdots\notag\\ &r_{l-1}=q_lr_l &r_{l^*-1}^*=q_{l^*}^*r_{l^*}^*\notag\\ \end{align*}$

分别令 $m_i=\deg q_i,m_i^*=\deg q_i^*,n_i=\deg r_i=n_0-m_1-\cdots-m_i$ ,对 $k\in\mathbb{N}$ ,定义 $\eta(k)=\max\{0\le j\le l|\sum\limits_{1\le i\le j}m_i\le k\}$ ,且显然有 $n_0-n_{\eta(k)}=\sum_{1\le i\le \eta(k)}m_i\le k<\sum\limits_{1\le i\le\eta(k)+1}m_i=n_0-n_{\eta(k)+1}.$

下面的定理是快速Euclid算法的基础：

定理8[2] 对于 $k\in\mathbb{N},h=\eta(k),h^*=\eta^*(k)$ ,若 $(r_0,r_1)\overset{2k}{\sim}(r_0^*,r_1^*),$ 则 $h=h^*,q_i=q_i^*,\rho_{i+1}=\rho_{i+1}^*$ 对 $1\le i\le h$ 成立。

证明只需对 $0\le j\le h$ 的 $j$ 进行归纳，证明如下命题：

$j\le h^*,q_i=q_i^*,\rho_{i+1}=\rho_{i+1}^*$ 对于 $1\le i\le j$ 成立，且 $j=h$ 或 $(r_j,r_{j+1})\overset{s}{\sim}(r_j^*,r_{j+1}^*),\text{其中}s=2(k-\displaystyle\sum_{1\le i\le j}m_i).$

$j=0$ 时命题无须论证，由定理7可以证明归纳过程。另外 $\sum_{1\le i\le j}\deg q_i^*=\sum_{1\le i\le j}\deg q_i\le\sum_{1\le i\le h}\deg q_i\le k\Rightarrow j\le\eta^*(k)=h^*.$ 证毕。 □

由此我们可以得到下面的算法：

算法3(快速扩展Euclid算法)

输入：首一多项式 $r_0,r_1\in F[x],k\in\mathbb{N}(0\le k\le n)$ ,其中 $n=n_0=\deg r_0>n_1=\deg r_1$ ,

输出： $h=\eta(k)$ 以及 $R_h\in M_{2\times 2}(F[x])$ .

如果 $r_1=0$ 或 $k<n_0-n_1$ ,则输出 $0,\begin{pmatrix}1\quad 0\\0\quad 1\end{pmatrix}$ ,
$d=\lfloor k/2\rfloor$ ,
递归调用本算法，输入 $r_0\upharpoonright 2d,r_1\upharpoonright (2d-(n_0-n_1)),d$ ,并将结果输出至 $j-1=\eta(d),R=Q_{j-1}\cdots Q_1$ ,
赋值 $\begin{pmatrix}r_{j-1}\\r_j\end{pmatrix}=R\begin{pmatrix}r_0\\r_1\end{pmatrix}$ , $\begin{pmatrix}n_{j-1}\\n_j\end{pmatrix}=\begin{pmatrix}\deg r_{j-1}\\ \deg r_j\end{pmatrix}$ ,
如果 $r_j=0$ 或者 $k<n_0-n_j$ 则输出 $j-1,R$ ,
赋值 $q_j=r_{j-1}\quo r_j$ , $\rho_{j+1}=\plc{r_{j-1}\rem r_j}$ , $r_{j+1}=\mathrm{monic}(r_{j-1}\rem r_j)$ , $n_{j+1}=\deg r_{j+1}$ , $d^*=k-(n_0-n_j)$ ,
递归调用本算法，输入 $r_j\upharpoonright 2d^*,r_{j+1}\upharpoonright(2d^*-(n_j-n_{j+1})),d^*$ ,并将结果输出至 $h-j=\eta(d^*),S=Q_h\cdots Q_{j+1}$ ,
赋值 $Q_j=\begin{pmatrix}0 &1\\ \rho_{j+1}^{-1} &-q_j\rho_{j+1}^{-1}\end{pmatrix}$ ,
输出 $h,SQ_jR$ .

注3 理论上每次取 $k$ 时应当使恰好只计算一步，这样可以达到最高的效率，即既不多取了不必要的系数进行计算，又不致于系数取得不够。当余式序列的次数 $n_i$ 下降得缓慢时，相应的 $k$ 就可以取得比较小。实际中无法根据 $n_i$ 的信息选择，因而有上面的二分递归的策略来选择.

注4 初始进行函数调用时，我们可取 $k=n$ ,根据 $\eta(k)$ 的定义我们知道 $\eta(k)=l$ ,因而算法必将返回 $l$ 和 $R_l$ ,根据 $R_l$ 可以得到 $r_l$ ,即最大公因子.

后面将会提到 $\mathbb{Z}[x]$ 上的素数模公因子算法，而 $\mathbb{Z}_p$ 为一域，如果再用到本节所提到的快速Euclid算法，则可提高计算效率。

结式与子结式

结式

对于多项式最大公因子问题，结式理论纯粹是一个概念上的工具，并没有用于算法中，但是对于它们的分析对后面的GCD算法理论有重要的作用(见[2]P142).然而结式的计算在某些问题中却十分重要,如符号积分中将要计算的Rothstein-Trager结式(可参见后文有关章节).因此前两小节介绍结式和子结式,第三小节讲它们的计算方法.

引理1 设非零多项式 $f$ , $g\in F[x]$ , $F$ 是域。那么 $\gcd(f,g)\neq 1$ 当且仅当 $\exists s,t\in F[x]\setminus\{0\}$ 使得 $sf+tg=0$ ，且 $\deg s<\deg g$ , $\deg t<\deg f$ .

证明

令 $h=\gcd(f,g)$ ，若 $f\neq 1$ ,则 $\deg h\ge 1$ ，令 $s=-g/h$ , $t=f/h$ 则满足。

反过来，设存在这样的 $s$ , $t$ ，若 $f$ , $g$ 互素，则 $sf=-tg\Rightarrow f|t$ ，这与 $t\neq 0$ 且 $\deg f>\deg t$ 矛盾，因此 $h=1$ . □

注5 当 $F$ 是UFD时仍有上面的引理成立.

定义8 对于 $d\in\mathbb{N}$ ，定义 $P_d=\{a\in F[x]|\deg a<d\}$ .

定义9 对于给定的 $n$ , $m$ 次多项式 $f$ , $g\in F[x]$ ，定义 $\varphi=\varphi_{f,g}:F[x]\times F[x]\rightarrow F[x]\qquad\text{使得} (s,t)\rightarrow sf+tg,$ $\varphi_0:P_m\times P_n\rightarrow P_{n+m}$ 作为 $\varphi$ 在其上的限制。

定理9 设 $f$ , $g\in F[x]$ 为 $n$ , $m$ 次非零多项式，那么有下面的结论：

$\gcd(f,g)=1\Leftrightarrow \varphi_0$ 是同构.
若 $\gcd(f,g)=1$ ，则Bezout系数 $s$ , $t$ 构成 $\varphi_0(s,t)=1$ 的唯一解.

证明由引理1知 $\deg\gcd(f,g)\ge 1\Leftrightarrow \varphi_0$ 不是单射.

由于 $F[x]$ 是PID(主理想整环),则 $\gcd(f,g)=1\Leftrightarrow\varphi_0$ 是满射.

因此第一条结论满足。由同构又知这样的 $s$ , $t$ 也是唯一的。 □

如果记 $(s,t)=(y_{m-1},\ldots,y_0,z_{n-1},\ldots,z_0)^T$ ，其中 $s=\sum_{0\le j<m}y_jx^j$ , $t=\sum_{0\le j<n}z_jx^j$ ,则线性映射 $\varphi_0$ 可在自然基 $\{(x^j,0)\}_{0\le j\le m-1},\{(0,x^j)\}_{0\le j\le n-1}$ 下表示矩阵是Sylvester矩阵：

$S=\begin{pmatrix}f_n&\qquad &\qquad &\qquad &g_m& \qquad &\qquad &\qquad &\qquad &\qquad \\ f_{n-1} &f_n & & &g_{m-1} &g_m & & & &\\ \vdots &\vdots &\ddots & &\vdots &\vdots &\ddots & & &\\ \vdots &\vdots & &f_n &g_1 &\vdots & &\ddots & &\\ \vdots &\vdots & &f_{n-1} &g_0 &\vdots & & &\ddots &\\ \vdots &\vdots & &\vdots & &g_0 & & & &g_m\\ f_0 &\vdots & &\vdots & & &\ddots & & &\vdots\\ &f_0 & &\vdots & & & &\ddots & &\vdots\\ & &\ddots &\vdots & & & & &\ddots &\vdots\\ & & &f_0 & & & & & &g_0 \end{pmatrix}.$

上面的定理用矩阵语言描述即为:

推论1 我们有下面的推论:

$\gcd(f,g)=1\Leftrightarrow \det S\neq 0$ ,
若 $\gcd(f,g)=1$ ,且 $y_0,y_1,\ldots,y_{m-1},z_0,\ldots,z_{n-1}\in F$ 满足 $S(y_{m-1},\ldots,y_0,z_{n-1},\ldots,z_0)^T=(0,0,\ldots,0,1)^T,$ 那么 $s=\sum y_ix^i$ , $t=\sum z_ix^i$ 为Bezout系数,使得 $sf+tg=1$ .

定义10 若D是UFD，且 $f,g\in D[x]$ ，则 $S=\mathrm{Syl}(f,g)$ 是它们的Sylvester矩阵，其行列式 $\det S$ 称为结式,记作 $\mathrm{res}(f,g)$ .

对于一些特殊情况，当 $n=m=0$ 时 $S$ 是空矩阵，且结式为1。若 $f$ 为0或非常数多项式，则 $\mathrm{res}(f,0)=\mathrm{res}(0,f)=0$ ，若 $f$ 是非零常数则 $\mathrm{res}(f,0)=\mathrm{res}(0,f)=1$ .前面定理在这些情形下仍然成立.

推论2 设 $F$ 为域，且有非零多项式 $f,g\in F[x]$ ，则下面各条件等价：

$\gcd(f,g)=1$ ,
$\mathrm{res}(f,g)=\deg S\neq 0$ ,
不存在非零多项式 $s,t\in F[x]$ 使得 $sf+tg=0,\quad\deg s<\deg g,\quad\deg t<\deg f.$

推论3 设 $R$ 是UFD,且非零多项式 $f,g\in R[x]$ .则 $\gcd(f,g)$ 非平凡当且仅当 $\mathrm{res}(f,g)=0$ .

推论4 若 $R$ 是一UFD,非零多项式 $f,g\in R[x]$ ，则存在非零多项式 $s,t\in R[x]$ 使得 $sf+tg=\mathrm{res}(f,g)$ 且 $\deg s<\deg g,\deg t<\deg f$ .

证明令 $F$ 是 $R$ 的有理扩张域。若 $r=\mathrm{res}(f,g)=0$ ，则由推论2知存在这样的 $s,t\in F[x]$ ，再将其乘一个公分母即可。若 $r\neq 0$ ，则 $f,g$ 互素，于是存在 $s^*,t^*\in F[x]$ 满足 $\deg s^*<\deg g,\deg t^*<\deg f$ 且 $s^*f+t^*g=1$ ,由线性方程组的Cramer法则知 $s=rs^*,t=rt^*$ 满足。 □

引理2 设 $R$ 为UFD，非零多项式 $f,g\in R[x]$ ， $r=\mathrm{res}(f,g)\in R$ ， $I\subset R$ 为一理想，记 $R$ 中元素 $a$ 模 $I$ 的像为 $\overline{a}$ ,设 $\overline{\plc{f}}\neq 0$ .则

$\overline{r}=0\Leftrightarrow \mathrm{res}(\overline{f},\overline{g})=0$ ,
若 $R/I$ 是UFD，则 $\overline{r}=0\Leftrightarrow\gcd(\overline{f},\overline{g})$ 非常数。

证明由 $\overline{\plc{f}}\neq 0$ 可知 $\mathrm{Syl}(\overline{f},\overline{g})$ 的"尺寸"并不会减小,因此有 $\overline{r}=0\Leftrightarrow\mathrm{res}(\overline{f},\overline{g})=0$ .

再假设 $\overline{g}\neq 0$ ,令 $i$ 为最小的指标使得 $\overline{g_{m-i}}\neq 0$ ,此时将Sylvester矩阵分块，去掉左 $i$ 列和上 $i$ 行，只留下右下 $(m+n-i)\times(m+n-i)$ 的方阵 $M$ ，显然 $M=Syl(\overline{f},\overline{g})$ ,于是 $\overline{r}=\overline{f_n^i\det M}=\overline{f_n^i}\mathrm{res}(\overline{f},\overline{g})$ ，于是引理得证。 □

子结式

设 $F$ 为任一域， $f$ , $g$ 是 $F[x]$ 上非零多项式，其 $f$ 的次数 $n$ 大于等于 $g$ 的次数 $m$ .如同快速Euclid算法一节所列表格,我们再次将Euclid算法的过程表示如下（各 $r_i$ 均为首一的）： $\rho_0r_0=f,\quad\rho_1r_1=g,\quad\rho_0s_0=\rho_1t_1=1,\quad\rho_1s_1=\rho_0t_0=0,$ $\begin{align*} &\rho_2r_2=r_0-q_1r_1,&&\rho_2s_2=s_0-q_1s_1,&&\rho_2t_2=t_0-q_1t_1,\\ &\cdots &&\cdots &&\cdots\\ &f=r_{l-1}-q_lr_l,&&\rho_{l+1}s_{l+1}=s_{l-1}-q_ls_l,&&\rho_{l+1}t_{l+1}=t_{l-1}-q_lt_l, \end{align*}$

对此有如下的

定义11 $n_i=\deg r_i(0\le i\le l+1)$ 称为次数序列.

定理10 设 $0\le k\le m\le n$ ,则 $k$ 不出现在次数序列当且仅当存在 $s$ , $t\in F[x]$ ,满足 $t\neq 0,\quad\deg s<m-k,\quad\deg t<n-k,\quad\deg(sf+tg)<k.$

证明必要性:若 $k$ 不在次数序列中，则存在 $i(2\le i\le l+1)$ 使得 $n_i<k<n_{i-1}$ ,于是 $s_if+t_ig=r_i,\deg r_i=n_i<k$ ,且 $\deg s_i=m-n_{i-1}<m-k$ , $\deg t_i=n-n_{i-1}<n-k$ .最后两个不等式可以用Euclid辗转相除的过程归纳证明.

而当 $i=l+1$ 时, $s=g/r_l,t=-f/r_l,k<n_l$ 且 $r_{l+1}=0$ .

充分性:由[2]引理5.15可知 $\exists i(1\le i\le l+1)$ 和 $\alpha\in F[x]\setminus\{0\}$ 使得 $t=\alpha t_i,$ , $s=\alpha s_i$ , $r=sf+tg=\alpha r_i$ ,于是 $n-n_{i-1}\le\deg\alpha+n-n_{i-1}=\deg(\alpha t_i)=\deg t<n-k,$ $n_i\le\deg \alpha+n_i=\deg(\alpha r_i)=\deg r<k,$ 故 $n_i<k<n_{i-1}$ . □

为了将上面的内容翻译成一种代数语言,我们考虑上一节定义的线性映射 $\varphi$ 在 $P_{m-k}\times P_{n-k}$ 上的限制.然而我们容易知道,该映射的象是在空间 $P_{n+m-k}$ 中,为了使得其具有在满足某些条件下有成为同构的可能性,我们要使两个空间维数相等.进而我们考虑了如下的线性映射: $\varphi_k:P_{m-k}\times P_{n-k}\rightarrow P_{n+m-2k}$ ,其满足 $(s,t)\mapsto sf+tg\quad \mathrm{quo}\quad x^k.$

我们有如下的推论:

推论5 所有的记号定义同前,则:

$k$ 在次数序列 $\{n_i\}$ 中当且仅当 $\varphi_k$ 是同构.
若 $k=n_i$ ,则 $s_i,t_i$ 是 $\varphi_k(s_i,t_i)=1$ 的唯一解.

我们记 $\varphi_k$ 的矩阵形式为 $S_k$ ,其也取为自然基上的表示,为Sylvester矩阵的子矩阵:

$\begin{pmatrix} f_n & & & &g_m & & &\\ f_{n-1} &f_n & & &g_{m-1} &g_m & &\\ \vdots & &\ddots & &\vdots & &\ddots &\\ f_{n-m+k+1} &\cdots &\cdots &f_n & g_{k+1} &\cdots &\cdots &g_m\\ \vdots & & &\vdots &\vdots & & &\vdots\\ f_{k+1} &\cdots &\cdots &f_m &g_{m-n+k+1} & & &\vdots\\ \vdots & & &\vdots &\vdots & & &\vdots\\ f_{2k-m+1} &\cdots &\cdots &f_k &g_{2k-n+1} &\cdots &\cdots &g_k \end{pmatrix}.$

推论6 我们有下面的推论:

$k$ 在次数序列中当且仅当 $\det S_k\neq 0$ .
若 $k=n_i$ ,且 $y_0,\ldots,y_{m-k-1},z_0,\ldots,z_{n-k-1}\in F$ 是下面的线性方程 $S_k(y_{m-k-1},\ldots,y_0,z_{n-k-1},\ldots,z_0)^T=(0,\ldots,0,1)^T$ 的唯一解,则 $s=\sum y_jx^j$ , $t=\sum z_jx^j$ .

定义12 $\sigma_k=\det S_k$ 称为子结式.

Euclid算法计算子结式

我们一步步来推出子结式的计算方法.首先我们有如下引理:

推论7 设 $f,g,r\in F[x]$ 首一且次数分别为 $n,m,d$ ,其中 $n\ge m$ ,且 $\rho r=f\rem g,\rho\in F\setminus\{0\},$ 则对于 $k(0\le k\le d)$ 有 $\sigma_k(f,g)=(-1)^{(n-k)(m-k)}\rho^{m-k}\sigma_k(g,r).$

证明设 $f=qg+\rho r$ , $q$ 为 $(n-m)$ 次多项式,于是 $\begin{pmatrix} 1\\f_{n-1}\\ \vdots\\ f_0 \end{pmatrix}-\begin{pmatrix} 1 & &\\g_{m-1} &\ddots &\\ \vdots & &1\\ g_0 & &\vdots\\ &\ddots &\vdots\\ & &g_0 \end{pmatrix}\begin{pmatrix} q_{n-m}\\ \vdots\\ q_0 \end{pmatrix}=\begin{pmatrix} 0\\ \vdots\\ 0\\ \rho r_d\\ \vdots\\ \rho r_0 \end{pmatrix}.$ 由此可以对 $\det S_k$ 作初等列变换,并交换一些列的顺序,我们得到 $\sigma_k=\det S_k=(-1)^{(n-k)(m-k)}\det\begin{pmatrix} 1 & & & & &\\ g_{m-1} &\ddots & &\rho r_d & &\\ \vdots & &1 &\vdots &\ddots &\\ \vdots & &\vdots &\vdots & &\rho r_d\\ g_{2k-n+1} &\cdots &g_k &\rho r_{2k-m+1} &\cdots &\rho r_k \end{pmatrix}.$ 上面的矩阵用分块可表示为如下形式: $\begin{pmatrix} 0 &0\\ * &S_k(g,\rho r) \end{pmatrix},$ 因此, $\sigma_k=(-1)^{(n-k)(m-k)}\sigma_k(g,\rho r)=(-1)^{(n-k)(m-k)}\rho^{m-k}\sigma_k(g,r)$ . □

进而我们有下面的定理:

定理11 设 $f=\rho_0r_0,g=\rho_1r_1\in F[x]$ , $\deg f=n\ge\deg g=m$ ,且 $r_0,r_1$ 首一,则:

(1)对于 $k(0\le k\le m)$ ,有 $\begin{equation*} \sigma_k=\det S_k=\begin{cases} (-1)^{\tau_i}\rho_0^{m-n_i}\prod_{1\le j\le i}\rho_j^{n_{j-1}-n_j},\quad &k=n_i,\\ 0,&k\not\in\{n_i\}, \end{cases} \end{equation*}$ 其中 $\tau_i=\sum_{1\le j< i}(n_{j-1}-n_i)(n_j-n_i)$ .

(2) $\sigma_m=\rho_1^{n-m}$ , $\sigma_{n_{i+1}}=(-1)^{(n_i-n_{i+1})(n-n_{i+1}+i+1)}(\rho_0\cdots\rho_{i+1})^{n_i-n_{i+1}}\sigma_{n_i}$ .

证明对于(1)中第一种情况,只需归纳证明并且注意 $\sigma_k(r_{i-1},r_i)=1$ .

对于(2),只需化简 $\tau_{i+1}-\tau_i\pmod{2}$ ,有 $\begin{align*} \tau_{i+1}-\tau_i&\equiv\sum_{1\le j<i+1}(n_{j-1}-n_{i+1})(n_j-n_{i+1})-\sum_{1\le j<i}(n_{j-1}-n_i)(n_j-n_i)\\ &\equiv n_{i-1}n_i-n_0n_{i+1}-n_in_{i+1}+in_{i+1}^2+n_0n_i+n_{i-1}n_i-(i-1)n_i^2\\ &\equiv n(n_i-n_{i+1})-n_in_{i+1}+in_{i+1}^2-(i-1)n_i^2\\ &\equiv (n-n_{i+1})(n_i-n_{i+1})+(i+1)(n_{i+1}^2-n_i^2)\\ &\equiv (n-n_{i+1}+i+1)(n_i-n_{i+1})\pmod{2}, \end{align*}$ 于是显然可以得到(2)中的递推式. □

取 $k=0$ ,则 $\sigma_k$ 即为结式,因此我们得到如下计算结式的方法:

推论8 若 $\deg\gcd(f,g)\ge 1$ ,则 $\mathrm{res}(f,g)=0$ ,否则 $\mathrm{res}(f,g)=(-1)^{\tau}\rho_0^{n_1}\prod_{1\le j\le l}\rho_j^{n_{j-1}},$ 其中 $\tau=\sum_{1\le j<l}n_{j-1}n_j$ .

事实上,对于 $F$ 是UFD的情况,上面推论一般也是成立的.例如下面举了一个 $F=\mathbb{R}[y]$ 的例子来说明:

例1 考虑 $f=x^2-y$ , $g=yx+1$ ,二者的结式为: $\mathrm{res}_x(f,g)=1-y^3.$

当用上面的推论来计算时,我们有 $n_0=2\quad r_0=x^2-y\quad \rho_0=1,$ $n_1=1\quad r_1=x+\frac{1}{y}\quad \rho_1=y,$ $n_2=0\quad r_2=1\quad \rho_2=\frac{1}{y^2}-y.$

于是结式为 $\mathrm{res}(f,g)=(-1)^{2\cdot 1}1^1\times y^2\times(1/y^2-y)^1=1-y^3$ . ◇

$\mathbb{Z}[x]$ 中的模GCD算法

模算法基于的思想是将整数环中的运算化为有限域上的运算,最后通过中国剩余定理算法将有限域中结果还原到整数环中.例如有两个多项式 $f,g\in\mathbb{Z}[x]$ ,考虑素数 $p$ ,令 $h=\gcd(f,g),h_p=h\bmod p,v_p=\gcd(f_p,g_p)$ ,我们要求 $h=h_p=v_p$ ,那么就可以用有限域中的结果 $v_p$ 来代替 $h$ ,然而若要 $h=h_p$ ,我们需要Mignotte界的保证.对于 $h_p=v_p$ ,其成立的条件我们后面也会给出理论上的分析.

Mignotte界

定义13(多项式的范数) 对于 $f=\sum\limits_{i=0}^{n} f_ix^i\in\mathbb{C}[x]$ ,定义其 $k$ -范数为： $\lVert f\rVert_k=\left(\sum\limits_{i=0}^{n}|f_i|^k\right)^{\frac{1}{k}}.$

由线性赋范空间的相关内容易如有如下结论： $\lVert f\rVert_{\infty}\le\lVert f\rVert _2\le\lVert f\rVert _1\le(n+1)\lVert f\rVert _{\infty}.$

首先我们有如下的引理：

引理3 $\forall f\in\mathbb{C}[x]$ , $z\in\mathbb{C}$ ,我们有 $\lVert (x-z)f\rVert _2=\lVert(\overline{z}x-1)f\rVert_2$ .

证明设 $\deg f=n$ ，并记 $f_{-1}=f_{n+1}=0$ ，则 $\begin{align*} \lVert (x-z)f\rVert _2^2=&\sum\limits_{i=0}^{n+1}|f_{i-1}-zf_i|^2=\sum\limits_{i=0}^{n+1}(f_{i-1}-zf_i)(\overline{f_{i-1}}-\overline{z}\overline{f_i})\\ &=\lVert f\rVert_2^2(1+|z|^2)-\sum\limits_{i=0}^{n+1}(z\overline{f_{i-1}}f_i+\overline{z}f_{i-1}\overline{f_i})\\ &=\sum\limits_{i=0}^{n+1}(\overline{z}f_{i-1}-f_i)(z\overline{f_{i-1}}-\overline{f_i})\\ &=\sum\limits_{i=0}^{n+1}|\overline{z}f_{i-1}-f_i|^2\\ &=\lVert(\overline{z}x-1)f\rVert_2^2, \end{align*}$ 证毕. □

注6 对于上面的引理,我们可以给出如下更加巧妙的证明:

证明我们给出断言, $\forall f\in\mathbb{C}[x]$ , $\|f\|_2^2=\frac{1}{2\pi}\int_0^{2\pi}|f(e^{i\phi})|^2\mathrm{d}\phi.$

此由三角函数系的正交归一性显然可以看出.于是 $\begin{align*} \|(x-z)f\|_2^2&=\frac{1}{2\pi}\int_0^{2\pi}|(e^{i\phi}-z)f(e^{i\phi})|^2\mathrm{d}\phi=\frac{1}{2\pi}\int_0^{2\pi}|(ze^{-i\phi}-1)f(e^{i\phi})|^2\mathrm{d}\phi\\ &=\frac{1}{2\phi}\int_0^{2\phi}|(\overline{z}e^{i\phi}-1)f(e^{i\phi})|^2\mathrm{d}\phi\\ &=\|(\overline{z}x-1)f\|_2^2, \end{align*}$ 证毕. □

若 $z_1,z_2,\ldots,z_n$ 是 $f(x)=0$ 的 $n$ 个复根，则显然有 $f=\sum\limits_{i=0}^nf_ix^i=f_n\prod\limits_{i=1}^n(x-z_i)$ .

定义14 定义 $M(f)=|f_n|\prod\limits_{i=1}^n\max\{1,|z_i|\}$ .

显然， $M(f)\ge|f_n|$ 且 $f=gh\Rightarrow M(f)=M(g)M(h)$ .

关于上面定义的 $M(f)$ ，还有下面的：

定理12(Landau不等式) $\forall f\in\mathbb{C}[x]$ , $M(f)\le\lVert f\rVert_2$ .

证明不妨设 $|z_1|,|z_2|,\ldots,|z_k|>1$ 且 $|z_{k+1}|,\ldots,|z_n|\le 1$ ,则 $M(f)=|f_nz_1z_2\cdots z_k|.$ 令 $g=f_n\prod\limits_{i=1}^{k}(\overline{z_i}x-1)\prod\limits_{k+1}^n(x-z_i)=g_nx^n+\cdots+g_0\in\mathbb{C}[x]$ ，则由引理3有 $\begin{align*} M^2(f)&=|f_n\overline{z_1}\overline{z_2}\cdots\overline{z_k}|^2=|g_n|^2\le\lVert g\rVert_2^2\\ &=\left\lVert\frac{g}{(\overline{z_1}x-1)}(x-z_1)\right\rVert_2^2\\ &=\cdots=\left\lVert\frac{g}{(\overline{z_1}x-1)(\overline{z_2}x-1)\cdots(\overline{z_k}x-1)}(x-z_1)(x-z_2)\cdots(x-z_k)\right\rVert_2^2\\ &=\lVert f\rVert_2^2, \end{align*}$ 证毕. □

引理4 若 $h=\sum\limits_{i=0}^mh_ix^i\in\mathbb{C}[x]$ 整除 $f=\sum\limits_{i=0}^nf_ix^i\in\mathbb{C}[x]$ , $n\ge m$ ，则 $\lVert h\rVert_2\le\lVert h\rVert_1\le 2^mM(h)\le \displaystyle\left|\frac{h_m}{f_n}\right|2^m\lVert f\rVert_2$ .

证明设 $h=h_m\prod\limits_{i=1}^m(x-u_i)$ ,则由韦达定理， $h_i=(-1)^{m-i}h_m\sum\limits_{\substack{s\subset{1,2,\ldots,m}\\|S|=m-i}}\prod\limits_{j\in S}u_j,$ 于是 $|h_i|\le|h_m|\sum\limits_{S}\prod\limits_{j\in S}|u_j|\le|h_m|\mathrm{C}_m^i\prod\limits_{i=1}^m|u_j|\le\mathrm{C}_m^iM(h)$ , 故有 $\lVert h\rVert_2\le\lVert h\rVert_1=\sum\limits_{i=0}^m|h_i|\le 2^mM(h)\le\left|\frac{h_m}{f_n}\right|2^mM(f)\le\left|\frac{h_m}{f_n}\right|2^m\lVert f\rVert_2.$ 证毕. □

定理13(Mignotte界) 设 $f,g,h\in\mathbb{Z}[x]$ 且 $\deg f=n\ge 1$ , $\deg g=m$ , $\deg h=k$ , $gh|f$ ,则：

$\lVert g\rVert_{\infty}\lVert h\rVert_{\infty}\le\lVert g\rVert_2\lVert h\rVert_2\le\lVert g\rVert_1\lVert h\rVert_1\le 2^{m+k}\lVert f\rVert_2\le (n+1)^{1/2}2^{m+k}\lVert f\rVert_{\infty}$ ,
$\lVert h\rVert_{\infty}\le\lVert h\rVert_2\le 2^k\lVert f\rVert_2\le 2^n\lVert f\rVert_1$ ,
$\lVert h\rVert_{\infty}\le\lVert h\rVert_2\le (n+1)^{1/2}2^k\lVert f\rVert_{\infty}$ .

证明由引理4,我们有 $\lVert g\rVert_1\lVert h\rVert_1\le 2^{m+k}M(g)M(h)\le 2^{m+k}M(f)\le 2^{m+k}\lVert f\rVert_2,$ 此即第一式。再令 $g=1$ 可得后两式。 □

大素数模公因子算法(Big Prime Modular Gcd Algorithm)

如不作特殊说明，本小节中 $\mathbb{Z}_p$ 域取代表元 $\mathbb{Z}_p=\left\{i\in\mathbb{Z}|\displaystyle -\frac{p}{2}<i<\frac{p}{2}\right\}$ .若记 $f$ 的首项系数为 $\plc{f}$ ,则定义其首一多项式为 $\mathrm{monic}(f)=\frac{f}{\plc{f}}.$

算法4(大素数模公因子算法)

输入： $\mathbb{Z}[x]$ 中本原式 $f$ , $g$ ,且 $\deg f=n\ge\deg g\ge 1$ , $\|f\|_{\infty}\le A$ , $\|g\|_{\infty}\le A$ ,

输出： $h=\gcd (f,g)\in\mathbb{Z}[x]$ .

赋值 $b=\gcd (\plc{f},\plc{g})$ , $B=(n+1)^{1/2}2^nAb$ ,
任取素数 $p\in(2B,4B]$ ,
$f_p=f \bmod{p}$ , $g_p=g \bmod{p}$ ,
$v_p=\mathrm{monic}(\gcd (f_p,g_p)\in\mathbb{Z}_p[x])$ ,
计算 $w,f^*,g^*\in\mathbb{Z}_p[x]$ 使得 $w\equiv bv_p\pmod{p},\quad f^*w\equiv bf\pmod{p},\quad g^*w\equiv bg\pmod{p},$
若 $\|f^*\|_1\|w\|_1\le B$ 且 $\|g^*\|_1\|w\|_1\le B$ 则继续下步，否则跳回第2步,
输出 $\mathrm{pp}(w)$ .

注7 在 $(2B,4B]$ 任取素数是因为在数论中有结论 $n$ 和 $2n$ 中必有一个素数.

设 $h=\gcd(f,g)\in\mathbb{Z}[x]$ ,且 $\plc{h}>0$ ,则 $r=\mathrm{res}(f/h,g/h)$ 是一非零常数，且满足 $|r|\le (n+1)^nA^{2n}$ .此由Hadamard不等式 $|\mathrm{res}(f,g)|\le\|f\|_2^m\|g\|_2^n\le (n+1)^{m/2+n/2}\|f\|_{\infty}^m\|g\|_{\infty}^n$ 可知,见[2].

下面的定理保证了算法4中判定条件的正确性.

定理14 算法4中给定的条件 $\|f^*\|_1\|w\|_1\le B\wedge\|g^*\|_1\|w\|_1\le B$ 等价于 $p\not |r$ ,此时输出正确的最大公因子。

证明若条件满足，则 $\|f^*w\|_{\infty}\le\|f^*w\|_1\le\|f^*\|_1\|w\|_1\le B<p/2.$ 同理 $\|bf\|_{\infty}<p/2$ ,由于 $f^*w\equiv bf\pmod{p}$ ,则 $f^*w=bf$ ,同样地，我们也可证明 $g^*w=bg$ .

于是 $\deg w=\deg\gcd(bf,bg)\Rightarrow \mathrm{pp}(w)=\gcd(f,g)$ .

另外，若 $\mathrm{pp}(w)=\gcd(f,g)$ ,则由定理13可推出算法中满足的条件。 □

事实上，我们对算法4中的条件稍加改变，仍然可行：

算法5(大素数模公因子算法) 可将算法4第6步中条件改为 $\mathrm{pp}(w_p)|f\wedge \mathrm{pp}(w_p)|g$ ,第5步只计算 $w$ 。

证明(算法有效性) 首先， $v_p|\gcd(f,g)$ ,其次，由 $\gcd(f,g)|f$ 知 $\gcd(f,g)=gcd(f,g)_p|f_p$ ,同样地， $\gcd(f,g)|g_p$ .

于是, $\gcd(f,g)|\gcd(f_p,g_p)=v_p$ ,因而 $v_p=gcd(f,g)$ . □

算法中是随机从区间 $(2B,+\infty)$ 中选取一个素数，这种随机性是否保证我们能较快地得到正确的结果呢？下面的定理作出了回答。

定理15 使得算法5条件满足的素数 $p$ 是素数集中仅除了有限个素数后的集合。

证明设 $h=\mathrm{monic}(\gcd(f,g)),h_p=h\bmod p$ .

只需证若 $p$ 不同时整除 $\plc{f}$ , $\plc{g}$ ,且 $p\not |\mathrm{res}(f/h,g/h)$ ,则 $h=h_p=v_p$ .

首先 $h_p|v_p$ ,若 $\deg v_p=\deg h_p=0$ ,则由首一性知 $v_p=h_p$ ,否则 $\deg v_p\ge 1$ ,此时由 $p\not |\gcd(\plc{f},\plc{g})$ 可得 $h_p\neq 0$ .而存在 $s,t$ 使 $\begin{align*} sf/h+tg/h&=\mathrm{res}(f/h,g/h)\\ &\Rightarrow sf+tg=\mathrm{res}(f/h,g/h)h\\ &\Rightarrow s_pf_p+t_pg_p=\mathrm{res}(f/h,g/h)_ph_p\\ &\Rightarrow v_p|h_p, \end{align*}$ 故仍有 $h_p=v_p$ . □

大素数模方法有效限制了系数膨胀，使得大整数计算负担减轻。算法中用到 $\mathbb{Z}_p$ 中Euclid算法，若再用上域上的快速Euclid算法，可提高效率。但是大素数算法中毕竟要用到大素数的模算术，如果能在较小的素数域中运算自然最好。中国剩余定理为我们提供了一种小素数模方法的可能性。

小素数模公因子算法(Small Prime Modular Gcd Algorithm)

下面仅给出小素数模方法的两种实现。其中算法6参考[2],算法7参考[3],两者的思想基本上是一样的.其中在两个算法中任取素数时都加上了限制 $p<2k\ln k$ ,此参看[2]生成素数的有关章节.从算法的实现细节上来说,第二个算法比第一个算法略优,其能减少很多不必要的计算.

算法6(小素数模公因子算法)

输入： $\mathbb{Z}[x]$ 上本原多项式 $f$ , $g$ ,且 $\deg f=n\ge\deg g\ge 1$ , $\|f\|_{\infty}\le A$ , $\|g\|_{\infty}\le A$ ,

输出： $h=\gcd(f,g)\in\mathbb{Z}[x]$ .

赋值 $b=\gcd(\plc{f},\plc{g})$ , $k=\lceil 2\log_2((n+1)^nbA^{2n})\rceil$ , $B=(n+1)^{1/2}2^nAb$ , $l=\lceil\log_2(2B+1)\rceil$ ,
任取含 $2l$ 个不同的素数的集合 $S$ ,且 $\forall p\in S,p<2k\ln k$ ,
$S=\{p\in S|p\not |b\}$ ,
$\forall p\in S$ , $v_p=\mathrm{monic}(\gcd(f_p,g_p))$ ,
$e=\min\{\deg v_p|p\in S\}$ , $S=\{p\in S|\deg v_p=e\}$ ,
若 $|S|>l$ 则去掉 $S$ 中 $(|S|-l)$ 个元素,只保留 $l$ 个,否则转到第2步,
用中国剩余定理计算 $w$ , $f^*$ , $g^*\in\mathbb{Z}[x]$ 使得 $\|w\|_{\infty},\|f^*\|_{\infty},\|g^*\|_{\infty}\le\left(\prod\limits_{p\in S}p\right)/2,$ 且 $\forall p\in S$ 有 $w\equiv bv_p\pmod{p},\quad f^*w\equiv bf\pmod{p},\quad g^*w\equiv bg\pmod{p},$
若 $\|f^*\|_1\|w\|_1\le B$ 且 $\|g^*\|_1\|w\|_1\le B$ 则继续下一步，否则转到第2步,
输出 $\mathrm{pp}(w)$ .

注8 $l$ 的选取使得 $2^l>2B$ ,因而可见 $S$ 中 $l$ 个元素相乘之积必大于 $2B$ .

算法7(小素数模公因子算法) 输入： $\mathbb{Z}[x]$ 中本原多项式 $f$ , $g$ ,且 $\deg f=n\ge\deg g\ge 1$ , $\|f\|_{\infty}\le A$ , $\|f\|_{\infty}\le A$ ,

输出： $h=\gcd(f,g)\in\mathbb{z}[x]$ .

$b=\gcd(\plc{f},\plc{g})$ , $B=(n+1)^{1/2}2^nAb$ , $k=\lceil 2\log_2((n+1)^nbA^{2n})\rceil$ ,
任取素数 $p>b$ (实际上 $p\not |b$ 即可),且 $p<2k\ln k$ ,
$v_p=\gcd(f_p,g_p)\in\mathbb{Z}_p[x]$ ,
若 $\deg v_p=0$ 则输出1,
$p_1=p$ , $v_1=v_p$ ,
若 $p_1\le 2B$ ，则执行下一步，否则跳转第12步,
再取素数 $p>b$ (or $p\not |b$ ),且 $p<2k\ln k$ , $p\not|p_1$ ,令 $v_p=\gcd(f_p,g_p)\in\mathbb{Z}_p[x]$ ,
若 $\deg v_p=0$ 则输出1,
若 $\deg v_p<\deg v_1$ ,则 $p_1=p$ , $v_1=v_p$ ,并跳至第6步,
若 $\deg v_p=\deg v_1$ 则由中国剩余定理计算 $V$ 使得 $V\equiv v_1\pmod{p_1},\quad V\equiv v_p\pmod{p},$ 并赋值 $p_1=p_1p$ , $v_1=V$ ,
转回第6步,
若 $v_1|f$ 且 $v_1|g$ 则继续，否则转回第2步,
输出 $\mathrm{pp}(v_1)$ .

多项式组的概率算法

下面引进在一元多项式GCD算法中又一个概率性的算法。对于多项式组来说，我们当然可以一步一步求每两个多项式的最大公因子得到整个多项式组的最大公因子，然而用下面的概率算法虽然得到的是可能解，效率却更高。

引理5 设 $R$ 为UFD， $n\in\mathbb{N}$ , $S\subset R$ 为有限集且令 $s=\#S$ , $r\in R[x_1,\ldots,x_n]$ 次数不超过 $d$ ,那么

若 $r$ 非零，则 $r$ 在 $S^n$ 中最多有 $ds^{n-1}$ 个零点.
若 $s>d$ 且 $r$ 在 $S^n$ 上取值为零，则 $r=0$ .

证明我们分条证明如下:

$n=1$ 情形显然。将 $r$ 写成 $x_n$ 的多项式 $r=\sum_{0\le i\le k}r_ix_n^i$ ，其中 $r_i\in R[x_1,\ldots,x_{n-1}]$ 且 $r_k\neq 0$ ,由于 $\deg r_k\le d-k$ ，则由归纳假设， $r_k$ 在 $S^{n-1}$ 中至多有 $(d-k)s^{n-2}$ 个零点，于是 $r$ 和 $r_k$ 至多在 $S^n$ 中有 $(d-k)s^{n-1}$ 个零点。并且 $\forall a\in S^{n-1}(r_k(a)\neq 0)$ ， $r_a=\sum_{0\le i\le k}r_i(a)x_n^i\in R[x_n]$ 至多有 $k$ 个零点，因此零点数目上限可估为： $(d-k)s^{n-1}+ks^{n-1}=ds^{n-1}.$
由1显然得到.

□

若从 $S^n$ 中随机选取 $a$ ,则有 $\mathrm{prob}\{r(a)=0|a\in S^n\}\le\frac{d}{\#S}$ .下面假设我们有一个有限集 $S\subset F$ 和一个 $S$ 上随机数发生器，则有下面的：

算法8(多项式组最大公因子的概率算法)

输入： $f_1,\ldots,f_n\in F[x]$ ， $F$ 是域,

输出：首一多项式 $h$ ，且 $h=\gcd(f_1,\ldots,f_n)$ 可能正确.

任取 $a_3,\ldots,a_n\in S$ ,
令 $g=f_2+\sum_{3\le i\le n}a_if_i$ ,
输出 $\gcd(f_1,g)$ .

用快速Euclid算法替换其中计算，还可提高效率。

定理16 设 $h^*=\gcd(f_1,\ldots,f_n)$ ，则 $h^*|h$ ，且 $\mathrm{prob}\{h\neq h^*\}\le d/\#S$ .

证明 $h^*|h$ 显然。将 $f_i$ 除以 $h^*$ ，这样我们可以假设整个函数组最大公因子为1，设 $f_1\neq 0$ ，令 $A_3,\ldots,A_n$ 为 $F[x]$ 上新的未定元，令 $R=F[A_3,\ldots,A_n]$ ,再令 $K=F(A_3,\ldots,A_n)$ 为 $R$ 的商域(field of fractions)，命 $G=f_2+\sum_{3\le i\le n}A_if_i\in R[x]$ , $r=\mathrm{res}_x(f_1,G)\in R$ ，则 $r$ 是关于 $A_3,\ldots,A_n$ 的次数不超过 $d$ 的多项式。令 $I=\idea{A_3-a_3,\ldots,A_n-a_n}$ ,有 $R/I\cong F$ ,由引理2,有 $\overline{r}=r(a_3,\ldots,a_n)\neq 0\Leftrightarrow\mathrm{res}_x(f_1,g)\neq 0\Leftrightarrow\gcd(f_1,g)=1,$ 设 $u=\gcd(f_1,G)\in R[x]$ ，由于 $u|f_1$ ，则它的系数都在 $F$ 关于 $f_1$ 的分裂域 $E$ (the splitting field of $f_1$ over F)中，但是 $E[x]\bigcap K[x]=F[x]$ ,因此 $u\in F[x]$ .于是由 $u|G$ 推知 $u|f_1,\ldots,f_n$ ，又由于 $\gcd(f_1,\ldots,f_n)=1$ ,则 $u\in F$ ，因此 $\gcd(f_1,G)$ 为一常数， $r$ 是 $R$ 中一非零元，再由引理5可得定理中对于概率的估计。 □

实际过程中，可以取 $f_1$ 为最小次数的多项式，以使错误概率降低，并且在算法结束后检验 $h$ 是否为所求的最大公因子，若不是，则重新选取随机数计算，直至输出正确结果。

参考文献

[1]聂灵沼，丁石孙, 代数学引论, 高等教育出版社, 北京, 2000.

[2]Joachim von zur Gathen and Jürgen Gerhard, Modern Computer Algebra, Cambridge University Press, 2002.

[3]张树功，雷娜，刘停战, 计算机代数基础---代数与符号计算的基本原理, 科学出版社, 2005.