Gröbner基方法入门第III部分:Gröbner基方法的应用

Gröbner基理论是一种在国外被普遍认同的用于求解多变元高次方程系统的有效算法,其概念最早由Buchberger提出.其本质是从多项式环中任意理想的生成元出发,刻画和计算出一组具有“好的”性质的生成元,进而研究理想的结构并进行某些理想运算;由于数学、科学和工程学中的许多问题都可以用多元多项式方程组表示(例如,理想,模块和矩阵),Gröbner基的代数算法在理论物理学、应用科学和工程学中具有广泛的应用;

---

计算多项式理想

让我们先来了解如何用Gröbner基来计算多项式理想;

判定任给多项式是否属于一个给定生成元的理想，

• $♡$定理3.1:
  设$\mathbb{P}$为 $\mathcal{K}[\mathbf{x}]$ 中的多项式组,而$\mathbb{G}$为 $\mathbb{P}$ 的 Gröbner 基,则对任意多项式 $P\in \mathcal{K}[\mathbf{x}]$:

$$P\in ⟨\mathbb{P}⟩⟺\mathrm{nform}(P,\mathbb{G})=0$$

• $♡$定理3.2:
  设$\mathbb{P}$和$\mathbb{Q}$为$\mathcal{K}[\mathbf{x}]$ 中的多项式组,而$\mathbb{G}$为$\mathbb{P}$的Gröbner基,则:

⟨Q⟩⊂⟨P⟩⟺nform⁡(Q,G)={0}\langle\mathbb{Q}\rangle \subset\langle\mathbb{P}\rangle \Longleftrightarrow \operatorname{nform}(\mathbb{Q}, \mathbb{G})=\{0\}⟨Q⟩⊂⟨P⟩⟺nform(Q,G)={0}

• $\star$例3.3(判定理想$I$的成员问题):
  令$I=⟨f_1,f_2⟩=⟨xz-y^2,x^3-z^2⟩\in \mathbb{C}[x,y,z]$,并且使用grlex项序.取$f=-4x^2{y}^2{z}^2+y^6+3z^5$.我们感兴趣的是是否有$f\in I$.

计算其Gröbner基:
$$G=\left(f_1,f_2,f_3,f_4,f_5\right)=\left(xz-y^2,x^3-z^2,x^2{y}^2-z^3,x{y}^4-z^4,y^6-z^5\right)$$

现在可以判定$I$的成员.比如,使用上述$G$来约化$f$,我们发现:

$$f=\left(-4x{y}^{2}z-4y^4\right)\cdot f_1+0\cdot f_2+0\cdot f_3+0\cdot f_4+(-3)\cdot f_5+0$$

因为其余数为$0$,可以判定$f\in I$.

应用概括

在数学和应用科学的许多不同领域中,有许多问题都可以使用Grobner基础解决.在这里,我们仅列出一些应用问题:

• 多项式方程组的求解系统,例如相交的曲面和曲线,找到曲线上或曲面上最接近给定点的点,Lagrange乘子问题(尤其是那些具有多个乘子的问题)等.这些问题的解决方案基于所谓的扩展理论.参见文献[1]

• 为等距​​曲线和曲面找到到由多项式方程定义的曲线和曲面的方程,例如圆锥截面,Bezier三次方程;在各种多项式集合之间找到syzygy关系,例如对称多项式,有限组不变式,插值函数等.这些问题的解决方案基于所谓的消除理论.参见文献[1]

• 找到等距的曲线和曲面作为相应曲线和曲面族的包络.参见文献[2,1]

• 隐式化问题,即消除参数并找到曲线和曲面的隐式形式.

• 机器人技术中的正向运动学和逆向运动学问题.参见文献[3,1]

• 自动几何定理证明.参见文献[3,4,1]

• 根据生成不变式表达有限组的不变式.参见文献[1]

• 查找多项式函数之间的关系,例如插值函数(Syzygy关系).

• 有关大地测量学的最新应用.参见文献[5]

• 另请参见约翰·拉顿计算与应用数学研究所(RICAM)的Grobner基地书目.参见文献[6]

一些例子

代数曲面

• $\star$例3.4:
  令$S_1$和$S_2$为多项式$f_1$和$f_2$所定义的球面:

$$f_1=4{\left(x_1-1\right)}^2+4x_2^2+4x_3^2-9,f_2={\left(x_1+1\right)}^2+x_2^2+x_3^2-4$$

也就是说 $S_1=\mathbf{V}\left(f_1\right)$并且$S_2=\mathbf{V}\left(f_2\right)$.那么,理想$J$的一个使用项序$x>y>z$生成的约化的Gröbner基为

$$G=\left\{256x_2^2+256x_3^2-495,16x_1-7\right\}$$

此处第一个多项式$c$给出了圆柱面$\mathbf{V}(c)$而第二项给出了平面$\mathbf{V}(\pi )$.如此一来,曲线$C=S_1\cap S_2=\mathbf{V}(c)\cap \mathbf{V}(\pi )$可以用两种方式可视化出来:

i) 两个球面相交的方式(图左);
ii) 圆柱面和平面相交的方式(图右);

机器人

• $\star$例3.5(机械手臂动作规划):
  我们建模一个CGA作为一个5-D实向量空间$V$的Clifford代数,这是3-D Euclidean空间的一个原点无穷大平面的扩张.令{e1,e2,e3,e4,e5}\left\{\mathbf{e}_{1}, \mathbf{e}_{2}, \mathbf{e}_{3}, \mathbf{e}_{4}, \mathbf{e}_{5}\right\}{e1​,e2​,e3​,e4​,e5​}是空间$V$的基向量族,并且在CGA中满足下列约束关系:

