Gröbner 基学习

虽然一直在用 Ideal.groebner_basis() 来解方程组，但其实一直都不太清楚什么是理想、什么是 Gröbner 基.今天稍微学习一下.因为我只学过工科《线性代数》，没有系统学习过更高级的代数，在这里尽可能用类比的方式去理解一些概念，不去管严谨性了.

多项式的理想

设 $R$ 是一个环， $R[x]$ 是以 $x$ 为变量的多项式环. 一个理想 $I$ 是 $R[x]$ 的一个子集，满足以下两个条件：

如果 $f(x) \in I$ 且 $g(x) \in I$ ，则 $f(x) + g(x) \in I$ （加法封闭性）
如果 $f(x) \in I$ 且 $h(x) \in R[x]$ ，则 $h(x) \cdot f(x) \in I$ （乘法封闭性）

Hilbert 基定理

对于给定的多项式集合 $f_1(x), f_2(x), \dots, f_n(x)$ ，可以定义一个 由这些多项式生成的理想，记作： $\langle f_1(x), f_2(x), \dots, f_n(x) \rangle$ 该理想包含所有可以表示为 $a_1(x) \cdot f_1(x) + a_2(x) \cdot f_2(x) + \dots + a_n(x) \cdot f_n(x)$ 的多项式，其中 $a_1(x), a_2(x), \dots, a_n(x) \in R[x]$ .

Hilbert 基定理 的表述如下：

如果 $R$ 是诺特环，那么 $R[x]$ 也是诺特环.

诺特环是满足 升链条件 的环. 升链条件是说 $R$ 中的任意升链的理想最终稳定，即对于任意理想序列

I_1 \subseteq I_2 \subseteq I_3 \subseteq \cdots

存在一个正整数 $N$ ，使得当 $n \geq N$ 时 $I_n = I_{N}$ . 换句话说，理想的升链不可能无限延伸.

而这个升链条件和 有限生成性 是等价的. 有限生成性是说 $R$ 中的每个理想都是 有限生成 的，即对于 $R$ 中任意理想 $I$ ，存在有限个元素 $f_1, f_2, \dots, f_n \in I$ ，使得

I =\langle f_1, f_2,\cdots, f_n \rangle

CTF Crypto 常研究的整数环 $\mathbb{Z}$ 或域 $K$ 都是诺特环. 有限生成性保证了我们可以用多项式去生成理想：

sage
x,y = QQ['x,y'].gens()
f1 = 2 * x + 3 * y - 5
f2 = 3 * x + 4 * y - 2
I = ideal(f1,  f2)
I
# Ideal (2 *x + 3* y - 5, 3 *x + 4* y - 2) of Multivariate Polynomial Ring in x, y over Rational Field

求出这个理想 I 有什么用呢？

Hilbert 零点定理

首先介绍两个概念：零点集 和 零化理想.

零点集（Variety）：给定一个多项式理想 $I \subset R = K[x_1, x_2, \dots, x_n]$ （ $K$ 是一个域），我们定义 $I$ 的 零点集（也称代数簇）为在 $I$ 中所有多项式同时为零的点的集合.

V(I) = \{ (a_1, a_2, \dots, a_n)\in K^n \mid f(a_1, a_2, \dots, a_n)= 0 \text{ for all } f \in I\}

零化理想（Vanishing Ideal）：给定一个点集 $S \subset K^n$ ，我们可以定义 零化理想 为包含所有在 $S$ 上取零的多项式的集合.

I(S) = \{ f \in R \mid f(a_1, a_2, \dots, a_n) = 0 \text{ for all } (a_1, a_2, \dots, a_n) \in S \}

零点集和零化理想在代数几何中形成了一个重要的 对应关系，称为 Hilbert 零点定理（Hilbert’s Nullstellensatz）. 该定理描述了代数方程的解集与代数结构之间的关系，特别是在代数闭域（如复数域 $\mathbb{C}$ ）上. 主要有以下两个方向的对应关系：

