1.   引言

Hermite标准型和Smith标准型是两种定义在整数矩阵上的重要标准型，它们在很多方面都有应用，比如，Hermite标准型可以用于解丢番图方程^[1]，整数规划^[2]和格上的计算问题^[3]，Smith标准型可以用来确定有限生成阿贝尔群的基础理论中的不变常量^[4]。而计算Hermite标准型和Smith标准型通常来说需要将格基三角化以后才能进行。所以为了提高计算Hermite标准型和Smith标准型的算法的效率，提高矩阵三角化算法的效率有很重要的意义。

从另一个角度来看，格是数论中很重要的概念，而基于格的密码学由于其高效、多功能和潜在抗量子攻击等性质吸引了众多密码学家的注意。对于同一个格而言，由于所有的格基都有相同的Hermite标准型，所以一般在基于格的公钥密码体制中将Hermite标准型作为公钥^[5]。

为了提高基于格的密码算法的效率，密码学家提出了理想格的概念。理想格相比于一般的格拥有更多的代数结构，可以加速运算并减少空间存储。目前已经有一些算法在理想格上运行比在一般格上要快，比如Lyubashevsky等人^[6]在理想格上给出了更快的Gram-Schmit正交化和高斯采样算法(循环格)。但是目前还没有理想格上对三角化的加速算法。

目前最快的格基三角化算法是Hafner和McCurley^[7]在1991年提出的。对于一个$n \times n$的整数矩阵A，其每个元素的上界为$B$，那么计算A的三角化矩阵可以在$O\left( {{n^{1 + \omega }}{{\log }_2}B} \right)$时间复杂度内完成，其中$O\left( {{n^\omega }} \right)$是两个$n \times n$维矩阵相乘所需要的乘法次数，目前最快的算法中$\omega$可以降低到2.372^[8]。该算法使用快速矩阵乘法来实现三角化，但是并没有结果说明如何在相同的时间内得到矩阵的Hermite标准型。直到1996年，Storjohann等人^[9]利用快速矩阵乘法技术将计算Hermite标准型的时间复杂度降低到$O\left( {{n^{1 + \omega }}{{\log }_2}B} \right)$。

至于Smith标准型的计算，确定性算法步骤基本是先计算出Hermite标准型然后再通过初等变换来计算。所以目前计算Smith标准型最快的时间复杂度和计算Hermite标准型是一样的。

本文利用理想格上的特殊结构来降低对理想格上格基三角化的复杂度，该算法的时间复杂度可以降低到$O\left( {{n^3}{{\log }_2}B} \right)$。同时，基于在文献[10]和文献[11]中提出的理想格性质，本文可以确定地得到理想格上格基的Smith标准型，其时间复杂度也低于目前最快的算法。虽然和文献[7]中类似，本文还不能在$O\left( {{n^3}{{\log }_2}B} \right)$时间复杂度内得到任意理想格上格基的Hermite标准型，但是针对格密码学中经常使用的一类理想格，本文可以得到一个在$O\left( {{n^3}{{\log }_2}B} \right)$时间内计算格基的Hermite标准型的算法。

本文的结构安排如下：第2部分介绍预备知识和现有的结果；第3部分提出新的理想格上格基三角化算法；第4部分说明对一类特殊的理想格可以在$O\left( {{n^3}{{\log }_2}B} \right)$时间内计算格基的Hermite标准型。

2.   预备知识

2.1   符号约定

本文用斜体粗体大写字母来表示矩阵，用粗体小写字母来表示行向量。对于矩阵${{A}}\in {{\mathbb{Z}}^{n\times m}}$，在第$i$行、第$j$列的元素表示为${a_{ij}}$，矩阵${{A}}$的$i$行表示为${{A}}_{{i}}$。一个整数矩阵的三角化矩阵用${{T}}$来表示，且用${{H}}$和${{S}}$分别表示该矩阵的Hermite标准型和Smith标准型。

对于一个多项式$f\left( x \right)$，其首项系数用${\rm{lc}}\left( f \right)$来表示，最高次数用${\rm{deg}}\left( f \right)$来表示。零多项式的次数定义为$- \infty$。

2.2   多项式的最大公因式及扩展欧几里得算法

给定某个唯一分解整环上两个多项式$f\left( x \right)$和$g\left( x \right)$，判定它们的最大公因子的最高次数是否$\ge 1$是一个经典问题。为此，下面介绍两个多项式的结式，其定义如下。

定义 1(结式)　令$f\left( x \right) = {f_n}{x^n} + {f_{n - 1}}{x^{n - 1}} + ···+$${f_1}x + {f_0}$, $g\left( x \right) = {g_m}{x^m} + {g_{m - 1}}{x^{m - 1}} + ··· + {g_1}x + {g_0}$为次数分别为$n$和$m$的两个多项式。定义$f\left( x \right)$和$g\left( x \right)$的Sylvester矩阵：