$${\mathbf{e}}_i^2=1,{\mathbf{e}}_i\cdot {\mathbf{e}}_j={\mathbf{e}}_j\cdot {\mathbf{e}}_i=0,{\mathbf{e}}_i\cdot {\mathbf{e}}_4={\mathbf{e}}_i\cdot {\mathbf{e}}_5=0,{\mathbf{e}}_4^2={\mathbf{e}}_5^2=0,{\mathbf{e}}_4\cdot {\mathbf{e}}_5=-1$$

进一步的方式表示以上约束有:

$$P=\mathbf{p}+\frac{1}{2}{\mathbf{p}}^2{e}_{\infty }+e_0,S=\mathbf{s}+\frac{1}{2}\left({\mathbf{s}}^2-r^2\right)e_{\infty }+e_0,\pi =\mathbf{n}+d{e}_{\infty }$$

这儿$\mathbf{p}$是3-D点位置, $\mathbf{s}$是3-D球面球心而$\mathbf{r}$是球半径.$\mathbf{n}$是3-D平面的单位向量, $d$是平面距离原点的距离.

值得注意的是,以上是约束方程,也就是机械手臂无论怎么动都必须满足的方程,我们还会引入目标方程,也就是希望机械手臂终端去触碰的轨迹,这时结合约束方程,就会得到一个非线性多项式方程组,其解即为操纵段的运动轨迹;比如需要求解:

$$C=S_1\wedge S_2=-\frac{17}{8}{\mathbf{e}}_1\wedge e_{\infty }+2{\mathbf{e}}_1\wedge e_0-\frac{7}{8}{e}_0\wedge e_{\infty }$$

写出其多项式方程组形式,再求这个方程组生成的理想$I$的Gröbner基我们得到:

$$\left\{-495+256r^2,c_3,c_2,-7+16c_1,n_3,n_2,n_1+2\right\}$$

最终我们解出得到${\mathbf{n}}_{\mathbf{c}}=(-2,0,0),\mathbf{c}=(0,0,0),$ and $r=\frac{\sqrt{5}}{2}$为所求;

密码分析的代数攻击

• $\star$例3.6:
  第一步就是需要用多项式来表征各种密码协议中的密码,比如S-Box的密码可以用一个非线性的多项式方程组来表征:

$$x_{m+j}^{(e)}+x_j^{(e-1)}+\sum _{l=1}^m{d}_{j,l}\cdot f\left(x_{m+l}^{(e-1)}+k_l^{(e-1)}\right)=0$$

那么很明显我们就是想解出某个约束方程组(先将上面这个方程组记为P={pi=0}\mathcal{P}=\left\{p_{i}=0\right\}P={pi​=0}),就会用到Gröbner基方法;现在考虑我们有一个明文/密文序列对$\left(\left(P_1,\dots P_t\right),\left(C_1,\dots ,C_t\right)\right)$,自然得到下列方程集合G={gi=0}\mathcal{G}=\left\{g_{i}=0\right\}G={gi​=0}:

$$\begin{array}{ll}{x}_1^{(0)}+P_1=0& x_1^{(r)}+C_1=0\\ ⋮& ⋮\\ x_t^{(0)}+P_t=0& x_t^{(r)}+C_t=0\end{array}$$

现在令$\mathfrak{I}$是多项式集合L=(⋃i{pi})∪(⋃i{gi})\mathcal{L}=\left(\bigcup_{i}\left\{p_{i}\right\}\right) \cup\left(\bigcup_{i}\left\{g_{i}\right\}\right)L=(⋃i​{pi​})∪(⋃i​{gi​})生成的理想,称之为密钥恢复理想.

聪明的读者到此处应该已经知道了,我们就是要求$\mathfrak{I}$的Gröbner基$G_{DRL}$,然后再回到之前列方程集合G={gi=0}\mathcal{G}=\left\{g_{i}=0\right\}G={gi​=0}再尝试求解的过程,如此就能恢复密钥;

---

总结

Gröbner基方法属于代数几何和交换代数偏应用的、计算机算法色彩比较浓厚的一个方向,由于其可用性、理论深度兼具,因此非常值得学习,特别是针对有志于用代数工具和思维解决工程实际问题的研究人员来说,更应该掌握;

(完结)

---

[1] D. Cox, J. Little, D. O’Shea, Ideals, Varieties, and Algorithms: An Introduction to Computational Algebraic Geometry and Commutative Algebra. (Springer, New York, 2008)
[2] R. Abłamowicz, J. Liu, On the Parallel Lines for Nondegenerate Conics, Department of Mathematics, TTU, Tech. Report No. 2006-1, January 2006, March 18, 2009
[3] B. Buchberger, in Proc. Marktoberdorf Summer School 1995. (Springer, 1997)
[4] B. Buchberger, F. Winkler, Gr ¨obner Bases and Applications, eds. (Cambridge University Press, 1998)
[5] J. L. Awange, E. W. Grafarend, Solving Algebraic Computational Problems in Geodesy and Geoinformatics. (Springer, Berlin, 2005)
[6] Grobner Basis Bibliography at Johann Radon Institute for Computational and Applied Mathematics (RICAM),March 18, 2009