从理想到零点集：给定理想 $I \subset R$ ，可以找到其零点集 $V(I)$ . $V(I)$ 表示了所有在 $I$ 中的多项式的公共解集.
从点集到零化理想：给定一个点集 $S \subset K^n$ ，可以构造零化理想 $I(S)$ ，表示所有在 $S$ 上取值为零的多项式.

这里就不贴 Hilbert 零点定理的具体定义了. 作为 CTF Crypto 玩家，我们最关心的是什么呢？

「给定理想 $I \subset R$ ，可以找到 其零点集 $V(I)$ 」，意味着我们可以用它来解方程！

试试看：

定义多项式环
R = PolynomialRing(QQ, 'x, y')
x, y = R.gens()

# 定义理想
I = R.ideal([x^2 - 1, y^2 - 1])

# 计算零点集
solutions = I.variety()
solutions
# [{y: 1, x: 1}, {y: 1, x: -1}, {y: -1, x: 1}, {y: -1, x: -1}]

一个有限解的方程组，对应的理想有什么特点呢？我们不妨去掉一个多项式看看：

定义多项式环
R = PolynomialRing(QQ, 'x, y')
x, y = R.gens()

# 定义理想
I = R.ideal([x^2 - 1])

# 计算零点集
solutions = I.variety()
solutions
# ValueError: The dimension of the ideal is 1, but it should be 0

报错了. 这里的 dimension 是什么意思呢？在《线性代数》中，我们学习过线性方程组 解空间 的概念. 解空间的维度，也称为 自由度. 不同维度解空间的几何意义很明显：

零维解空间：如果方程组有唯一解，那么解空间是一个点，没有自由度
一维解空间：如果解空间是一条直线，则表示有一个自由度
二维或更高维解空间：如果解空间是一个平面或更高维的超平面，表示有多个自由度

同样的，我们用理想的维度是描述该理想所对应的几何对象的自由度或维数.

零维理想，它对应的 零点集是离散的点集，没有自由度
它的零点集可能是有限个孤立的解点，而不是「一条曲线」或者「一个曲面」

尝试用这个方法去解一些 CTF Crypto 题，我们会发现，如果把上面的 QQ 换成 ZZ 或是 Zmod(N)，使用 I.variety()，会产生报错：

ValueError: Coefficient ring must be a field for function 'variety'.

我们需要更强大的工具.

Gröbner 基

回忆一下，在多项式环中，我们知道理想是 有限生成 的，意味着我们可以找到一个有限生成元的集合作为理想的「基」.

什么是基？在《线性代数》中，我们学过：在向量空间中，基是一个由向量组成的集合，通过它可以生成整个向量空间. 向量空间的基具有以下两个特性：

线性无关性：基中的向量不能通过其他向量线性表示.
生成性：基中的向量的线性组合可以生成空间中的任意向量. 例如，对于 $\mathbb{R}^3$ 空间，一个基可以是 ${(1, 0, 0), (0, 1, 0), (0, 0, 1)}$ . 任何向量 $(x, y, z) \in \mathbb{R}^3$ 都可以通过基向量的线性组合表示出来：

在多项式环中，一个 理想的基 是一个生成集合，使得理想中的所有元素都可以通过这个集合的线性组合和多项式乘积表示. 这里同样不贴具体定义了，我们可以直接用向量空间的基来类比理解.

	向量空间的基	多项式理想的基
空间	向量空间（如 $\mathbb{R}^n$ ）	多项式环中的理想
基	线性无关的向量	多项式
生成性	基中的向量的线性组合可以生成空间中的所有向量	基中的多项式的线性组合和乘积可以生成理想中的所有多项式
操作	线性组合	多项式的线性组合和乘法

而所谓的 Gröbner 基 可以看作是多项式理想的「标准化基」，类似线性代数中的「行阶梯形矩阵」. Gröbner 基满足一些特殊的性质，这些性质使得我们可以用它来简化多项式在 $I$ 中的表示和操作. 要定义 Gröbner 基还需要一些概念：

