整系数多项式因子分解

问题的引入
约化基算法
约化基算法的一些细节说明

事实上我们可以讨论UFD及其分式域上的多项式，但下面我们仅限于讨论 $\mathbb{Z}$ 和 $\mathbb{Q}$ 上的多项式。由相关的高等代数学的知识，我们知道对于 $\mathbb{Z}[x]$ 上的多项式 $f$ ，其在 $\mathbb{Q}[x]$ 中的不可约因子分解可对应于在 $\mathbb{Z}[x]$ 中的不可约因子分解，即若 $f=f_1f_2\cdots f_r(f_i\in\mathbb{Q}[x]),$ 则有 $f=f_1'f_2'\cdots f_r'(f_i'\in\mathbb{Z}[x]).$ 于是 $\mathbb{Z}[x]$ 上任一多项式 $f$ 的因子分解对应于 $\mathbb{Z}$ 上的因子分解和 $\mathbb{Z}[x]$ 上本原多项式的因子分解。前者在素数理论中讨论，这里我们只讨论后者。

很自然的，由前面的最大公因子模方法我们可以想到用模方法来求解因子分解问题。首先我们可以利用上一章中的无平方因子分解的方法得到 $\mathbb{Z}[x]$ 上的无平方因子本原多项式 $f$ ,这时，我们会遇到如下一些问题：

素数 $p$ 的选取要足够大，以使我们能从 $f \bmod p$ 得到 $f$ ,这一点我们可由模公因子算法中介绍的Mignotte界理论得到。
虽然 $f$ 已是无平方因子，但 $f \bmod p$ 却不一定是无平方因子的。如多项式 $f=x^2+5x+4$ 无平方因子，但 $f \bmod 3=x^2+2x+1=(x+1)^2$ .那么在随机选取素数 $p$ 的时候如何使得 $f \bmod p$ 也是无平方因子呢？这一点在结式理论和后文中回答.
当我们在 $\mathbb{Z}_p[x]$ 中将多项式分解后，如何将 $f \bmod p$ 的分解对应到 $f$ 的分解。最简单的方法是尝试每一种可能的因子组合。因为若 $f$ 有不可约分解 $f=f_1f_2\cdots f_r$ ,则 $\overline{f}=\overline{f_1}\cdots\overline{f_r}$ ,但 $\overline{f_i}$ 不一定不可约。当然，用这种尝试的方法有时效率很低，因此后面还要介绍一种格中短向量(short vectors in lattices)方法。

综上，我们首先要进入 $\mathbb{Z}_p[x]$ 中求得因子分解，这一步我们可以利用“大素数”方法和“小素数”方法，只是这里的小素数不再是各不相同的素数，而是素数幂。第二步是由 $\mathbb{Z}_p[x]$ 返回 $\mathbb{Z}[x]$ 中，求得最终结果，可以用尝试因子组合的方法和格中短向量方法.

大素数模方法和因子组合(Factor Combination)算法

定义1 对于 $F$ 上多项式 $f$ ,定义其判别式为 $\mathrm{disc}(f)=\mathrm{res}(f,f')$ .

由推论1知， $\overline{f}=f\bmod p$ 是无平方因子的当且仅当 $\mathrm{disc}(\overline{f})\neq 0$ .

引理1 $'$ 表示形式微商，则有 $\overline{f'}=\overline{f}'$ .

定理1 令 $f\in\mathbb{Z}[x]$ 是一非零无平方因子多项式, $p\in\mathbb{N}$ 是一个素数且 $p\not |\mathrm{lc}(f)$ ,则 $\overline{f}$ 是无平方因子的当且仅当 $p\not |\mathrm{disc}(f)$ .