则${f\left( x \right)}$和${g\left( x \right)}$的结式定义为${\bf{Sylv}}\left( {f\left( x \right),g\left( x \right)} \right)$的行列式，用${\rm{Res}}\left( {f\left( x \right),g\left( x \right)} \right)$来表示。

结式的概念可用来判定$f\left( x \right)$和$g\left( x \right)$是否存在次数大于1的最大公因式，而为了计算$f\left( x \right)$和$g\left( x \right)$的最大公因式，需要多项式上扩展欧几里得算法来计算。下列等式给出了计算$f\left( x \right)$和$g\left( x \right)$的最大公因式的过程：

这里$\deg \left( g \right) \!\!> \!\! \deg \left( {{r_1}} \right) \!> \!\deg \left( {{r_2}} \right) \!> \! ··· \!>\!\deg \left( {{r_{l - 1}}} \right)\!>$$\deg \left( {{r_l}} \right) = 0$。

如果上述计算是在一个域中进行(比如${\mathbb{Q}}$)，那么所有的${\alpha _i}$都可以取为1，则${r_l}\left( x \right)$就为$f\left( x \right)$和$g\left( x \right)$在域中拥有最大次数的公因式。

从上述过程中,可以用$f\left( x \right)$和$g\left( x \right)$来表示所有的余式${r_i}\left( x \right)$，即${s_i}\left( x \right)f\left( x \right) + {t_i}\left( x \right)g\left( x \right)$，其中$i = 1,$$2, ··· ,l - 1,\,l$，那么有如下性质。

引理 1　令$f\left( x \right)$, $g\left( x \right)$为次数分别为$n$和$m$的两个多项式，这里$n>m$。令${r_1}\left( x \right),{r_2}\left( x \right), ··· , {r_l}\left( x \right)$为式(1)中定义的余式。若${\rm{deg}}({r_1}) = {n_i}$，且${r_i}\left( x \right) \!=\!$${s_i}\left( x \right)f\left( x \right) + {t_i}\left( x \right)g\left( x \right)$，则${\rm{deg}}\left( {{s_i}} \right) = m - {n_{i - 1}} < m,$${\rm{deg}}\left( {{t_i}} \right) = n - {n_{i - 1}} < n$并且满足${s_i}\left( x \right) ={\alpha _i}{s_{i \!-\! 2}}\left( x \right) \!-$${q_i}\left( x \right){s_{i \!-\! 1}}\left( x \right)$, ${t_i}\left( x \right) \!=\! {\alpha _i}{t_{i \!-\! 2}}\left( x \right) \!- {q_i}\left( x \right){t_{i \!-\! 1}}\left( x \right)$。

欧几里得算法是最古老的算法之一，其应用非常广泛。本文给出文献[12]中关于${\mathbb{Z}}$上多项式的扩展欧几里得算法的相关结论。引理2对于证明本文算法的正确性和分析复杂度有重要作用。

引理 2　令${\cal F}$为一个域，$f\left( x \right)$, $g\left( x \right)$, $s\left( x \right)$, $t\left( x \right) \in$${\cal F}\left[ x \right]$，且${\rm{deg}}\left( {f\left( x \right)} \right) \!=\! n$, $r\left( x \right) \!=\! s\left( x \right)f\left( x \right) \!+\! t\left( x \right)g\left( x \right)$, $t\left( x \right) \ne 0$，并假设${\rm{deg}}\left( r \right) + {\rm{deg}}\left( t \right) < n = {\rm{deg}}\left( f \right)$。令${r_i}\left( x \right) = {s_i}\left( x \right)f\left( x \right) + {t_i}\left( x \right)g\left( x \right)$为通过式(1)得到的余式，其中$0 \le i \le l + 1$。定义整数$j$满足条件${\rm{deg}}\left( {{r_j}} \right) \le {\rm{deg}}\left( r \right){\rm{}} < {\rm{deg}}\left( {{r_{j - 1}}} \right)$。那么存在一个非零元素$\alpha \left( x \right) \in {\cal F}\left[ x \right]$使得

引理 3　对于$f\left( x \right)$, $g\left( x \right) \in {\mathbb{Z}} \left[ x \right]$，且满足${\rm{deg}}\left( f \right) =$$n > {\rm{deg}}\left( g \right) = m \ge {\rm{}}1$。令${\rm{}}0 \le k \le m < n$，那么$k$不会出现在式(1)中余式序列的次数中当且仅当存在$s\left( x \right)$和$t\left( x \right)$满足

引理 4　对于$f\left( x \right)$, $g\left( x \right) \in {\mathbb{Z}}\left[ x \right]$，且满足${\rm{deg}}\left( f \right) =$$n > {\rm{deg}}\left( g \right) = m \ge {\rm{}}1$。那么存在快速的扩展欧几里得算法可以$O\left( {{n^3}{{\log }_2}B} \right)$时间内计算出${\mathbb{Q}}\left[ x \right]$上的${r_i}\left( x \right)$, ${s_i}\left( x \right)$, ${t_i}\left( x \right)$，这里$B$是$f\left( x \right)$和$g\left( x \right)$的系数上界。