初始项，是在多项式中，按照某种项序排列后，系数不为零的 最大项. 比如说多项式 $3x_2^2+5x_1x_2+7x_1^2+11x_1+13_x2+17$ 的初始项是 $3x_2^2$ . 你可能会问，凭什么把多项式写成这个样子？如果写成 $7x_1^2+5x_2x_1+3x_2^2+13_x2+11x_1+17$ 初始项不就是 $7x_1^2$ 了吗？因此，在讨论之前，我们必须要规定多项式的项序 $\prec$ ，在 SageMath 中，我们定义多项式环的时候可以指定项序为 order='lex'（字典序）或 order='deglex'（总次序字典序）.

初始理想 $in(I)$ ，是由理想 $I$ 中所有多项式的 初始项 生成的理想 $in(I)=\langle in(f):f\in I\rangle$ 而这个初始理想不是只有这一种生成方法. 如果一个 $I$ 的有限子集 $\mathcal{G}$ 中的初始项足以生成初始理想 $in(I)=\langle in(g):g\in \mathcal{G}\rangle$ 则 $\mathcal{G}$ 是一个 Gröbner 基. Gröbner 基的定义并没有要求「极小」，所以包含 $\mathcal{G}$ 的任何 $I$ 的子集实际上也是 Gröbner 基. 不过我们总是想知道「极小」的那个，所以定义 约化（reduced）基，满足额外条件

唯一性：基中的每个多项式的首项（leading term）系数是 1
不可约性：基中的每个多项式的首项不能被其他基中的多项式首项整除

我们之前说过， Gröbner 基类似线性代数中的「行阶梯形矩阵」. 而《线性代数》中，如果线性方程组的解空间维度为 0，那么可以通过高斯-若尔当消元法，将增广矩阵行变换为「行最简形」矩阵，形如：

\begin{bmatrix} 1 & 0 & 0 & 2 \\ 0 & 1 & 0 & -1 \\ 0 & 0 & 1 & 3 \\ \end{bmatrix}

我们可以直接读出以上方程的解是 $x=2,y=-1,z=3$ . 而 Gröbner 约化基的两个性质决定了，如果我们的理想是零维的，理论上求出的 Gröbner 基应当类似「行最简形」矩阵，形如：

(x-2, y+1, z-3)

1965 年，Bruno Buchberger 提出了计算 Gröbner 基的算法. 在 SageMath 中可以直接计算 Gröbner 约化基，用到的就是这一算法（加上约化的步骤）：

I.groebner_basis()

下面以一个简单的 RSA 问题作为例子：

from Crypto.Util.number import *

p, q = getPrime(256), getPrime(256)
N = p * q
m1 = bytes_to_long(b"flag{12345678901234567890")
m2 = bytes_to_long(b"1234567890123456789012345")
m3 = bytes_to_long(b"6789012345678901234567890}")
e = 17
c1 = pow(m1, e, N)
c2 = pow(m2, e, N)
c3 = pow(m3, e, N)
s = m1 + m2 + m3
print(c1, c2, c3, s)

现在我们有 Zmod(N) 下四个多项式 $x^{17}-c_1,y^{17}-c_2,z^{17}-c_3,x+y+z-s$ ，由于多项式的数量和变量数量相等，也不存在冗余，它们生成的理想是零维的. 怎么求解零点集呢？求这四个多项式生成的理想的 Gröbner 约化基看看：

R = PolynomialRing(Zmod(N), 'x, y, z')
x, y, z = R.gens()
I = Ideal([x^e - c1, y^e - c2, z^e - c3, s - x - y - z])
for g in I.groebner_basis():
    print(g)

输出如下

x + 5974809440284492118398340740115081791644292019379820874909382967923162606074068591903366215264267350207409678964865715475401589302388454632868287701112821
y + 5974809440284492118398340740115081791644292019379820874909382967923162606074068591903366215264601463180355418414350632064321191429229742673837799458069744
z + 5974809440284492118398340740115081791644292019379820874909382967923162606074068591903366215177788998487202319109154974611609201086171175247580719929614504

对 Gröbner 约化基中的每一个多项式的常数项，在模 N 下取相反数，就得到了这四个多项式生成的理想的零点集.