证明 $\overline{f}$ 无平方因子 $\Leftrightarrow\mathrm{disc}(\overline{f})\neq 0\Leftrightarrow\mathrm{res}(\overline{f},\overline{f}')\neq 0$ ,再由上面引理知: $\mathrm{res}(\overline{f},\overline{f}')\neq 0\Leftrightarrow\mathrm{res}(\overline{f},\overline{f'})\neq 0.$

又 $p\not |\mathrm{lc}(f)$ ,则由引理2知 $\mathrm{res}(\overline{f},\overline{f'})\neq 0\Leftrightarrow\overline{\mathrm{res}(f,f')}\neq 0\Leftrightarrow p\not |\mathrm{disc}(f).$

证毕。 □

由于 $\mathrm{lc}(f)|\mathrm{res}(f,f')$ ,则我们有下面的：

推论1 $f$ 是 $\mathbb{Z}[x]$ 上非零无平方因子多项式，则 $\overline{f}$ 无平方因子当且仅当 $p\not |\mathrm{disc}(f)=\mathrm{res}(f,f')\in\mathbb{Z}\setminus \{0\}$ .

假设有 $\mathbb{Z}[x]$ 上本原多项式 $f$ 的分解 $f=f_1f_2\cdots f_k$ ,且在模 $p$ 下有： $\overline{f}=\overline{f_1}\overline{f_2}\cdots\overline{f_k}=\overline{\mathrm{lc}(f)}g_1g_2\cdots g_r,$ 其中 $g_i$ 为 $\field{p}[x]$ 上首一不可约多项式.若 $p/2$ 比Mignotte界 $(n+1)^{1/2}2^n|\mathrm{lc}(f)|\cdot\|f\|_{\infty}$ 小,则有下面的等式： $\frac{\mathrm{lc}(f)}{\mathrm{lc}(f_1)}f_1=\mathrm{lc}(f)\prod_{i\in S}g_i\in\mathrm{Z}[x],$ 该式原先在 $\mathrm{Z}_p[x]$ 上就已成立了.其中指标集 $S$ 为 $S=\{i\in\{1,\ldots,r\}|g_i|\overline{f_1}\}$ .

算法1(整系数多项式因子分解1:大素数和因子组合方法)

输入：无平方因子 $n$ 次本原多项式 $f\in\mathbb{Z}[x]$ ，其中 $\mathrm{lc}(f)>0$ 且 $\|f\|_{\infty}=A$ ,

输出： $f$ 在 $\mathbb{Z}[x]$ 上的不可约因子 $\{f_1,\ldots,f_k\}$ .

若 $n=1$ 则输出 $f$ ,否则 $b=\mathrm{lc}(f),B=(n+1)^{1/2}2^nAb$ ,
随机任取一个奇素数 $p\in(2B,4B)$ ,直至 $\gcd(\overline{f},\overline{f}')=1\in\field{p}[x]$ ,即满足上面推论条件,
利用有限域上因子分解算法求出 $g_1,\ldots,g_r\in\mathbb{Z}[x]$ ,其无穷范数均比 $p/2$ 要小，且在 $\field{p}$ 上不可约，于是 $f\equiv bg_1\cdots g_r\pmod{p}$ ,
$T=\{1,\ldots,r\}$ , $s=1$ , $G=\emptyset$ , $f^*=f$ ,
当 $2s\le\#T$ 时循环执行下面4步，否则转第10步,
枚举 $T$ 的所有 $s$ 元子集 $S$ ,并做下两步7、8循环：
计算 $g^*$ , $h^*\in\mathbb{Z}[x]$ 使得其无穷范数比 $p/2$ 要小并且 $g^*\equiv b\prod_{i\in S}g_i\pmod{p}$ , $h^*\equiv b\prod_{i\in T\setminus S}g_i\pmod{p}$ ,
若 $\|g^*\|_1\|h^*\|_1\le B$ 则 $T=T\setminus S$ , $G=G\bigcup\{\mathrm{pp}(g^*)\}$ , $f^*=\mathrm{pp}(h^*)$ , $b=\mathrm{lc}(f^*)$ ,跳出6、7、8循环并转第5步,
$s=s+1$ ,
输出 $G\bigcup\{f^*\}$ .

证明(算法有效性) 由第2步 $p>B\Rightarrow p\not|b$ 我们已经知道 $\overline{f}$ 是无平方因子的。在第8步中，若条件真则有 $g^*h^*=bf^*$ ，因为由 $g^*h^*\equiv bf^*\pmod{p}$ 和 $\|g^*h^*\|_{\infty}\le\|g^*h^*\|_1\le\|g^*\|_1\|h^*\|_1\le B<p/2$ 知等式是成立的。记 $f$ 的因子 $u\in\mathbb{Z}[x]$ ,其在 $\mathbb{Z}_p[x]$ 中不可约因子个数 $\mu(u)$ .现在我们要归纳证明在每次到第5步时，有下面命题成立：

$f^*\equiv b\prod_{i\in T}g_i\pmod{p},\quad b=\mathrm{lc}(f^*),\quad f=f^*\prod_{g\in G}g$ ,
$G$ 中多项式均不可约,
$f^*$ 本原且它的任何一个不可约因子 $u\in\mathrm{Z}[x]$ 有 $\mu(u)\ge s$ .

初始时命题显然成立，假设命题在每次循环进行到第7步前均是成立的，此时经过第7步后当第8步的条件成立时，各量均要发生变化，根据前面的分析则有 $g^*h^*=bf^*$ ,于是 $\mathrm{pp}(g^*)$ 是 $\mathrm{pp}(bf^*)=f^*$ 的因子。由于 $\mu(g^*)=s$ 且对任何 $f^*$ 的不可约因子 $u$ 有 $\mu(u)\ge s$ ,则 $\mathrm{pp}(g^*)$ 是 $f^*$ 的不可约因子.当 $f^*$ 有一个不可约因子 $g$ 满足 $\mu(g)=s$ 时，当循环到s时必然能将此因子选出，这一点可以构造来证明，即取指标集 $S$ 为 $g$ 在 $\field{p}[x]$ 中不可约因子的编号.

最后一步是证明在第5步时，若 $2s>\#T$ ，则 $f^*$ 是不可约的.令 $g\in\mathbb{Z}[x]$ 是 $f^*$ 的一个不可约因子且 $h=f^*/g$ 非平凡,于是 $s\le\mu(g),\mu(h)\le\#T$ .但是 $\mu(g)+\mu(h)=\#T$ ，且 $s>\#T/2$ ，则 $h$ 必为常数， $f^*$ 必不可约. □

例1 考虑 $f=4x^4+13x^3+28x^2+27x+18$ 在 $\mathbb{Z}[x]$ 上的分解. ◇

解 $f$ 是本原的,且 $f'=16x^3+39x^2+56x+27$ , $\mathrm{disc}(f)=1656288$ ,于是 $f$ 无平方因子.此时 $n=4$ , $A=28$ , $b=\mathrm{lc}(f)=4$ ,则 $B=(n+1)^{1/2}2^nAb=1792\sqrt{5}=4007.03$ ,取素数 $p=8017>2B$ 且 $p\not|\mathrm{disc}(f)$ ,此时可以得到 $\mathbb{Z}_{8017}$ 上的分解： $f\equiv 4(x-955)(x+957)(x^2-2003x-4007)\pmod{p}.$

首先 $s=1$ ,若取 $S=\{1\}$ ,则 $g^*=4(x-955)=4x-3820,$ $h^*=4(x+957)(x^2-2003x-4007)=4x^3+3833x^2-3226x-2275,$ $\|g^*\|_1\|h^*\|_1=(4+3820)(4+2833+3226+2275)>B,$ 同样的取 $S=\{2\}$ 时也可验证是不可以的。若取 $S=\{3\}$ ,则 $g^*=4(x^2-2003x-4007)=4x^2+5x+6,$ $h^*=4(x-955)(x+957)=4x^2+8x+12,$ 此时 $\|g^*\|_1\|h^*\|_1=15*24=360<B$ ,则 $G=\{4x^2+5x+6\}$ , $f^*=\mathrm{pp}(h^*)=x^2+2x+3$ , $b=\mathrm{lc}(f^*)=1$ , $T=\{1,2\}$ ,下一步 $s=2$ ,循环条件不满足，则 $G=G\bigcup\{f^*\}=\{x^2+2x+3,4x^2+5x+6\}$ .

对于一般的多项式,我们可以如下分解.当然,在算法第4步分解无平方因子多项式时,也可以调用后面几节将要介绍的分解算法.

算法2(整系数多项式的因子分解2)

输入： $f\in\mathbb{Z}[x]$ ， $\deg f=n>1$ 且 $\|f\|_{\infty}=A$ ,

输出：常数 $c\in\mathbb{Z}$ 和序对集 $\{(f_1,e_1),\ldots,(f_k,e_k)\}$ ,其中 $f_i\in\mathbb{Z}[x]$ 均是不可约两两互素的多项式, $e_i\in\mathbb{N}$ ,且 $f=c\prod_{i=1}^{k}f_i^{e_i}$ .

$c=\mathrm{cont}(f)$ , $g=\mathrm{pp}(f)$ ,若 $\mathrm{lc}(f)<0$ 则 $c=-c$ , $g=-g$ ,
调用算法9得到分解 $g=\prod_{1\le i\le s}g_i^i$ ,且 $\mathrm{lc}(g_i)>0$ , $g_s$ 非平凡,
$G=\emptyset$ ,
对 $1\le i\le s$ 循环,调用上面算法1得到 $g_i$ 的所有不可约因子 $h_1,\ldots,h_t\in\mathbb{Z}[x]$ , $G=G\bigcup\{(h_1,i),\ldots,(h_t,i)\}$ ,
输出 $c$ 和 $G$ .

Hensel提升(lifting)理论

以下我们全在整数环这个特殊的UFD中讨论,有些算法和命题在将 $\mathbb{Z}$ 换为其它的UFD,如 $\mathbb{Z}[x]$ 也是正确的。

当我们已知一个分解 $f\equiv gh\pmod{p}$ ( $g$ , $h$ 互素)时，最简单的问题是获得分解 $f\equiv g^*h^*\pmod{p^2}$ ,即将其“提升”。由于 $p$ 是素数，则存在 $s$ , $t\in\mathbb{Z}[x]$ 使得 $sg+th\equiv 1\pmod{p}$ ,如果我们取： $e=f-gh,\quad g^*=g+te,\quad h^*=h+se,$ 则有 $\begin{align*} f-g^*h^*&=f-(g+te)(h+se)=f-gh-(sg+th)e-ste^2\notag \\ &=(1-sg-th)e-ste^2\equiv 0\pmod{p^2},\notag \end{align*}$ 这样可以达到我们的要求。

引理2 在 $\mathbb{Z}[x]$ 中,我们有如下结论:

设 $f$ , $g\in\mathbb{Z}[x]$ ,其中 $g$ 非零且首一,则存在唯一的多项式 $q$ , $r\in\mathbb{Z}[x]$ 使得 $f=qg+r$ 且 $\deg r<\deg g$ .
$f$ , $g$ , $q$ , $r$ 同上，若对于某个整数 $m$ 有 $f\equiv 0\pmod{m}$ ,则 $q\equiv r\equiv 0\pmod{m}$ .

证明第一条基本同Euclid环中的证明方法,只要注意到 $g$ 是首一的即可。对于第二条，由 $f\equiv 0\pmod{m}$ 知必有 $\mathbb{Z}[x]$ 中的多项式 $f^*$ 使得 $f=mf^*$ ，于是必存在唯一的 $q^*,r^*$ 使得 $f^*=q^*g+r^*,\quad \deg r^*<\deg q^*,$ 此时有 $f=mf^*=(mq^*)g+(mr^*)$ ,由唯一性得 $q=mq^*$ , $r=mr^*$ . □

我们可以给出如下的单步Hensel提升(Hensel Step)算法.

算法3(单步Hensel提升)

输入：整数 $m\in\mathbb{Z}$ ,多项式 $f,g,h,s,t\in\mathbb{Z}[x]$ 使得 $f\equiv gh\pmod{m},\quad sg+th\equiv 1\pmod{m},$ $h$ 首一，且 $\deg f=n=\deg g+\deg h$ , $\deg s<\deg h$ , $\deg t<\deg g$ .

输出：多项式 $g^*,h^*,s^*,t^*\in\mathbb{Z}[x]$ 使得 $f\equiv g^*h^*\pmod{m^2},\quad s^*g^*+t^*h^*\equiv 1\pmod{m^2},$ $h^*$ 首一， $g^*\equiv g\pmod{m}$ , $h^*\equiv h\pmod{m}$ , $s^*\equiv s\pmod{m}$ , $t^*\equiv t\pmod{m}$ , $\deg g^*=\deg g$ , $\deg h^*=\deg h$ , $\deg s^*<\deg h^*$ , $\deg t^*<\deg g^*$ .

计算 $e,q,r,g^*,h^*\in\mathbb{Z}[x]$ 使得 $\deg r<\deg h$ 且 $\begin{align*} e&\equiv f-gh\pmod{m^2},\qquad &se&\equiv qh+r\pmod{m^2},\notag\\ g^*&\equiv g+te+qg\pmod{m^2}, &h^* &\equiv h+r\pmod{m^2}, \notag \end{align*}$
计算 $b,c,d,s^*,t^*\in\mathbb{Z}[x]$ 使得 $\deg d<\deg h^*$ 且 $\begin{align*} b&\equiv sg^*+th^*-1\pmod{m^2},\qquad &sb&\equiv ch^*+d\pmod{m^2},\notag\\ s^*&\equiv s-d\pmod{m^2},&t^*&\equiv t-tb-cg^*\pmod{m^2},\notag \end{align*}$
输出 $g^*,h^*,s^*,t^*$ .

证明(算法有效性) 我们逐项验证各项输出的要求.首先， $f\equiv g^*h^*\pmod{m^2}$ , $\begin{align*} f-g^*h^*&\equiv f-(g+te+qg)(h+r)\equiv f-(g+te+qg)(h+se-qh)\notag\\ &\equiv (f-gh)-(sg+th)e-ste^2+q^2gh+(th-sg)eq\notag\\ &\equiv (1-sg-th)e-ste^2+q^2gh+(th-sg)eq\equiv 0\pmod{m^2},\notag \end{align*}$ 这是因为根据前面的引理我们由 $se\equiv 0\pmod{m}$ 得到 $q\equiv r\equiv 0\pmod{m}$ .

由 $\deg r<\deg h$ 知 $h^*$ 也是首一的,且 $g^*-g\equiv te+qg\equiv 0\pmod{m},$ $h^*-h\equiv r\equiv 0\pmod{m},$ 由 $h^*\equiv h+r\pmod{m^2}$ 也可得到 $\deg h^*=\deg h$ ,于是 $\deg g^*=\deg f-\deg h^*=\deg f-\deg h=\deg g$ .

其次, $s^*g^*+t^*h^*\equiv 1\pmod{m}$ , $\begin{align*} s^*g^*+t^*h^*&\equiv (s-d)g^*+(t-tb-cg^*)h^*\notag\\ &\equiv (s-sb+ch^*)g^*+(t-tb-cg^*)h^*\equiv (sg^*+th^*)(1-b)\notag\\ &\equiv (sg^*+th^*)(2-sg^*-th^*)\equiv 1-(sg^*+th^*-1)^2\equiv 1-(sg+th-1)^2\notag\\ &\equiv 1\pmod{m^2},\notag \end{align*}$ 由 $sb\equiv 0\pmod{m}$ 可知 $c\equiv d\equiv 0\pmod{m}$ ,于是 $s^*-s\equiv d\equiv 0\pmod{m},$ $t^*-t\equiv tb+cg^*\equiv 0\pmod{m},$ 而 $\deg d<\deg h^*$ ,于是 $\deg s^*\le\deg(s-d)<\deg h^*$ ,由 $s^*g^*+t^*h^*\equiv 1\pmod{m^2}$ 知 $\deg t^*<\deg g^*$ .所有结论证毕. □

既然本节开始提出的方法已经能够解决问题,为什么还要引入上面的算法呢？我们通过下面一个例子来说明问题：

例2 考虑 $f=x^4-1$ , $m=5$ , $h=x-2$ , $g=x^3+2x^2-x-2$ , $s=-2$ , $t=2x^2-2x-1$ 的情况. ◇

解由本节开始的方法处理,有 $e=f-gh=5x^2-5,$ $g^*=g+te=10x^4-9x^3-13x^2+9x+3,$ $h^*=h+se=-10x^2+x+8.$ 我们看到, $\deg g^*>\deg g$ , $\deg h^*>\deg h$ ,这种规模的增大无疑对后续的提升造成更多的计算负担,并且次数的提高也不是我们想要的正确的因子分解的结果.因此我们用算法3来进行提升:

$e$ 任取为 $5x^2-5$ ,则对 $se$ 进行 $h$ 的带余除法有： $se=-10x^2+1\equiv (-10x+5)h-5\pmod{25},$ 于是 $q=-10x+5$ , $r=-5$ ,故 $g^*\equiv g+te+qg\equiv x^3+7x^2-x-7\pmod{25},$ $h^*\equiv h+r\equiv x-7\pmod{25},$ $b\equiv sg^*+th^*-1\equiv -5x^2-10x-5,$ $c=10x-10,\quad d=-10,$ $s^*\equiv s-d\equiv 8\pmod{25},$ $t^*\equiv t-tb-cg^*\equiv -8x^2-12x-1.$

正如Hensel单步提升算法所提到的,我们有 $\deg g^*=\deg g$ , $\deg h^*=\deg h$ .

如果我们归纳地利用单步Hensel算法,依次对 $m$ , $m^2$ , $m^4$ , $\cdots$ 使用，则对任何正整数 $l$ ，我们总可找到比其大的 $2$ 的幂次，于是有下面的：

定理2(Hensel引理) 对于给定的正整数 $l$ 以及算法3中输入的条件,我们可以将 $m^2$ 用 $m^l$ 代替，仍然得到满足条件的输出.

定理3(Hensel提升的唯一性) 对于非零整数 $m$ 和正整数 $l$ 以及非零多项式 $g,h,g^*,h^*,s,t\in\mathbb{Z}[x]$ ,其中 $sg+th\equiv 1\pmod{m}$ , $\mathrm{lc}(g)$ 和 $\mathrm{lc}(h)$ 不是 $\mathbb{Z}_m$ 中的零因子, $g$ 和 $g^*$ 有同样的领项和次数，且模 $m$ 同余，对于 $h$ 和 $h^*$ 有相似的条件.此时若 $gh\equiv g^*h^*\pmod{m^l}$ ,则 $g\equiv g^*\pmod{m^l}$ , $h\equiv h^*\pmod{m^l}$ .

证明假设结论不成立,即 $g\not\equiv g^*\pmod{m^l}$ 或 $h\not\equiv h^*\pmod{m^l}$ ,不妨假设前者不成立,于是我们可以找到最大的指标 $i(1\le i<l)$ 使得 $m^i|g-g^*$ 且 $m^i|h-h^*$ ，不妨设 $g^*-g=um^i$ , $h^*-h=vm^i$ 且 $m\not|u$ .则 $0\equiv g^*h^*-gh\equiv g^*(h^*-h)+h(g^*-g)\equiv (g^*v+hu)m^i\pmod{m^l},$ 于是 $m|m^{l-i}|(g^*v+hu)$ ,若 $f$ 将模 $m$ 的象以 $\overline{f}$ 来记，则有 $\overline{sg}+\overline{th}=1,\quad \overline{g^*}=\overline{g},\quad \overline{g^*v}+\overline{hu}=0.$ 因此 $0=\overline{t}(\overline{g^*v}+\overline{hu})=\overline{tgv}+(1-\overline{sg})\overline{u}=(\overline{tv}-\overline{su})\overline{g}+\overline{u},$ 于是 $\overline{g}|\overline{u}$ ,又 $g$ 和 $g^*$ 的领项和次数均相同,我们有 $\deg\overline{u}<\deg\overline{g}$ ,于是由整除性知 $\overline{u}=0$ ,这与 $m\not|u$ 矛盾. □

前面所说的均是二因子的Hensel提升,为了做多因子的情况，我们先给出如下定义：

定义2(因子树(Factor Tree)) 对于 $\mathbb{Z}[x]$ 中的多项式 $f$ ,以及正整数 $m$ (例如我们可以取作素数 $p$ ),设有整数 $a$ 使得 $a\mathrm{lc}(f)\equiv 1\pmod{m}$ ,则 $f$ 模 $m$ 的因子树(factor tree of f modulo m)是指一个二叉树 $\tau$ :其根结点是 $af$ ;每个结点的两个子结点均是该结点在 $\mathbb{Z}_m[x]$ 中的非平凡首一因子;叶结点均为 $\mathbb{Z}_m[x]$ 的不可约因子.

注1 实际我们有模素数的因子分解生成因子树时,需要用扩展Euclid算法算出各个属于同一中间结点的两个子结点的Bezout系数,以便进行下面的多因子Hensel提升算法.一个典型的因子树如下图所示.其中每个结点的括号中显示了其相应的Bezout系数.

模5因子树

当然由模 $m$ 的因子树我们可以由单步Hensel算法得到模 $m^2$ 乃至更高次幂的因子树,只要我们由根结点依次一步步在每个结点做Hensel提升即可.下面给出该算法：

算法4(多因子Hensel提升)

输入：整数 $m$ 和 $n$ 次多项式 $f\in\mathbb{Z}[x]$ , $a_0\in\mathbb{Z}$ 使得 $a_0\mathrm{lc}(f)\equiv 1\pmod{m}$ ,正整数 $l$ ,一个 $f$ 模 $m$ 的因子树 $\tau$ ,共有 $r$ 个叶子.

输出：整数 $a^*$ 使得 $a^*\mathrm{lc}(f)\equiv 1\pmod{m^l}$ 和一个 $f$ 模 $m^l$ 的因子树 $\tau^*$ ,各个新结点 $v^*$ 和原结点 $v$ 满足 $v^*\equiv v\pmod{m}$ .

$d=\lceil\log_2l\rceil$ , $\tau_0=\tau$ ,
对 $j$ 从 $1$ 循环到 $d$ ,执行3～5步,
计算整数 $a_j$ 使得 $a_j\equiv 2a_{j-1}-\mathrm{lc}(f)a_{j-1}^2\pmod{m^{2^j}}$ , $\tau_j=\tau_{j-1}$ ,将 $\tau_j$ 的根结点换为 $a_jf$ ,
从根结点遍历 $\tau_j$ 的结点,对每个非叶结点 $v$ ,执行第5步（由根向叶结点方向进行）,
调用算法3,输入 $m^{2^{j-1}}$ 来提升 $v=g_vh_v$ 和 $s_vg_v+t_vh_v\equiv 1\pmod{m^{2^{j-1}}}$ ,提升到模 $m^{2^{j}}$ ,
输出 $a_d$ , $\tau_d$ .

注2 注意到 $d$ 的选取能够使我将因子树提升到足够高的次数.

注3 我们只需要说明每一步求得的 $a_j$ 确实满足要求.这是因为 $a_j\mathrm{lc}(f)\equiv 2a_{j-1}\mathrm{lc}(f)-\mathrm{lc}^2(f)a_{j-1}^2\equiv 1-(1-a_{j-1}\mathrm{lc}(f))^2\equiv 1\pmod{m^{2^j}}$ .

应用Hensel提升的Zasenhaus算法

有了前面的Hensel提升理论,下面我们就可以利用它取代前面的大素数模算法.

算法5(整系数多项式分解3:素数幂和因子组合算法)

输入：一个无平方因子本原 $n$ 次多项式 $f\in\mathbb{Z}[x]$ , $\mathrm{lc}(f)>0$ 且 $\|f\|_{\infty}=A$ ,

输出： $f$ 的不可约因子 $\{f_1,\ldots,f_k\}\subset\mathbb{Z}[x]$ .

若 $n=1$ 则输出 $f$ ,否则 $b=\mathrm{lc}(f)$ , $B=(n+1)^{1/2}2^nAb$ , $C=(n+1)^{2n}A^{2n-1}$ , $\gamma=\lceil 2\log_2C\rceil$ ,
任意选取素数 $p\le 2\gamma\ln\gamma$ , $\overline{f}=f \bmod p$ ,直到 $p\not|b$ 且 $\gcd(\overline{f},\overline{f}')=1\in\field{p}[x]$ ,然后令 $l=\lceil\log_p(2B+1)\rceil$ ,
调用有限域上因子分解算法计算 $h_1,\ldots,h_r\in\mathbb{Z}[x]$ ,各因子均是首一不可约因子,且无穷范数小于 $p/2$ ,于是 $f\equiv bh_1\cdots h_r\pmod{p}$ ,
$a=b^{-1}\bmod p$ ,利用扩展Euclid算法建立 $f$ 模 $p$ 的因子树,叶结点为 $h_1,\ldots,h_r$ ,再调用算法4计算分解 $f\equiv bg_1\cdots g_r\pmod{p^l}$ ,其中 $g_i\in\mathbb{Z}[x]$ 为首一且无穷范数小于 $p^l/2$ , $g_i\equiv h_i\pmod{p}$ ,
调用因子组合算法并输出.(此处同算法1第4～10步.) $T=\{1,\ldots,r\}$ , $s=1$ , $G=\emptyset$ , $f^*=f$ ,
当 $2s\le\#T$ 时循环执行下面4步，否则转第11步,
枚举 $T$ 的所有 $s$ 元子集 $S$ ,并做下两步8、9循环：
计算 $g^*$ , $h^*\in\mathbb{Z}[x]$ 使得其无穷范数比 $p^l/2$ 要小并且 $g^*\equiv b\prod_{i\in S}g_i\pmod{p^l}$ , $h^*\equiv b\prod_{i\in T\setminus S}g_i\pmod{p^l}$ ,
若 $\|g^*\|_1\|h^*\|_1\le B$ 则 $T=T\setminus S$ , $G=G\bigcup\{\mathrm{pp}(g^*)\}$ , $f^*=\mathrm{pp}(h^*)$ , $b=\mathrm{lc}(f^*)$ ,跳出7、8、9循环并转第6步,
$s=s+1$ ,
输出 $G\bigcup\{f^*\}$ .

注4 步骤2中 $\gamma$ 的引入见[1]18.4节.

证明(算法正确性) 记 $f$ 的因子 $u\in\mathbb{Z}[x]$ ,其在 $\mathbb{Z}_p[x]$ 中不可约因子个数 $\mu(u)$ .现在我们要归纳证明在每次到第6步时，有下面命题成立：

$f^*\equiv b\prod_{i\in T}g_i\pmod{p^l},\quad b=\mathrm{lc}(f^*),\quad f=f^*\prod_{g\in G}g$ ,
$G$ 中多项式均不可约,
$f^*$ 本原且它的任何一个不可约因子 $u\in\mathrm{Z}[x]$ 有 $\mu(u)\ge s$ .

主要证法和算法1的证明一致,我们只需证明当 $f^*$ 有一个不可约因子 $g$ 满足 $\mu(g)=s$ 时，当循环到s时必然能将此因子选出，这一点可以构造来证明，即取指标集 $S$ 为 $g$ 在 $\field{p}[x]$ 中不可约因子的编号.当然这里与前面的证法有所不同,因为 $\mathbb{Z}_{p^l}[x]$ 并不是UFD,要证明唯一性还需要用Hensel提升的唯一性定理.首先可设 $\mathrm{lc}(h)g\equiv b\prod_{i\in S}g_i\pmod{p}$ , $\mathrm{lc}(g)h\equiv b\prod_{i\in T\setminus S}g_i\pmod{p}$ ,再设 $g^*\equiv b\prod_{i\in S}g_i\pmod{p^l}$ , $h^*\equiv b\prod_{i\in T\setminus S}g_i\pmod{p^l}$ .由 $f^*=gh$ 可知 $bf^*=\plc{h}g\plc{g}h,$ 另外 $bf^*\equiv g^*h^*\pmod{p^l},$ 以上两式均是 $bf^*\bmod p$ 的提升,于是 $\mathrm{lc}(h)g\equiv g^*\pmod{p^l}$ 且 $\mathrm{lc}(g)h\equiv h^*\pmod{p^l}$ ,再由所定的Mignotte界和 $l$ 的选择可知9中的条件必然成立. □

例3 仍然考虑例1中 $f=4x^4+13x^3+28x^2+27x+18\in\mathbb{Z}[x]$ 的分解. ◇

解首先, $n=4$ , $A=28$ , $b=4$ , $B=1792\sqrt{5}=4007.03$ , $\gamma=104$ ,而 $2,3|\mathrm{disc}(f)$ ,故取 $p=5$ ,此时 $l=\lceil\log_5(2B+1)\rceil=6$ ,要提升3次.首先利用模 $5$ 因子分解和扩展Euclid算法得到如下模5因子树：

$\begin{equation*} 4f= \begin{cases} s=x,g=x^2-1\begin{cases}s=3,g=x+1\\t=2,h=x-1\end{cases}\\ t=-x+2,h=x^2+2x-2 \end{cases} \end{equation*}$

利用多因子提升算法提升为模25因子树：

$\begin{equation*} 19f=\begin{cases} s=6x,g=x^2-5x-11\begin{cases}s=-2,g=x-9\\t=2,h=x+4\end{cases}\\ t=-6x-8,h=x^2+2x+3 \end{cases} \end{equation*}$ 以此类推有模 $5^4=625$ 因子树： $\begin{equation*} 469f=\begin{cases} s=-69x,g=x^2-155x-311\begin{cases}s=-177,g=x-134\\t=177,h=x-21\end{cases}\\ t=69x-208,h=x^2+2x+3 \end{cases} \end{equation*}$ 模 $5^8=390625$ 因子树： $\begin{equation*} 292969f=\begin{cases} s=86806x,g=x^2-97655x-195311\begin{cases}s=-108927,g=x+82991\\t=108927,h=x-180646\end{cases}\\ t=-86806x-130208,h=x^2+2x+3 \end{cases} \end{equation*}$ 于是我们有 $f\equiv 4(x+82991)(x-180646)(x^2+2x+3)\pmod{5^8}$ .这里我们再对其进行还原时，显然有 $s=1$ 时可得到不可约因子 $(x^2+2x+3)$ ,此时 $f^*=h^*\equiv 4(x+82991)(x-180646)\equiv 4x^2+5x+6\pmod{5^8}$ .于是再一次得到分解 $f=(x^2+2x+3)(4x^2+5x+6)$ .

格中短向量(Short vectors in lattices)理论

问题的引入

通过大素数模方法或Hensel提升方法,我们都可以得到多项式 $f\in\mathbb{Z}[x]$ 在模某个整数 $m$ 后的分解,即 $f\equiv bg_1\cdots g_r\pmod{m}$ .这时候我们用因子组合的算法将它们拼起来还原.但是这种方法的效率有时候不会很高,如Swinnerton-Dyer多项式(见[1]15.3节).于是我们要发展一套更有效的方法,下面几节将要介绍的格中短向量方法是一种多项式时间算法.

由定义13，以下我们取默认的范数 $\|f\|$ 为2-范数,即 $\|f\|_2$ .我们将多项式的系数看作向量，则多项式范数等同于该向量的范数.

引理3 设 $f$ , $g\in\mathbb{Z}[x]$ 分别是 $n$ , $k$ 次多项式, $u\in\mathbb{Z}[x]$ 是一非平凡首一多项式, $m$ 为一正整数,若在 $\mathbb{Z}_m[x]$ 中有 $u|f\pmod{m}$ , $u|g\pmod{m}$ , $\|f\|^k\|g\|^n<m$ .则 $f$ 和 $g$ 有非平凡公因子.

证明假设 $f$ , $g$ 没有非平凡的公因子,则在 $\mathbb{Q}[x]$ 中有 $\gcd(f,g)=1$ ,由结式理论推论4可知存在 $s$ , $t\in\mathbb{Z}[x]$ 使得 $sf+tg\equiv\mathrm{res}(f,g)\pmod{m}$ ,由于 $u$ 在模 $m$ 下能整除 $f$ 和 $g$ ，则 $u|\mathrm{res}(f,g)\bmod m$ .但 $u$ 是非平凡首一多项式,于是必有 $\mathrm{res}(f,g)\equiv 0\pmod{m}$ ,再由阿达马不等式有 $|\mathrm{res}(f,g)|<\|f\|^k\|g\|^n<m$ ,此即说明 $\mathrm{res}(f,g)=0$ ,与 $\gcd(f,g)=1\in\mathbb{Q}[x]$ 矛盾.于是二者在 $\mathbb{Z}[x]$ 中有非平凡公因子. □

由前面我们已得出的分解结果和上面的引理,我们可以设想这样一种分解的想法。首先我们已经有待分解的 $n$ 次多项式 $f\in\mathbb{Z}[x]$ 和 $f$ 在模 $m$ 下的一个因子 $u\in\mathbb{Z}[x]$ ,此时我们需要找到一个较“短”的 $k$ 次多项式 $g\in\mathbb{Z}[x]$ 使得 $\|g\|^n<m\|f\|^{-k}$ ,且 $u|g\bmod m$ ,于是可通过 $\gcd(f,g)$ 得到 $f$ 的一个非平凡因子.为了叙述方便,以后记号 $f$ 既可以表示 $n$ 次多项式,也可以表示 $n+1$ 维系数向量.引入下面的定义：

定义3 设有正整数 $n$ 和向量 $f_1,\ldots,f_n\in\mathbb{R}^n$ ,则 $L=\sum_{1\le i\le n}\mathbb{Z}f_i=\{\sum_{1\le i\le n}r_if_i|r_1,\ldots,r_n\in\mathbb{Z}\}$ 称为格子(lattice)或由 $f_1,\ldots,f_n$ 产生的 $\mathbb{Z}$ -模. $f_1,\ldots,f_n$ 称为 $L$ 的基.而 $L$ 的范数是指： $|L|=|\det(f_1,\ldots,f_n)|\in\mathbb{R}.$ 后面将看到范数的定义是与基的选择无关的.

现在我们考虑寻找一个次数小于 $j$ 的多项式 $g$ ,设 $L\subset\mathbb{Z}^j$ 是由 $u$ 和 $m$ 生成的,即 $L=\{g=qu+rm|q,r\in\mathbb{Z}[x],\deg q<j-d,\deg r<d\}.$ 其中 $d=\deg u$ ,这时我们有下面的定理：

定理4 对于任何一个次数小于 $j$ 的多项式 $g$ , $u|g\bmod m\Leftrightarrow g\in L$ .

证明对于 $\Rightarrow$ 显然,对于 $\Leftarrow$ ,我们有 $g=q^*u+r^*m$ ,再由 $r^*$ 对首一多项式 $u$ 的除法可得 $r^*=q^{**}u+r^{**}$ ([1]中证明此处写作 $q^*$ 对 $u$ 的除法),其中 $\deg r^{**}<\deg u$ .令 $q=q^*+mq^{**}$ , $r=r^{**}$ ,则有 $g=qu+rm$ ,且 $\deg q<j-d$ , $\deg r<d$ ,于是 $g\in L$ . □

现在我们的问题化为在 $L$ 中寻找一种约化的基,以使得基向量长度较短,满足要求.

约化基算法

下面要介绍的约化基算法即是所谓的3-L算法(Lenstra,Lenstra and Lovász).

引理4 令 $N\subset M\subset \mathbb{R}^n$ 为两个 $\mathbb{Z}$ -模，分别由 $g_1,\cdots g_n$ 和 $f_1,\ldots,f_n$ 生成,则 $|M|$ 整除 $|N|$ .

证明由 $N\subset M$ 知 $N$ 的生成元 $g_i$ 均是 $M$ 的生成元 $f_i$ 的线性组合,即存在整系数矩阵 $A$ 使得 $(g_1,\ldots,g_n)=A(f_1,\ldots,f_n)$ ,于是 $|N|=\det A|M|$ , $\deg A\in\mathbb{Z}$ . □

若 $N=M$ ,则有 $\mathbb{Z}$ -模的范数与生成元无关.由Hadamard不等式我们知道 $|M|\le\|f_1\|\cdots\|f_n\|$ .

因为范数与基的选择无关,因而我们想到,如果选取的基越“正交”,那么某种程度上这组基矢的长度越短.因而,向量基的正交化可以启示我们得到一种求约化基（即所谓的短矢量）的方法.

现在我们已知由 $f_1,\ldots,f_n$ 生成的 $\mathbb{Z}$ -模,即一个 $n$ 维格子,若取内积为 $\langle f,g\rangle=f^Tg$ ,由高等代数学(见[2]P281)的内容我们知道可以对它们进行Gram-Schmidt正交化,正交化的过程可以归纳地进行,即令 $f_1^*=f_1$ ,对于 $i\ge 2$ ,有 $f_i^*=f_i-\sum_{1\le j<i}f_j^*\mu_{ji},\text{其中}\mu_{ji}=\frac{\idea{f_i,f_j^*}}{\idea{f_j^*,f_j^*}}.$ 于是存在一个上三角阵 $M=(\mu_{ij})$ ,其对角元为1,使得 $(f_1,\ldots,f_n)=(f_1^*,\ldots,f_n^*)M,$ 其中 $f_i^*$ 张成同样的空间,且两两互相正交.由正交化的几何意义我们可以很明显地看到,每个向量的长度都不大于原向量的长度,即基向量的长度缩短了.但是光作GSO(Gram-Schmidt orthogonalization)是不行的,因为正交化后所得的向量并不一定是原先格子中的向量,这是模和线性空间的不同.但是首先，我们有下面的估计：

引理5 设 $L$ 为由 $(f_1,\ldots,f_n)$ 生成的 $\mathbb{Z}$ -模, $(f_1^*,\ldots,f_n^*)$ 是对其进行GSO所得的基,则对任意非零向量 $f\in L$ ,我们有 $\|f\|\ge\min\{\|f_1^*\|,\ldots,\|f_n^*\|\}.$

证明由GSO过程知道有对角元为1的上三角阵 $M=(\mu_{ij})$ 满足 $(f_1,\ldots,f_n)=(f_1^*,\ldots,f_n^*)M,$ 则 $f_i=\sum_{1\le j\le n}f_j^*\mu_{ji}=\sum_{1\le j\le i}f_j^*\mu_{ji}$ .对于非零向量 $f\in L$ ,存在 $k\le n$ 使得 $f=\sum_{1\le i\le k}\lambda_if_i,\quad \lambda_k\neq 0,\lambda_1\cdots\lambda_k\in\mathbb{Z}.$

于是 $f=\sum_{1\le i\le k}\lambda_if_i=\sum_{1\le i\le k}\lambda_i\sum_{1\le j\le i}f_j^*\mu_{ji}=\lambda_kf_k^*+\sum_{1\le i<k}\gamma_if_i^*$ ,其中 $\gamma_i\in\mathbb{R}$ ,将此式代入 $\|f\|$ 可得： $\begin{align*} \|f\|^2&=(\lambda_kf_k^*+\sum_{1\le i<k}\gamma_if_i^*)(\lambda_kf_k^*+\sum_{1\le i<k}\gamma_if_i^*)\\ &=\lambda_k^2\|f_k^*\|^2+\sum_{1\le i<k}\gamma_i^2\|f_i^*\|^2\ge\lambda_k^2\|f_k^*\|^2\\ &\ge\|f_k^*\|^2\ge\min\{\|f_1^*\|^2,\ldots,\|f_n^*\|^2\}, \end{align*}$ 证毕. □

既然我们用GSO得到的不一定是格的约化基,那么我们可以放宽条件,下面给出一种约化基的定义方式：

定义4 设 $f_1,\ldots,f_n\in\mathbb{R}^n$ 线性无关且 $(f_1^*,\ldots,f_n^*)$ 是其对应的GS正交基.则称 $(f_1,\ldots,f_n)$ 是约化基，如果对于 $1\le i<n$ 有 $\|f_i^*\|^2\le 2\|f_{i+1}^*\|^2$ 且对于 $\mu_{ji}$ 的非零元均有 $|\mu_{ji}|<1/2$ .

定理5 设 $(f_1,\ldots,f_n)$ 是其所生成的格子 $\in\mathbb{R}^n$ 的约化基且 $f\in L\setminus\{0\}$ ,则 $\|f_1\|\le 2^{(n-1)/2}\|f\|$ .

证明由于 $\|f_1\|^2=\|f_1^*\|^2\le 2\|f_2^*\|^2\le 2^2\|f_3^*\|^2\le\cdots\le 2^{n-1}\|f_n^*\|^2$ 可设 $\|f_m^*\|=\min\{\|f_1^*\|,\ldots,\|f_n^*\|\}$ ,则 $2^{n-1}\|f\|^2\ge 2^{n-1}\|f_m^*\|^2\ge 2^{m-1}\|f_m^*\|^2\ge\|f_1^*\|^2=\|f_1\|^2,$ 于是命题得证. □

下面给出生成约化基的算法：

算法6(约化基算法)

输入：线性无关的向量 $f_1,\ldots,f_n\in\mathbb{Z}^n$ ,

输出：由输入向量所生成的 $\mathbb{Z}$ -模的约化基 $(g_1,\ldots,g_n)$ .

将 $g_1,\ldots,g_n$ 初始化为 $f_1,\ldots,f_n$ ,并进行相应的GSO过程,得到约化基 $G^*=(g_1^*,\ldots,g_n^*)$ 和变换矩阵 $M\in\mathbb{Q}^{n\times n}$ 使得 $G=G^*M$ , $i=2$ ,
当 $i\le n$ 时,执行下面3～5步,
让 $j$ 从 $i-1$ 循环到 $1$ ，执行下面4步,
$g_i=g_i-g_j\lceil\mu_{ji}\rfloor$ (此处取最接近 $\mu_{ji}$ 的整数),重新计算GSO得到 $G^*$ , $M$ ,
若 $i>1$ 且 $\|g_{i-1}^*\|^2>2\|g_i^*\|^2$ 则交换 $g_{i-1}$ 和 $g_i$ ,并重新计算GSO得到 $G^*$ , $M$ , $i=i-1$ ,否则 $i=i+1$ ,
输出 $(g_1,\ldots,g_n)$ .

注5 也可以由GSO过程求得变换矩阵 $M$ 使得 $(f_1^*,\ldots,f_n^*)=(f_1,\ldots,f_n)M$ ,再将 $M$ 中元素均取整后代替算法6第4步中的计算.下面举的几个例子用此算法,当然算法6中的矩阵 $M$ 更好计算一些.

例4 记 $a=219914302784468853031851163930189578018051741$ , $b=5^{64}$ ,设 $L$ 由 $(1,a)$ 和 $(0,b)$ 生成,用上面的算法求其约化基. ◇

解编程可得如下约化基： $g_1=(-6999570441183108942993, -13384313532767302775813),$ $g_2=(-32538542807519884274273, 15228795581564048106332),$ 其中 $g_1=-6999570441183108942993(1,a)+2839517743881186811624(0,b).$

我们取 $g^*=g_1$ 作为短矢量,有 $g^*=-6999570441183108942993x-13384313532767302775813.$

如果我们再考虑由 $(1,a,0),(0,1,a),(0,0,b)$ 生成的 $\mathbb{Z}$ -模,则按照算法可得如下约化基： $g_1=(4, 5, 6),$ $g_2=(5989804332598408382848, 487684974564901535567,-4399607033869690201541),$ $g_3=(-3921135160431868252895, 6733001971931690223946,-2996744869655163018019),$ 其中 $\begin{align*} g_1&=4(1,a,0)-879657211137875412127404655720758312072206959(0,1,a)\\ &+356850792566185450269524416969136119168940313(0,0,b), \end{align*}$

此时得到短矢量 $g^*=4x^2+5x+6$ .

约化基算法的一些细节说明

对于约化基算法6,它应该是一种说明性质的,实际使用它时有些效率上的不足.例如仔细分析一下我们会发现该算法第4步中的GSO更新是不必要的,可以将这一步省去.而且在每一步交换两个基向量时对GSO的更新也是有很多冗余计算的.当我们采用本节介绍的算法后,我们可以发现它甚至能比原算法效率提高一百倍.

事实上,关于格的约化基的定义方式在各文献中不一致,上节所提的定义方式是文献[1]给出的.A. K. Lenstra, H. W. Lenstra和L. Lovász的文献[3]中就给出了如下定义:

定义5 设 $f_1,\ldots,f_n\in\mathbb{R}^n$ 线性无关且 $(f_1^*,\ldots,f_n^*)$ 是其对应的GS正交基,并且记 $\mu_{ij}=\idea{f_i,f_j^*}/\idea{f_j^*,f_j^*}$ 则称 $(f_1,\ldots,f_n)$ 是约化基,如果满足以下条件:

$|\mu_{ij}|\le 1/2,\forall 1\le j<i\le n$ ,
$|f_i^*+\mu_{i,i-1}f_{i-1}^*|^2\ge\frac{3}{4}|f_{i-1}^*|^2,\forall 1<i\le n$ .

注6 这里关于矩阵元 $\mu_{ij}$ 的定义可能和上节有点不一样,这是上节将 $f_i$ 视为列向量,而本节视为行向量,只是叙述语言的不同,并无本质差别.

从定义中我们明显看出,本节定义的约化基一定是上一节定义的约化基,其条件更强,因此对后面的算法是没有影响的.下面我们给出新的约化基算法,它在细节处理比前节的算法要节省很多计算.

算法7(约化基算法) 输入输出同算法6.

初始化工作.首先将各 $g_i$ 初化为 $f_i$ ,并且 $i$ 顺次由1循环到 $n$ ,做如下步骤2至4,
$g_i^*=g_i$ ,
将 $j$ 顺次由1循环到 $i-1$ ,计算 $\mu_{ij}=\idea{g_i,g_j^*}/G_j$ , $g_i^*=g_i^*-\mu_{ij}g_j^*$ ,
$G_i=\idea{g_i^*,g_i^*}$ ,
$k=2$ ,并循环做下面6-10步,
将 $l$ 顺次由 $k-1$ 递减到 $1$ ,做如下7-8步,
若 $|\mu_{kl}|>1/2$ ,则 $r=\lfloor\mu_{kl}\rceil,g_k=g_k-rg_l,$ 对 $j=1,2,\ldots,l-1$ 顺次计算 $\mu_{kj}=\mu_{kj}-r\mu_{lj}$ ,并且 $\mu_{kl}=\mu_{kl}-r$ ,
若 $l=k-1$ 则检验 $G_k<(\frac{3}{4}-\mu_{k,k-1}^2)G_{k-1}$ 是否成立,若成立则交换 $g_k$ 与 $g_{k-1}$ 并更新此时的各GSO结果,并直接转第6步,
若 $k=n$ 则终止算法并输出 $(g_1,\ldots,g_n)$ ,
$k=k+1$ .

算法的终止性见[3].

本算法仅在初始化时需要计算诸 $g_i^*$ ,在后面的算法中实际上已不需要它们,只要保存 $\mu_{ij}$ 矩阵以及各 $g_i^*$ 的模 $G_i$ 即可.在本节的开始,我们也提到了在交换两个基矢时对整个GSO的更新实际上包含了很多不必要的计算,因此本算法第8步所提的到的更新GSO步骤是很重要的,我们在下面给出:

算法8(约化基算法第八步的更新) 各符号同算法7.

$\mu=\mu_{k,k-1}$ , $G=G_k+\mu^2G_{k-1}$ , $\mu_{k,k-1}=\mu G_{k-1}/G$ , $G_k=G_{k-1}G_k/G$ , $G_{k-1}=G$ ,
交换两个基矢 $(g_{k-1},g_k)=(g_k,g_{k-1})$ ,
对 $j=1,2,\ldots,k-2$ 顺次交换 $(\mu_{k-1,j},\mu_{kj})=(\mu_{kj},\mu_{k-1,j})$ ,
对 $i=k+1,k+2,\ldots,n$ 顺次计算 $\begin{pmatrix}\mu_{i,k-1}\\ \mu_{ik}\end{pmatrix}=\begin{pmatrix}1 &\mu_{k,k-1}\\ 0 &1\end{pmatrix}\begin{pmatrix}0 &1\\ 1 &-\mu\end{pmatrix}\begin{pmatrix}\mu_{i,k-1}\\ \mu_{ik}\end{pmatrix}$
若 $k>2$ 则 $k=k-1$ .

关于更新算法的正确性,只需作一些计算即可证明,这里也不验证了,可以参考[3]P520.

应用格中短向量的分解算法

下面以Hensel提升和格中短向量方法为例来说明后者.这里我们先证明一个引理,便于后面算法正确性的证明.

引理6 $p\in\mathbb{Z}$ 是素数, $l$ 是正整数, $f$ , $g$ , $u\in\mathbb{Z}[x]$ 是非零多项式且 $p\not|\mathrm{lc}(f)$ , $f\bmod p$ 无平方, $g|f$ , $u$ 是首一非平凡多项式,且 $u|f\bmod p^l$ , $u|g\bmod p$ .则 $u|g\bmod p^l$ .

证明令 $h,v,w\in\mathbb{Z}[x]$ 使得 $f=gh\equiv uw\pmod{p^l}$ 且 $g\equiv uv\pmod{p}$ . $f\bmod p$ 无平方,则 $g\bmod p$ 也无平方因子, $\gcd(u\bmod p,v\bmod p)=1\in\field{p}[x]$ .由Hensel引理知有 $u^*$ , $v^*\in\mathbb{Z}[x]$ 使得 $u^*\equiv u\pmod{p}$ , $v^*\equiv v\pmod{p}$ 且 $g\equiv u^*v^*\pmod{p^l}$ .于是 $uvh\equiv gh\equiv uw\pmod{p}$ 推出 $vh\equiv w\pmod{p}$ . $v^*h\equiv vh\equiv w\pmod{p}$ 且 $u^*(v^*h)\equiv gh=f\equiv uw\pmod{p^l}$ .再由 $u$ , $v$ 在模 $p$ 下互素,我们由提升的唯一性知 $u^*\equiv u\pmod{p^l}$ , $g\equiv uv^*\pmod{p^l}$ . □

算法9(整系数因子分解算法4:Hensel提升和格中短向量算法)

输入：一个无平方因子本原 $n(\ge 1)$ 次多项式 $f\in\mathbb{Z}[x]$ , $\mathrm{lc}(f)>0$ 且 $\|f\|_{\infty}=A$ ,

输出： $f$ 的不可约因子 $\{f_1,\ldots,f_k\}\subset\mathbb{Z}[x]$ .

若 $n=1$ 则输出 $\{f\}$ ,否则 $b=\mathrm{lc}(f)$ , $B=(n+1)^{1/2}2^nA$ , $C=(n+1)^{2n}A^{2n-1}$ , $\gamma=\lceil 2\log_2C\rceil$ ,
任选素数 $p\le 2\gamma\ln\gamma$ , $\overline{f}=f\bmod p$ ,直至 $p\not|b$ 且 $\gcd(\overline{f},\overline{f}')=1\in\field{p}[x]$ ,再令 $l=\lceil\log_p(2^{n^2}B^{2n})\rceil$ ,
在 $\field{p}[x]$ 上得到分解 $f\equiv bh_1\cdots h_r\pmod{p}$ ,各因子无穷范数小于 $p/2$ 且首一,
利用Hensel提升得到分解 $f\equiv bg_1\cdots g_r\pmod{p^l}$ ,各因子不可约且无穷范数小于 $p^l/2$ ,首一,
$T=\{1,\ldots,r\}$ , $G=\emptyset$ , $f^*=f$ ,
当 $T\neq\emptyset$ 时,做下面7～10步,
在 $\{g_t|t\in T\}$ 中选择次数最大的因子 $u$ , $d=\deg u$ , $n^*=\deg f^*$ ,对 $d<j\le n^*$ 的 $j$ 循环做下面8、9步,
调用算法6计算一个短矢量 $g^*\in L$ ,其中 $L$ 为 $\{ux^i|0\le i<j-d\}\cup\{p^lx^i|0\le i<d\},$
用试除法得到 $S\subset T$ ,其中 $S=\{i\in T|h_i|g^*\bmod p\}$ ,计算 $h^*\in\mathbb{Z}[x]$ 使得其无穷范数小于 $p^l/2$ 且满足 $h^*\equiv b\prod_{i\in T\setminus S}g_i\pmod{p^l}$ ,若 $\|\mathrm{pp}(g^*)\|_1\|\mathrm{pp}(h^*)\|_1\le B$ 则 $T=T\setminus S$ , $G=G\bigcup\{\mathrm{pp}(g^*)\}$ , $f^*=\mathrm{pp}(h^*)$ , $b=\mathrm{lc}(f^*)$ ,转第6步,
$T=\emptyset$ , $G=G\bigcup\{f^*\}$ ,
输出 $G$ .

证明(算法有效性:) 只需证明每次执行第6步时,我们有 $f^*\equiv b\prod_{i\in T}g_i\pmod{p^l},\quad b=\mathrm{lc}(f^*),\quad f=\pm f^*\prod_{g\in G}g,$ 且 $G$ 中多项式均不可约.初始时显然满足,假设每次到第7步时均满足,令 $g\in\mathbb{Z}[x]$ 为 $f^*$ 的一个不可约因子且 $u|g\bmod p$ ,则由本节开始的引理知 $u|g\bmod p^l$ .相反地,若 $v\in\mathbb{Z}[x]$ 是 $f$ 的因子且在模 $p$ 下能被 $u$ 整除，则 $g|v\in\mathbb{Z}[x]$ .我们可以证明第9步中的条件成立当且仅当 $\mathrm{pp}(g^*)\mathrm{pp}(h^*)=\pm f^*$ ,又 $\deg g^*<j$ ,我们知道只要 $j\le\deg g$ 则条件不满足.同样地，第10步能使得上述条件在算法循环结束时也是成立的,如果 $\#T=1$ 且 $g=f^*$ 是不可约的.

假设 $\deg g<n^*$ ,令 $j=1+\deg g$ .则 $g\in L$ .于是 $\|g^*\|\le 2^{(j-1)/2}\|g\|<2^nB$ .再由 $l$ 的选择,我们有 $\|g^*\|^{j-1}\|g\|^{\deg g^*}<(2^nB)^nB^n\le p^l,$ 于是由引理3知 $\gcd(g,g^*)$ 非平凡,由 $g$ 不可约以及 $\deg g^*\le j-1=\deg g$ 得 $g=\pm\mathrm{pp}(g^*)$ .

令 $h=f^*/g$ ,则由Hensel提升唯一性知在第9步有 $\mathrm{lc}(g)h\equiv h^*\pmod{p^l}$ .再由 $p^l/2$ 大于 $\|bh\|_{\infty}$ 的Mignotte界bB,于是 $\mathrm{lc}(g)h=h^*,h=\mathrm{pp}(h^*)$ ,且 $f^*=\pm\mathrm{pp}(g^*)\mathrm{pp}(h^*)$ ,算法会到到 $f$ 的不可约因子 $g$ . □

例5 仍然考虑例1和例3中的例子 $f=4x^4+13x^3+28x^2+27x+18\in\mathbb{Z}[x]$ . ◇

解首先,此时 $l=\log_5(2^{n^2}B^{2n})=48.1266$ ,故需提升6次,我们在例3的结果上再提升三次,可以得到如下结果： $\begin{align*} f&\equiv 4(x^2+2x+3)(x+219914302784468853031851163930189578018051741)\\ &(x+186661511897595309720943636396038563766616229)\pmod{5^{64}}, \end{align*}$ 另外由前面例3结果我们知道 $f\equiv 4(x^2+2x-2)(x+1)(x-1)\pmod{5}.$

首先 $u=x^2+2x+3$ , $d=2$ ,则 $L$ 的生成元为 $\{(1,2,3),(0,5^{64},0),(0,0,5^{64})\}.$ 很显然 $(1,2,3)$ 应该是一个短向量,由试除法得到 $S=\{1\}$ , $h^*=4\prod_{i=2,3}g_i\bmod 5^{64}=4x^2+5x+6$ ,显然满足条件,得到一个不可约因子 $x^2+2x+3$ ,此时 $f^*=4x^2+5x+6$ , $b=4$ .此时我们再取因子 $u=x+219914302784468853031851163930189578018051741,$ $d=1$ , $n^*=2$ , $j$ 只能取 $2$ ,则得到 $L$ 的生成元 $\{u,(0,5^{64})\}$ ,由例4得到 $g^*=-6999570441183108942993x-13384313532767302775813,$ $g^*$ 是本原的且是 $g^*\equiv 2x+2\pmod{5}$ ,由试除法知 $S=\{2\}$ ,但此时已有 $\|g^*\|_1>B$ ,故此时无解，循环结束，第二个不可约因子为此时的 $f^*=4x^2+5x+6$ .