2.3   格

定义 2(格)　给定$m$个线性无关的向量，${{{b}}_{\bf{1}}}$, ${{{b}}_{\bf{2}}}$, $···$, ${{{b}}_{{m}}}$，其中${{{b}}_{{i}}} \in {{\mathbb{R}}^n}$。${{{B}}} \in {{\mathbb{R}}^{m \times n}}$定义为${{{B}}_{{i}}}={{{b}}_{{i}}}$。则由${{B}}$生成的格${\cal L}\left( {{B}} \right)$定义为

则称${{B}}$是格${\cal L}\left( {{B}} \right)$的一组基，其中$m$和$n$分别称为格${\cal L}\left( {{B}} \right)$的秩和维数。当$m=n$时，称格${\cal L}\left( {{B}} \right)$是满秩的。

定义 3(行列式)　给定格${\cal L}\left( {{B}} \right)$，其行列式定义为${\rm{det}}\left( {{\cal L}\left( {{B}} \right)} \right) = \sqrt {{\rm{det}}\left( {{{{B}}^{\rm{T}}}{{B}}} \right)}$。

当${\cal L}\left( {{B}} \right)$是满秩的时候，${{B}}$是一个非奇异的方阵，此时${\rm{det}}\left( {{\cal L}\left( {{B}} \right)} \right) = \left| {{\rm{det}}\left( {{B}} \right)} \right|$。

注意到，当从给定格${\cal L}$中选取任意格向量时，并不是每一组选取的格向量集合都可以扩展为格${\cal L}$的一组基。下面的引理给出了判定一组选取的格向量集合是否能扩展为一组格基的方法^[13]。

引理 5　给定满秩格${\cal L}({{ b}_{\bf 1}},{{ b}_{\bf 2}}, ··· ,{{ b}_{{n}}})$中$r$个线性无关的向量${{ v}_{\bf 1}},{{ v}_{\bf 2}}, ··· ,{{ v}_{{r}}}$，且满足

则下列的条件是等价的：

(1) 存在格向量${{{u}}_{{{r}} + {\bf{1}}}}$, ${{{u}}_{{{r}} + {\bf{2}}}}$, ··· , ${{{u}}_{{n}}}$使得${{{v}}_{\bf{1}}}$, ${{{v}}_{\bf{2}}}$, ···, ${{{v}}_{{r}}}$, ${{{u}}_{{{r}} + {\bf{1}}}}$, ${{{u}}_{{{r}} + {\bf{2}}}}$, ···, ${{{u}}_{{n}}}$是${\cal L}$的一组基；

(2) ${{A}}$的所有$r \times r$阶子式的最大公因子为1；

(3) ${{{v}}_{\bf{1}}}$, ${{{v}}_{\bf{2}}}$, ···, ${{{v}}_{{r}}}$是${\cal L}\mathop \cap {\rm{span}}({{{{v}}_{\bf{1}}}},{{{{v}}_{\bf{2}}}}, ··· ,{{{{v}}_{{r}}}})$的一组基；

(4) 存在一个矩阵${{P}} \,\in\, {\mathbb{Z}}{^{n \,\times\, n}}$使得${{A}} \,\cdot\, {{P}} =$${\left[ {\begin{array}{*{20}{c}} {{{{I}}_{{r}}}}&{{{{{ O}}}_{r \times \left( {n - r} \right)}}} \end{array}} \right]_{r \times n}}$；

(5) 存在一个矩阵${{B}} \in {\mathbb{Z}}{^{\left( {n - r} \right) \times n}}$使得${\left[ {\begin{array}{*{20}{c}} {{{A}}}\\ {{B}} \end{array}} \right]_{n \times n}}$是一个幺模矩阵。

引理 6　令${{A}} \in {\mathbb{Z}}{^{m \times n}}$，其中$n>m$。假设${{A}}$可以通过添加$(n-m)$个合适的行成为幺模矩阵。如果${{A}}$的每一行都是一个格${\cal L}$的格向量，那么${{A}}$可以扩充为${\cal L}$的一组基。

由引理5可知，因为${{A}}$可以扩充为一个幺模矩阵，则存在${{P}} \in {\mathbb{Z}}{^{n \times n}}$使得${{A}} ··· {{P}} = {\left( {{{{I}}_{{m}}},0, ··· ,0} \right)_{{n}}}$，其中等式右边有$(n-m)$个0。假设${\cal L}$的一组基是${{B}} \in {\mathbb{Z}}{^{n' \times n}}$，其中$m \le n' \le {\rm{}}n$。

因为${{A}} \in {\cal L}$，所以存在矩阵${{U}} \in {\mathbb{Z}}{^{m \times n'}}$使得${{A}} = {{U}} \cdot {{B}}$。所以${{A}} \cdot {{P}} = {{U}} \cdot {{B}} \cdot {{P}} = {{{I}}_{{m}}},$$0, ··· ,0_{{n}}$。记${{P}}' = {{B}} \cdot {{P}}$然后将${{P}}'$分为两个部分，${{{P}}_{\bf{1}}}^{'} \in {\mathbb{Z}}{^{n' \times n'}}$和${{{P}}_{{2}}}^{'} \in {\mathbb{Z}}{^{n' \times (n-n^{'})}}$，即${{P}}^{'}=[{{{P}}_{{1}}}^{'} \;\bigr|\; {{{P}}_{{2}}}^{'}]$。于是有

因为${{U}} \cdot {{{P}}_{\bf{1}}}^{'} = {{\mathbb{Z}}^{m \times n'}}$, $m \le n'$，所以${{U}} \cdot {{{P}}_{\bf{1}}}^{'}=$${\left( {{{{I}}_{{m}}},0, ··· ,0} \right)_{n'}}$。则${{U}}$可扩充为一个幺模矩阵。假设${{U}}' = {\left[ { {{{{U}}^{{\rm T}}}}\;\bigr|\;{{{{\bar{ U}}}^{{\rm T}}}} } \right]^{\rm {T}}}$是一个幺模矩阵，${{U}}' \cdot {{B}} =$$\left[ { {{{{A}}^{{\rm T}}}}\;\bigr|\;{{{{\bar{ A}}}^{{\rm T}}}}} \right]^{{\rm T}}$是${\cal L}$的一组基。所以${{A}}$可以扩充为${\cal L}$的一组基。

2.4   理想格

理想格是定义在多项式环上的一类特殊的格，同时具有加法和乘法封闭的性质。一般来说，考虑环$R = {\mathbb{Z}}\left[ {{x}} \right]/\left\langle {f\left( x \right)} \right\rangle$，这里$f\left( x \right) \in {\mathbb{Z}}\left[ x \right]$是一个次数为$n$的首一多项式，$\left\langle {f\left( x \right)} \right\rangle$表示$f\left( x \right)$在多项式环${\mathbb{Z}}\left[ x \right]$中生成的理想。然后考虑式(7)的嵌入

对于任何一个多项式$v\left( x \right) \in {\rm{}}R$，用${{v}}$来表示$v\left( x \right)$在嵌入$\sigma$下的像，并且将${{v}}$和$v\left( x \right)$考虑为等价的表达式。

令$g\left( x \right) \in {\rm{}}R$为一个次数小于$n$的多项式且$v\left( x \right) \in \left\langle {g\left( x \right)} \right\rangle$，则存在一个次数小于$n$的多项式$w\left( x \right) \in {\mathbb{Z}}\left[ x \right]$使得$v\left( x \right) = w\left( x \right)g\left( x \right){\rm{mod}}f\left( x \right)$。如果将$w(x)$表示为$w\left( x \right) = {w_{n - 1}}{x^{n - 1}} + {w_{n - 2}}{x^{n - 2}} + ··· +$${w_0}$，那么$v\left( x \right) = \displaystyle\mathop \sum \nolimits_{i = 0}^{n - 1} {w_i}{x^i}g\left( x \right){\rm{mod}}f\left( x \right)$。于是每一个$\left\langle {g\left( x \right)} \right\rangle$中的元素都可以由$g\left( x \right){\rm{mod}}f\left( x \right)$, $xg\left( x \right){\rm{mod}}f\left( x \right)$, ···, ${x^{n - 1}}g\left( x \right){\rm{mod}}f\left( x \right)$整系数线性表示的。所以$\left\langle {g\left( x \right)} \right\rangle$在嵌入$\sigma$下构成一个格。于是有：

定义 4(理想格)　给定$g\left( x \right) \in {\rm{}}R ={\mathbb{Z}} \left[ {\rm{x}} \right]/$$\left\langle {f\left( x \right)} \right\rangle$，这里$f\left( x \right) \in {\mathbb{Z}}\left[ x \right]$是一个次数为$n$的首一多项式，那么由$g\left( x \right)$在嵌入$\sigma$下构成一个格${\cal L}$，称${\cal L}$为由$g\left( x \right)$生成的理想格。

更进一步，如果$g\left( x \right)$和$f\left( x \right)$在${\mathbb{Z}}$上互素，则$g(x) {\rm{mod}} f(x)$, $xg\left( x \right){\rm{mod}}f\left( x \right)$, ···, ${x^{n - 1}}g\left( x \right){\rm{mod}}f\left( x \right)$是线性无关的。否则存在不全为零的整系数${a_0}$, ${a_1}$, $···, {a_{n - 1}}$使得$\displaystyle\mathop \sum \nolimits_{i = 0}^{n - 1} {a_i}{x^i}g\left( x \right){\rm{mod}}f\left( x \right) = 0$，即$\left (\displaystyle\mathop \sum \nolimits_{i = 0}^{n - 1} {a_i}{x^i}\right)g\left( x \right) = 0\;{\rm{mod}}f\left( x \right)$，而这说明$g\left( x \right)$和$f\left( x \right)$并不是互素的，矛盾。所以此时由$g\left( x \right)$生成的理想格是满秩的。

定义 5(本原格向量)　一个格向量${{v}} \in {\cal L}$如果是格${\cal L}$中的一个本原格向量当且仅当对任意的整数$k>1$，${{v}}/k \notin {\cal L}$。

定义 6(本原向量)　对于一个向量${{v}} =$$\left( {{v_1},{v_2}, ··· ,{v_n}} \right) \in {\cal L}$，如果${\rm{gcd}}\left( {{v_1},{v_2}, ··· ,{v_n}} \right) = 1$，则称${{v}}$是一个本原向量。

定义 7(本原多项式)　一个多项式$a\left( x \right) \in$${\mathbb{Z}}\left[ x \right]$称为本原多项式当且仅当对任意整数满足$k>1$都有$a\left( x \right)/k \notin {\mathbb{Z}}\left[ x \right]$。

定义 8(容度)　给定一个多项式$a\left( x \right) = {a_n}{x^n} +$${a_{n - 1}}{x^{n - 1}} + ··· + {a_0} \in {\mathbb{Z}}\left[ x \right]$，其容度定义为$a\left( x \right)$的各系数的最大公因子，即${\rm{gcd}}\left( {{a_n},{a_{n - 1}}, ··· ,{a_0}} \right)$，并将容度表示为${\rm{cont}}\left( {a\left( x \right)} \right)$。

很明显，对于任意的多项式$a\left( x \right) \in {\mathbb{Z}}\left[ x \right]$，$a\left( x \right)/{\rm{cont}}\left( {a\left( x \right)} \right)$是一个本原的多项式，称之为$a\left( x \right)$的本原部分。

一个格向量${{v}} = {{xB}} \in {\cal L}\left( {{B}} \right)$是一个本原的格向量当且仅当${{x}}$是一个本原向量。和在一般格中类似，在由$g\left( x \right) \in {\rm{}}R = {\mathbb{Z}}\left[ {{x}} \right]/\left\langle {f\left( x \right)} \right\rangle$生成的理想格中，一个格向量$v\left( x \right) = t\left( x \right)g\left( x \right){\rm{mod}}f\left( x \right)$是本原的当且仅当$t\left( x \right)$是一个本原多项式。

2.5   Hermite标准型

对于整数矩阵而言，Hermite标准型是一个非常重要的概念，其定义如下：

定义 8(Hermite标准型)　一个非奇异的方阵${{H}} \in {{\mathbb{Z}}^{n \times n}}$是Hermite标准型，如果满足如下条件：

(1) ${h_{ii}} > 0$, $1 \le i \le n$;

(2) ${h_{ij}} > 0$, $1 \le j < i \le n$;

(3) $0 \le {h_{ji}} < {h_{ii}}$, $1 \le j < i \le n$。

需要注意的是，这里只给出了Hermite标准型的一种定义，是作行变换得到一个上三角矩阵。根据是行列变换以及最后是上三角矩阵还是下三角矩阵，Hermite标准型会有不同的定义。

对于高维随机生成的矩阵，其Hermite标准型的对角元素是非常不平衡的：大多数都很小(实际上大多数都为1)，而且经常最后一个元素非常大，该类Hermite标准型通常会有密码学意义。由此定义如下一个非常特别的Hermite标准型：

定义 8(简单Hermite标准型)　一个非奇异的方阵${{H}} \in {{\mathbb{Z}}^{n \times n}}$是简单Hermite标准型当且仅当其是Hermite标准型且满足${h_{ii}} = 1$，其中$1 \le i \le n - 1$。

通常在格密码中选择具有简单Hermite标准型的格，可以使得计算更简单、密钥尺寸更小。

2.6   Smith标准型

对于整数矩阵而言，另一个重要的标准型是Smith标准型。其定义如下：

定义 8(Smith标准型)　一个方阵${{S}} \in {{\mathbb{Z}}^{n \times n}}$是Hermite标准型，如果满足如下条件：

(1) ${s_{ii}}|{s_{jj}}$, $i<j$；

(2) ${s_{ij}} > 0$, $i \ne j$。

文献[10,11]说明在理想格中，格基的Hermite标准型具有非常特殊的形式。

引理 7　令${\cal L}$为由$g\left( x \right) \in {\rm{}}R = {\mathbb{Z}}\left[ {{x}} \right]/\left\langle {f\left( x \right)} \right\rangle$生成的理想格，这里$f\left( x \right)$是${\mathbb{Z}}\left[ {{x}} \right]$中一个次数为$n$的首一多项式，$g\left( x \right)$的次数为$m$，且$n>m$。假设$g\left( x \right)$与$f\left( x \right)$互素，那么${\cal L}$的Hermite标准型由式(8)表示

满足${h_{ii}}|{h_{1j}}$，对于$1 \le i \le l \le j \le n$。

由上所述，对于一个理想格而言，其格基的Hermite标准型的对角线构成了其Smith标准型。

3.   理想格上格基三角化的快速算法

这节给出对于理想格${\cal L}$上格基快速三角化的算法，该算法可以在$O\left( {{n^3}{{\log }_2}B} \right)$时间内完成，这里${\cal L}$是由$g\left( x \right) \in {\rm{}}R = {\mathbb{Z}}\left[ {{x}} \right]/\left\langle {f\left( x \right)} \right\rangle$生成的理想格，$f\left( x \right)$是${\mathbb{Z}}\left[ {{x}} \right]$上一个首一$n$次的不可约多项式，$B$是$f\left( x \right)$和$g\left( x \right)$的系数上界(在本文中，不作特殊说明外，考虑$g\left( x \right)$为一个本原多项式)。本文算法包括两个步骤，首先利用扩展欧几里得算法计算出一系列次数递减的本原格向量，然后从这些格向量中构造出${\cal L}$的一个三角化格基。

为了简单表达，先给出一些符号：对于由$f\left( x \right)$和$g\left( x \right)$得到的余式序列表示为${r_1}\left( x \right)$, ${r_2}\left( x \right)$, ···, ${r_l}\left( x \right)$。将$f\left( x \right)$和$g\left( x \right)$分别表示为${r_{ - 1}}\left( x \right)$和${r_0}\left( x \right)$,余式的次数分别用${n_i}$来表示，即${n_i} = {\rm{deg}}\left( {{r_i}} \right)$，且用${\delta _i}$来表示相邻次数之差，即${\delta _i} = {n_i} - {n_{i - 1}}$，对于$i = - 1,0, ··· ,l - 1$。

3.1   计算本原格向量序列

这节给出计算本原格向量序列的算法，该算法源于理想格上三角化和使用欧几里得算法来计算多项式的余式时情况很类似。表1给出了计算本原格向量序列的过程。

表 1  本原格向量序列

输入：${\mathbb{Z}}\left[ {{x}} \right]$中$f\left( x \right)$和$g\left( x \right)$，次数分别为$n$和$m$，且$n>m$；
(1) 利用扩展欧几里得算法计算${\mathbb{Q}}[x]$上${r_i}^{'}\left( x \right)$, ${s_i}^{'}\left( x \right)$,　　　　　 ${t_i}^{'}\left( x \right)$，使得${r_i}^{'}\left( x \right) = {r_{i - 2}}^{'}\left( x \right) + {q_i}^{'}\left( x \right){r_{i - 1}}^{'}\left( x \right)$　　　　　 和${r_i}^{'}\left( x \right) = {s_i}^{'}\left( x \right)f\left( x \right) +$${t_i}^{'}\left( x \right)g\left( x \right)$成立，这里　　　　　 $i = 1,2, ··· ,l$；
(2) 计算每一个${t_i}^{'}\left( x \right)$系数分母的最小公倍数${C_i}$, 　　　　　 $i = 1,2, ··· ,l$；
(3) 令${r_i}\left( x \right) = {r_i}^{'}\left( x \right) \cdot {C_i}$为余式序列中第$i$个余式，　　　　　 $i = 1,2, ··· ,l$；
输出：${r_1}\left( x \right)$, ${r_2}\left( x \right)$, ···, ${r_l}\left( x \right)$

下载: 导出CSV 

| 显示表格

引理 8　令$f\left( x \right)$和$\left( x \right)$为${\mathbb{Z}}\left[ {{x}} \right]$中次数分别为$n$和$m$两个多项式，$f\left( x \right)$是首一不可约多项式且次数满足$n>m$。定义${\cal L}$是由$g\left( x \right) \in {\rm{}}R = {\mathbb{Z}}\left[ {{x}} \right]/\left\langle {f\left( x \right)} \right\rangle$生成的理想格。令$B$为$f\left( x \right)$和$g\left( x \right)$所有系数的上界，那么表1算法可以在$O\left( {{n^3}{{\log }_2}B} \right)$内输出${\cal L}$中次数递减的本原格向量。

首先，可以看到${t_i}\left( x \right) = {t_i}^{'}\left( x \right) \cdot {C_i}$是本原多项式。注意到${C_i}{r_i}^{'}\left( x \right) = {C_i}{s_i}^{'}\left( x \right)f\left( x \right) + {C_i}{t_i}^{'}\left( x \right)g\left( x \right)$，由于$f\left( x \right)$是首一的，那么从理想格的角度来看，${t_i}\left( x \right)$对应于格基的整系数表示，所以可以得到${C_i}{s_i}^{'}\left( x \right)$和${C_i}{t_i}^{'}\left( x \right)$都是整系数多项式。因此，算法1中输出的余式${r_i}\left( x \right)$为格${\cal L}$中的本原格向量，$i = 1,2, ··· ,l$。

至于表1算法的时间复杂度，根据引理4，在$O\left( {{n^3}{{\log }_2}B} \right)$时间内计算出${\mathbb{Q}}[x]$上所有的${r_i}^{'}\left( x \right)$, ${s_i}^{'}\left( x \right)$, ${t_i}^{'}\left( x \right)$，这意味着输出长度最大为$O\left( {{n^3}{{\log }_2}B} \right)$。另一方面，在表1算法中计算${t_i}^{'}\left( x \right)$所有系数分母的最小公倍数，其最大为所有分母的乘积，于是可以得到${t_i}^{'}\left( x \right)$的系数大小是由行列式$O\left( {{n}{{\log }_2}B} \right)$唯一决定的。所以算法1的输出尺寸最大为$O\left( {{n^3}{{\log }_2}B} \right)$，当考虑快速整数乘法时，步骤(2)中时间复杂度也最大为$O\left( {{n^3}{{\log }_2}B} \right)$。所以表1算法可以在$O\left( {{n^3}{{\log }_2}B} \right)$时间内输出次数递减的本原格向量序列。

表1算法是将域上面多项式的扩展欧几里得算法延伸到了整数多项式环上，因为在由$g\left( x \right) \in {\rm{}}R =$${\mathbb{Z}}\left[ {{x}} \right]/\left\langle {f\left( x \right)} \right\rangle$生成的理想格${\cal L}$中有$r\left( x \right) = s\left( x \right)f\left( x \right) +$$t\left( x \right)g\left( x \right)$，所以当$t\left( x \right)$的系数为整数时，相当于$x\left( x \right)$在格${\cal L}$中是由格基的整系数线性表示的，可以得到$r\left( x \right)$的系数也必然为整数。

3.2   理想格上格基的三角化

这节说明怎么利用次数递减的本原格向量序列来对格基进行三角化。为了便于表述，将集合$\left\{ {1,2, ··· ,{{n}}} \right\}$划分为$l$个子集合：$\{ n - {n_{i - 1}} + 1,n -$${n_{i - 1}} + 2 ··· ,n - {n_i} \}{\rm{}} = \bigcup\nolimits_{i = 1}^l {{I_i}}$。具体算法如表2所示。

表 2  理想格上格基的三角化

输入：本原格向量序列，${r_0}\left( x \right)$, ${r_1}\left( x \right)$, ···, ${r_l}\left( x \right)$(向量形式为${{{r}}_{\bf 0}}$, 　　　　${{{r}}_{\bf 1}}$, ···, ${{{r}}_{ l}}$)
(1) 令${{T}} \leftarrow {0^{n \times n}}$
(2) 如果$k \in {I_l},{{ T}_k}\left( x \right) = {r_l}\left( x \right){x^{n - k}},i \leftarrow l - 1$
(3) 如果$k \in {I_i}$，
(a) 计算$\phi$和ψ使得 　　　　　　$\phi {\rm{lc}}\left( {{r_i}} \right) + \psi {\rm{lc}}\left( {{{{T}}_{n - {n_{i + 1}}}}} \right) = {\rm{gcd}}\left( {\rm{lc}}\left( {{{{T}}_{n - {n_{i + 1}}}}} \right),\right.$ 　　　　　　$\left.{\rm{lc}}\left( {{r_i}} \right) \right)$
(b) 令${{{T}}_{n - {n_i}}}\left( {{x}} \right) = \phi {r_i}\left( x \right) + \psi {{{T}}_{n - {n_{i + 1}}}}\left( x \right){x^{{\delta _i}}}$
(c) 如果${\rm{lc}}\left( {{{{T}}_{n - {n_i}}}} \right) = 1$，则令 　　　　　 ${{{T}}_j}\left( x \right) = {{{T}}_{n - {n_i}}}\left( x \right){x^{n - {n_i} - j}}$, 　　　　　 $j = 1,2, ··· ,n - {n_i}$，并结束循环
(d) 否则${{{T}}_k}\left( x \right) = {{{T}}_{n - {n_i}}}\left( x \right){x^{n - {n_i} - k}}$, $i \leftarrow i - 1$
(e) 如果$i>0$，到(3)开始循环，否则结束循环
输出：${{T}}$

下载: 导出CSV 

| 显示表格

引理 9　令$f\left( x \right)$和$g\left( x \right)$为${\mathbb{Z}}\left[ {{x}} \right]$中次数分别为$n$和$m$两个多项式，$f\left( x \right)$是首一不可约多项式且次数满足$n>m$。定义${\cal L}$是由$g\left( x \right) \in {\rm{}}R = {\mathbb{Z}}\left[ {\rm{x}} \right]/\left\langle {f\left( x \right)} \right\rangle$生成的理想格。那么存在一个确定性算法，输入表1算法中得到的本原格向量序列，输出${\cal L}$的一个三角化格基，运行时间为$O\left( {{n^3}{{\log }_2}B} \right)$，其中$B$为$f\left( x \right)$和$g\left( x \right)$所有系数的上界。

现在来分析表2算法的时间复杂度。根据Hadmard界，${r_i}\left( x \right)$的各系数的上界为${\left( {\sqrt {n + m} B} \right)^{n + m}}$，所以${r_i}\left( x \right)$的系数由${\left( {\sqrt {n + m} B} \right)^{n + m}}$界定。每一次迭代需要${n_i} + {n_{i + 1}} + 2$次$O\left( {{n}{{\log }_2}B} \right)$比特数字的乘法，所以总的时间复杂度为$\displaystyle\mathop \sum \nolimits_{i = 0}^{l - 1} \Bigr( \left( {{n_i} + {n_{i + 1}} + 2} \right)$$O\left( {n{{\log }_2}B} \right) \Bigr) = O\left( {{n^3}{{\log }_2}B} \right)$。

由于${t_{nn}}$为格${\cal L}$中的常数，且${t_{nn}}{x^i} \in {\cal L}$，其中$i = 0,1, ··· ,n - 1$。所以在进行表2算法时，实际可以在计算中通过模${t_{nn}}$来降低计算量，这种操作并不会增加总的时间复杂度。

定理 1　令$f\left( x \right)$和$g\left( x \right)$为${\mathbb{Z}}\left[ {{x}} \right]$中次数分别为$n$和$m$两个多项式，$f\left( x \right)$是首一不可约多项式且次数满足$n>m$, $B$为$f\left( x \right)$和$g\left( x \right)$所有系数的上界。定义${\cal L}$是由$g\left( x \right) \in {\rm{}}R = {\mathbb{Z}}\left[ {{x}} \right]/\left\langle {f\left( x \right)} \right\rangle$生成的理想格。那么存在一个确定的算法输入$f\left( x \right)$和$g\left( x \right)$，在$O\left( {{n^3}{{\log }_2}B} \right)$时间内输出${\cal L}$的一个三角化格基${{T}}$。特别地，${{T}}$的对角线为${\cal L}$上格基的Smith标准型。

证明　根据算法1和算法2，定理的第1部分是正确的。

对于定理的第2部分，利用引理7来证明。根据T的结构，可知${{{T}}_{{i}}} = {{{H}}_{{i}}} + \displaystyle\mathop \sum \nolimits_{k = i + 1}^n {{{H}}_k}$。由引理7，${t_{ii}} = {h_{ii}}|{h_{jk}}$，其中$i \le j \le k \le n$,所以${t_{ii}}|{{{T}}_{{i}}}$。然后利用矩阵的初等列变换可知${{T}}$的对角线正好构成${\cal L}$上格基的Smith标准型。 证毕

3.3   例子

根据本文的算法，给出一个例子来形象地表示算法过程。假设$f\left( x \right) = {x^8} + {x^6} - 3{x^4} - 3{x^3} + 8{x^2} +$$2x - 5$, $g\left( x \right) = 3{x^6} + 5{x^4} - 4{x^2} - 9x + 21$。利用算法1，得到本原格向量如式(9)

这里${n_1} = 4$, ${n_2} = 2$, ${n_3} = 1$, ${n_4} = 0$。然后利用算法2，得到

于是一个三角化矩阵为

并且Smith标准型为

4.   快速计算Hermite标准型

这一节说明怎么在$O\left( {{n^3}{{\log }_2}B} \right)$时间内计算一类特殊的理想格的Hermite标准型。事实上，这一类特殊的理想格的Hermite标准型是具有简单形式的。

同样，计算是基于文献[11]中发现的理想格的性质。对于具有简单Hermite标准型的理想格，其Hermite标准型可以隐式地由两个整数$(d,r)$来表示，其中$d$为理想格的行列式，$r = - {h_{\left( {n - 1} \right)n}}$。而唯一非平凡的列是最后一列，且${h_{in}} = {r^{n - i}}{\rm{mod}} \;d$，对于$i = 1,2, ··· ,n - 1$。所以最后一列可以在$O\left( {{n^3}{{\log }_2}B} \right)$时间内平凡地计算出来。但是目前还不清楚对于Hermite标准型为一般形式的理想格怎么来加速计算过程，这也将是下一步的研究内容。

5.   结论

本文通过利用理想格本身特殊的多项式结构，提出了一个新的算法可以在$O\left( {{n^3}{{\log }_2}B} \right)$时间内对理想格格基进行三角化，并且利用理想格上Hermite标准型的特殊性质，同样可以在$O\left( {{n^3}{{\log }_2}B} \right)$内计算出Smith标准型。最后，针对某一类应用于密码学的理想格，可以在$O\left( {{n^3}{{\log }_2}B} \right)$时间内计算出Hermite标准型。