密码分析中的格罗布纳基 第一部分：基础代数

目录

• 多项式环和仿射簇
• 理想
• 单项式序
• 多变量除法算法
• Gröbner Bases
• S-polynomial和Buchberger's Algorithm
• 极小和约化的Gröbner Bases
• 使用Gröbner Basis求解多项式系统

一个Gröbner basis是具有强大计算性质的多项式理想的规范生成集。给定一个多项式方程组，计算一个关于lexicographic单项式序的Gröbner basis可以将其简化为一系列单变量多项式，这些多项式可以通过标准求根方法求解。

这是关于对算术化导向密码（arithmetization-oriented ciphers）进行Gröbner basis攻击的两部分文章的第一部分。算术化导向密码是一类为在零知识证明系统内部使用而设计的哈希函数。第一部分构建了必要的代数机制：Gröbner basis是什么，如何计算，以及为什么它能解决多项式系统。第二部分将展示哈希函数如何成为一个多项式系统，以及该机制如何破解它。

本文中的定义和定理遵循Cox、Little和O'Shea的《Ideals, Varieties, and Algorithms》（第4版，Springer, 2015）。第1章和第2章涵盖了本文中的所有材料。

多项式环和仿射簇

起点是精确地定义多项式方程组及其解集。

定义。 设 $k$ 是一个域，$x_1, \ldots, x_n$ 是不定元。 $x_1, \ldots, x_n$ 中的一个单项式是形如以下形式的积：

$$x^\alpha = x_1^{\alpha_1} x_2^{\alpha_2} \cdots x_n^{\alpha_n}, \qquad \alpha = (\alpha_1, \ldots, \alphan) \in \mathbb{Z}{\geq 0}^n.$$

$x^\alpha$ 的总次数是 $|\alpha| = \alpha_1 + \cdots + \alpha_n$。一个关于 $x_1, \ldots, x_n$ 且系数在 $k$ 中的多项式 $f$ 是单项式的有限 $k$-线性组合：

$$f = \sum{\alpha} c\alpha x^\alpha, \qquad c_\alpha \in k.$$

所有此类多项式的集合，配备通常的加法和乘法，形成一个交换环，记作 $k[x_1, \ldots, x_n]$，称为 $n$ 个变量上系数在 $k$ 中的多项式环。

多项式方程组的解集是我们需要的基本几何对象。

定义。 设 $f_1, \ldots, f_s \in k[x_1, \ldots, x_n]$。由 $f_1, \ldots, f_s$ 定义的仿射簇是所有公共零点的集合：

$$V(f_1, \ldots, f_s) = { (a_1, \ldots, a_n) \in k^n \mid f_i(a_1, \ldots, a_n) = 0 \text{ for all } i = 1, \ldots, s }.$$

例子。 在 $\mathbb{R}^2$ 中，簇 $V(x_1^2 + x_2^2 - 1)$ 是单位圆。簇 $V(x_1 - x_2, x_1^2 - 1)$ 是有限集 ${(1,1),(-1,-1)}$。

理想

一个多项式方程组可以用许多不同的多项式集合来描述。将任何 $f_i$ 乘以一个任意多项式 $h$，或者用 $f_1 + h \cdot f_2$ 替换 $f_1$，都不会改变解集。这表明解集不取决于所选择的特定生成元，而是取决于它们生成的更大的代数对象。那个对象就是一个理想。

定义。 子集 $I \subseteq k[x_1, \ldots, x_n]$ 是一个理想，如果：

1. $0 \in I$，
2. $f, g \in I \Rightarrow f + g \in I$，
3. $f \in I, h \in k[x_1, \ldots, x_n] \Rightarrow hf \in I$。

定义。 给定 $f_1, \ldots, f_s \in k[x_1, \ldots, x_n]$，由 $f_1, \ldots, f_s$ 生成的理想是

$$\langle f_1, \ldots, fs \rangle = \left{ \sum{i=1}^{s} h_i f_i \;\middle|\; h_i \in k[x_1, \ldots, x_n] \right}.$$

这是包含 $f_1, \ldots, f_s$ 的最小理想。

关键的观察是，同一理想的不同生成集定义了相同的簇。这从簇的定义来看并不明显，但从理想结构中可以立即得出。

引理。 如果 $\langle f_1, \ldots, f_s \rangle = \langle g_1, \ldots, g_t \rangle$，那么 $V(f_1, \ldots, f_s) = V(g_1, \ldots, g_t)$。

这个引理意味着我们可以自由地用任何其他生成集（包括Gröbner basis）替换一个理想的任何生成集，而不会改变簇。使用一个方便的生成集来求解系统等同于使用原始生成集来求解系统。

我们还记录了与给定簇相关的理想，它将出现在域方程的构建中。

定义。 给定一个仿射簇 $V \subseteq k^n$，$V$ 的理想是

$$I(V) = { f \in k[x_1, \ldots, x_n] \mid f(a) = 0 \text{ for all } a \in V }.$$

理想 $I(V)$ 捕捉了在 $V$ 上消失的所有多项式关系，并且通常严格大于用于定义 $V$ 的任何特定生成集 $\langle f_1, \ldots, f_s \rangle$。

单项式序

为了在 $k[x_1, \ldots, x_n]$ 中进行多项式计算，我们需要一个前导项的概念：在执行多项式除法时，我们试图首先抵消的项。在单变量情况下，前导项就是次数最高的项。在多变量情况下，没有单一的自然选择，不同的选择会导致具有不同性质的Gröbner basis。

定义。 $k[x_1, \ldots, x_n]$ 上的单项式序 是单项式集合上的全序 $>$，满足：

1. 如果 $x^\alpha > x^\beta$，那么对于所有 $\gamma \in \mathbb{Z}_{\geq 0}^n$，都有 $x^\alpha \cdot x^\gamma > x^\beta \cdot x^\gamma$，
2. $>$ 是一个良序：每个非空单项式集合都有一个最小元素。

条件2意味着在任何单项式序下 $1 = x^{(0,\ldots,0)}$ 是最小的单项式，并且与条件1一起保证任何约化序列最终都会终止。

实践中有三种序。它们的计算和结构性质差异显著，序的选择对攻击效率至关重要。

定义 (lexicographic order, lex)。 如果 $\alpha - \beta \in \mathbb{Z}^n$ 的最左边非零项是正的，则 $x^\alpha >_{\mathrm{lex}} x^\beta$。

例子。 在 $k[x_1, x_2, x_3]$ 中：$x_1^2 x3 >{\mathrm{lex}} x_1 x2^5 >{\mathrm{lex}} x_2^4 x_3^2$。变量 $x_1$ 无条件支配，无论 $x_2$ 和 $x_3$ 的次数如何。这使得lex order的行为像字典一样，也正是这个性质使其适合消元：一个lex Gröbner basis将包含仅涉及 $x_2, x_3$ 的元素，然后是仅涉及 $x_3$ 的元素，从而允许我们一次一个变量地求解系统。

定义 (graded lexicographic order, grlex)。 如果 $|\alpha| > |\beta|$，或者如果 $|\alpha| = |\beta|$ 且 $x^\alpha >{\mathrm{lex}} x^\beta$，则 $x^\alpha >{\mathrm{grlex}} x^\beta$。

例子。 在 $k[x_1, x_2, x_3]$ 中：$x_1 x_2 x3 >{\mathrm{grlex}} x_1^2 x_3$，因为 $|\alpha| = 3 > 2 = |\beta|$。首先比较总次数；lex打破平局。

定义 (graded reverse lexicographic order, grevlex)。 如果 $|\alpha| > |\beta|$，或者如果 $|\alpha| = |\beta|$ 且 $\alpha - \beta$ 的最右边非零项是负的，则 $x^\alpha >_{\mathrm{grevlex}} x^\beta$。

例子。 在 $k[x_1, x_2, x_3]$ 中，在次数为2的单项式中：$x1^2 >{\mathrm{grevlex}} x_1 x2 >{\mathrm{grevlex}} x_1 x3 >{\mathrm{grevlex}} x2^2 >{\mathrm{grevlex}} x_2 x3 >{\mathrm{grevlex}} x_3^2$。

固定单项式序后，我们可以指定每个多项式的特殊项。

定义。 固定一个单项式序 $>$ 并设 $f = \sum\alpha c\alpha x^\alpha \neq 0$。

• $f$ 的多重度是 $\mathrm{multdeg}(f) = \max{>}{\alpha \mid c\alpha \neq 0}$。
• 前导单项式是 $\mathrm{LM}(f) = x^{\mathrm{multdeg}(f)}$。
• 前导系数是 $\mathrm{LC}(f) = c_{\mathrm{multdeg}(f)} \in k$。
• 前导项是 $\mathrm{LT}(f) = \mathrm{LC}(f) \cdot \mathrm{LM}(f)$。

例子。 对于 $f = 4x_1^2 x_2 + 3x_2^3 - x_1 \in \mathbb{Q}[x_1, x2]$ 在 $>{\mathrm{lex}}$ 下：$\mathrm{multdeg}(f) = (2,1)$，$\mathrm{LM}(f) = x_1^2 x_2$，$\mathrm{LC}(f) = 4$，$\mathrm{LT}(f) = 4x_1^2 x_2$。

多变量除法算法

有了前导项的概念，我们可以将多项式长除法推广到多变量情境。

定理。 固定一个单项式序 $>$ 和一个有序 $s$ 元组 $F = (f_1, \ldots, f_s)$。那么每个 $f \in k[x_1, \ldots, x_n]$ 都可以写成

$$f = a_1 f_1 + \cdots + a_s f_s + r$$

其中 $a_i, r \in k[x_1, \ldots, x_n]$， $r$ 的任何单项式都不能被任何 $\mathrm{LT}(f_i)$ 整除，并且当 $a_i f_i \neq 0$ 时，$\mathrm{multdeg}(f) \geq \mathrm{multdeg}(a_i f_i)$。多项式 $r$ 是 $f$ 被 $F$ 除的余式，记作 $\overline{f}^F$。

该算法贪婪地进行：在每一步，如果当前前导项可被某个 $\mathrm{LT}(f_i)$ 整除，则将其抵消；否则将其移至余式。

然而，这种推广有两个严重的缺陷，在单变量情况下不会出现。

首先，余式 $\overline{f}^F$ 不一定是唯一的：重新排序 $f_1, \ldots, f_s$ 会为相同的 $f$ 产生不同的余式。其次，更关键的是，$\overline{f}^F = 0$ 并不意味着 $f \in \langle f_1, \ldots, f_s \rangle$。一个多项式可能是一个理想的成员，但在被生成集除时未能约化为零，仅仅因为正确的抵消没有以正确的顺序发生。

这两个缺陷并非小问题。它们意味着任意生成集在计算上对于理想成员测试和系统求解是无用的。Gröbner bases正是定义为能消除这两个缺陷的生成集。

Gröbner Bases

在定义Gröbner basis之前，我们需要知道每个理想一开始就拥有有限生成集，否则“基”的概念将是模糊的。这就是Hilbert Basis Theorem的内容。

定理 (Hilbert Basis Theorem)。 每个理想 $I \subseteq k[x_1, \ldots, x_n]$ 都有一个有限生成集。

该证明使用了升链条件：任何理想链 $I_1 \subseteq I_2 \subseteq \cdots$ 最终必须稳定。这也将保证Buchberger's Algorithm（它逐步扩大一个生成集）总是会终止。

定义。 对于理想 $I \subseteq k[x_1, \ldots, x_n]$，前导项理想是

$$\mathrm{LT}(I) = \langle \mathrm{LT}(f) \mid f \in I, f \neq 0 \rangle.$$

前导项理想收集了 $I$ 中每个元素的前导项，而不仅仅是生成集中的元素。$\langle \mathrm{LT}(f_1), \ldots, \mathrm{LT}(f_s) \rangle$ 和 $\mathrm{LT}(I)$ 之间的差距正是导致除法算法失败的原因。Gröbner basis弥补了这个差距。

定义。 有限集合 $G = {g_1, \ldots, g_t} \subset I$ 是 $I$ 的一个Gröbner basis，如果

$$\langle \mathrm{LT}(g_1), \ldots, \mathrm{LT}(g_t) \rangle = \mathrm{LT}(I).$$

等价地，对于每个非零 $f \in I$，存在 $g_i \in G$ 使得 $\mathrm{LT}(g_i)$ 整除 $\mathrm{LT}(f)$。

每个非零理想都有一个Gröbner basis，并且每个Gröbner basis都是 $I$ 的一个生成集。以下两个引理证实Gröbner bases修复了之前识别出的两个缺陷。

引理。 设 $G$ 是 $I$ 的一个Gröbner basis。那么 $k[x_1, \ldots, x_n]$ 中的每个 $f$ 都有一个唯一的余式 $\overline{f}^G$，与除法算法中 $G$ 的元素顺序无关。这个余式称为 $f$ 相对于 $G$ 的范式，记作 $\mathrm{NF}(f, G)$。

引理。 设 $G$ 是 $I$ 的一个Gröbner basis。那么

$$f \in I \iff \overline{f}^G = 0.$$

这两个引理共同说明，一旦我们有了一个Gröbner basis，理想成员测试就变成了一个确定性的单一计算。由于我们知道 $V(G) = V(I)$，我们可以用一个Gröbner basis替换任何生成集，并求解生成的系统。

S-polynomial和Buchberger's Algorithm

为了计算Gröbner basis，我们需要一个判据来检测给定的生成集是否已经是一个Gröbner basis。关键的观察是，生成集不能成为Gröbner basis的唯一方式是它的某些元素组合产生了一个多项式，其前导项不能被任何生成元的前导项整除。S-polynomial旨在精确地暴露这些组合。

定义。 设 $f, g \in k[x_1, \ldots, x_n]$ 非零，其中 $\alpha = \mathrm{multdeg}(f)$ 且 $\beta = \mathrm{multdeg}(g)$。设 $x^\gamma = \mathrm{lcm}(\mathrm{LM}(f), \mathrm{LM}(g))$，其中 $\gamma_i = \max(\alpha_i, \beta_i)$。$f$ 和 $g$ 的S-polynomial是

$$S(f,g) = \frac{x^\gamma}{\mathrm{LT}(f)} \cdot f - \frac{x^\gamma}{\mathrm{LT}(g)} \cdot g.$$

$f$ 和 $g$ 的前导项通过构造抵消，产生一个次数严格更低的多项式。如果这个多项式在模当前生成集下约化为零，它就不会给理想贡献任何新东西，也不需要新的生成元。如果它不约化为零，它的余式是一个新的理想元素，其前导项在 $\langle \mathrm{LT}(G) \rangle$ 中缺失，证明 $G$ 尚未成为Gröbner basis。

例子。 设 $f = x_1^3 - 2x_1 x_2$ 和 $g = x_1^2 x_2 - 2x_2^2 + x_1$ 在 $\mathbb{Q}[x_1, x2]$ 中，在 $>{\mathrm{lex}}$ 下。那么 $\mathrm{lcm}(\mathrm{LM}(f), \mathrm{LM}(g)) = x_1^3 x_2$，且

$$S(f,g) = x_2 \cdot f - x_1 \cdot g = -2x_1 x_2^2 - x_1^2 + 2x_2^3.$$

定理 (Buchberger's Criterion)。 理想 $I$ 的一个生成集 $G = {g_1, \ldots, g_t}$ 是一个Gröbner basis当且仅当

$$\overline{S(g_i, g_j)}^G = 0 \quad \text{for all } i \neq j.$$

这个判据直接产生了一个算法：从给定的生成元开始，计算所有S-polynomial对，将任何非零余式添加为新的生成元，并重复直到没有新的生成元出现。

Buchberger's Algorithm。

输入： $F = {f_1, \ldots, f_s}$

输出： 一个Gröbner basis $G \supseteq F$

设置 $G := F$

重复：

\quad 设置 $G' := G$

\quad 对于每个对 ${p, q} \subseteq G'$：

\quad\quad 计算 $r := \overline{S(p,q)}^{G'}$

\quad\quad 如果 $r \neq 0$，设置 $G := G \cup {r}$

直到 $G = G'$

返回 $G$

终止性遵循升链条件：每个非零余式都严格扩大了 $\langle \mathrm{LT}(G) \rangle$，并且这个链必须稳定。

极小和约化的Gröbner Bases

Buchberger's Algorithm终止时会得到一个Gröbner basis，但通常包含冗余元素。我们分两步将其缩小。

定义。 Gröbner basis $G$ 是极小的，如果 $G$ 中的每个 $p$ 都是首一的，并且 $\mathrm{LT}(p) \notin \langle \mathrm{LT}(G \setminus {p}) \rangle$。

定义。 Gröbner basis $G$ 是约化的，如果 $G$ 中的每个 $p$ 都是首一的，并且 $p$ 中的任何单项式都不能被 $G$ 中任何其他 $q$ 的 $\mathrm{LT}(q)$ 整除。

约化的Gröbner basis是通过首先移除冗余元素使其极小，然后将每个剩余元素模其他元素完全约化而从任何Gröbner basis获得的。结果是唯一的。

定理。 固定一个单项式序。每个非零理想 $I \subseteq k[x_1, \ldots, x_n]$ 都有一个唯一的约化Gröbner basis。

这种唯一性意味着约化的Gröbner basis是理想和所选序的规范不变量。当且仅当它们的约化Gröbner bases一致时，两个多项式系统生成相同的理想。对于我们的目的，它保证了计算是确定性的：无论Buchberger's Algorithm如何处理S-polynomial，最终的约化基总是相同的。

使用Gröbner Basis求解多项式系统

我们现在拥有所有的部分。以下过程求解域 $k$ 上的多项式方程组 $f_1 = \cdots = f_s = 0$。

步骤1：构建理想。 将系统收集到 $I = \langle f_1, \ldots, f_s \rangle \subset k[x_1, \ldots, x_n]$。找到 $V(I)$ 等同于找到 $V(f_1, \ldots, f_s)$。

步骤2：添加域方程。 如果 $k=\mathbb{F}_p$，那么 $\mathbb{F}_p$ 的每个元素都满足 $a^p - a = 0$。将域方程 $x_i^p - x_i$ 添加到每个变量的生成集中，将簇限制到 $\mathbb{F}_p^n$ 并确保理想是零维的，这意味着 $V(I)$ 是一个有限集。

步骤3：选择一个单项式序并计算一个Gröbner basis。 使用lex order应用Buchberger's Algorithm，将主要关注的变量放在前面。生成的基 $G$ 生成相同的理想并满足 $V(G) = V(f_1, \ldots, f_s)$。

步骤4：读出单变量多项式。 因为lex order尽可能积极地消除了前面的变量，Gröbner basis $G$ 将包含一个只涉及最后一个变量 $x_n$ 的元素 $g \in k[x_n]$。它在 $k$ 上的根是任何解中 $x_n$ 的唯一可能值。

步骤5：回代。 对于 $g$ 的每个根 $a_n$，将 $x_n = an$ 代入 $G$ 的其余元素中并重复：找到关于 $x{n-1}$ 的单变量多项式，提取其根，代入，并继续直到所有变量都被确定。完整的解集 $V(I)$ 被恢复。

例子

考虑在变量 $x > y > z$ 下 $\mathbb{Q}$ 上的以下系统：

$$ \begin{cases} f_1 = x + y + z - 6 = 0\ f_2 = x + 2y - z - 3 = 0\ f_3 = x^2 + y^2 + z^2 - 14 = 0 \end{cases} $$

计算Gröbner basis。 我们应用Buchberger's Algorithm，处理S-polynomial直到所有都约化为零。

$f_1$ 和 $f_2$ 的S-polynomial。 两者都有前导项 $x$，所以 $\mathrm{lcm}(\mathrm{LM}(f_1), \mathrm{LM}(f_2)) = x$，并且：

$$S(f_1, f_2) = f_1 - f_2 = (x + y + z - 6) - (x + 2y - z - 3) = -y + 2z - 3.$$

这在模 ${f_1, f_2, f_3}$ 下不约化为零，所以我们将 $g_1 = y - 2z + 3$ 添加到基中。

$f_1$ 和 $f_3$ 的S-polynomial。 这里 $\mathrm{LM}(f_1) = x$ 且 $\mathrm{LM}(f_3) = x^2$，所以 $\mathrm{lcm} = x^2$，并且：

$$S(f_1, f_3) = x \cdot f_1 - f_3 = xy + xz - 6x - y^2 - z^2 + 14.$$

我们将其在模当前基 ${f_1, f_2, f_3, g_1}$ 下约化。前导项 $xy$ 可被 $\mathrm{LT}(f_1) = x$ 整除，所以我们减去 $y \cdot f_1$：

$$xy + xz - 6x - y^2 - z^2 + 14 - y(x + y + z - 6) = xz - 6x - 2y^2 - yz + 6y - z^2 + 14.$$

前导项 $xz$ 再次可被 $\mathrm{LT}(f_1)$ 整除，所以我们减去 $z \cdot f_1$：

$$xz - 6x - 2y^2 - yz + 6y - z^2 + 14 - z(x + y + z - 6) = -6x - 2y^2 - 2yz + 6y - 2z^2 + 6z + 14.$$

前导项 $-6x$ 可被 $\mathrm{LT}(f_1)$ 整除，所以我们减去 $-6 \cdot f_1$：

$$ -6x - 2y^2 - 2yz + 6y - 2z^2 + 6z + 14 - (-6)(x + y + z - 6) = -2y^2 - 2yz + 12y - 2z^2 + 12z - 22. $$

除以 $-2$ 得到 $y^2 + yz - 6y + z^2 - 6z + 11$。前导项现在是 $y^2$，可被 $\mathrm{LT}(g_1) = y$ 整除。减去 $y \cdot g_1$：

$$y^2 + yz - 6y + z^2 - 6z + 11 - y(y - 2z + 3) = 3yz - 9y + z^2 - 6z + 11.$$

减去 $3z \cdot g_1$：

$$3yz - 9y + z^2 - 6z + 11 - 3z(y - 2z + 3) = -9y + 7z^2 - 15z + 11.$$

减去 $-9 \cdot g_1$：

$$ -9y + 7z^2 - 15z + 11 - (-9)(y - 2z + 3) = 7z^2 - 33z + 38. $$

当前基中没有元素的前导项能整除 $z^2$，所以这个余式是一个新的生成元：$g_2 = 7z^2 - 33z + 38$。

验证剩余的S-polynomial。 此时基是 $G = {f_1, f_2, f_3, g_1, g_2}$。我们必须检查所有剩余的对。其中七个可以立即被互素判据排除：如果两个多项式的前导单项式互素，它们的S-polynomial总是约化为零。

唯一非平凡的剩余对是 $(f_2, f_3)$。我们有 $\mathrm{lcm}(\mathrm{LM}(f_2), \mathrm{LM}(f_3)) = x^2$，所以：

$$S(f_2, f_3) = x \cdot f_2 - f_3 = 2xy - xz - 3x - y^2 - z^2 + 14.$$

通过 $f_1$ 约化三次以消除 $x$ 项：

$$\xrightarrow{-2y \cdot f_1} -xz - 3x - 3y^2 - 2yz + 12y - z^2 + 14$$

$$\xrightarrow{+z \cdot f_1} -3x - 3y^2 - yz + 12y - 6z + 14$$

$$\xrightarrow{+3 \cdot f_1} -3y^2 - yz + 15y - 3z - 4.$$

通过 $g_1$ 约化三次以消除 $y$ 项：

$$\xrightarrow{+3y \cdot g_1} -7yz + 24y - 3z - 4$$

$$\xrightarrow{+7z \cdot g_1} 24y - 14z^2 + 18z - 4$$

$$\xrightarrow{-24 \cdot g_1} -14z^2 + 66z - 76 = -2(7z^2 - 33z + 38) = -2g_2 \xrightarrow{+2 \cdot g_2} 0.$$

所有S-polynomial都约化为零，确认该基是一个Gröbner basis。

约化为极小形式。 当前的基是 ${f_1, f_2, f_3, g_1, g_2}$，前导项为 $x, x, x^2, y, 7z^2$。由于 $\mathrm{LT}(f_2) = x$ 可被 $\mathrm{LT}(f_1) = x$ 整除，并且 $\mathrm{LT}(f_3) = x^2$ 也可被 $\mathrm{LT}(f_1) = x$ 整除，因此 $f_2$ 和 $f_3$ 都是冗余的并被移除。将 $g_2$ 除以 7 使其首一，得到 $z^2 - \frac{33}{7}z + \frac{38}{7}$。极小基是：

$$ \left{ x + y + z - 6, \quad y - 2z + 3, \quad z^2 - \tfrac{33}{7}z + \tfrac{38}{7} \right}. $$

约化为约化形式。 我们将每个元素模其他元素完全约化，确保任何元素的任何单项式都不能被另一个元素的前导项整除。

对于 $f_1 = x + y + z - 6$：单项式 $y$ 可被 $\mathrm{LT}(g_1) = y$ 整除，所以我们减去 $g_1$：

$$f_1 - g_1 = (x + y + z - 6) - (y - 2z + 3) = x + 3z - 9.$$

没有剩余单项式可被 $y$ 或 $z^2$ 整除，所以这已完全约化。

对于 $g_1 = y - 2z + 3$：没有单项式可被 $\mathrm{LT}(f_1) = x$ 或 $\mathrm{LT}(g_2) = z^2$ 整除。无变化。

对于 $z^2 - \frac{33}{7}z + \frac{38}{7}$：没有单项式可被 $x$ 或 $y$ 整除。无变化。

在lex order下的约化Gröbner basis是：

$$ \begin{cases} x + 3z - 9 = 0\ y - 2z + 3 = 0\ z^2 - \tfrac{33}{7}z + \tfrac{38}{7} = 0 \end{cases} $$

这种三角结构是行阶梯形的多项式类比。变量 $x$ 已从第二个和第三个方程中消除，变量 $y$ 已从第三个方程中消除。这就是Elimination Theorem的作用。

步骤4：求解单变量多项式。 第三个方程只涉及 $z$：

$$z^2 - \tfrac{33}{7}z + \tfrac{38}{7} = 0 \implies 7z^2 - 33z + 38 = (7z - 19)(z - 2) = 0$$

得到 $z=2$ 或 $z=\tfrac{19}{7}$。

步骤5：回代。 对于 $z$ 的每个值，代入第二个方程求 $y$，然后代入第一个方程求 $x$。

情况 $z=2$：

$$y - 2(2) + 3 = 0 \implies y = 1.$$

$$x + 3(2) - 9 = 0 \implies x = 3.$$

解：$(x, y, z) = (3, 1, 2)$。

情况 $z=\tfrac{19}{7}$：

$$y - 2\left(\tfrac{19}{7}\right) + 3 = 0 \implies y = \tfrac{17}{7}.$$

$$x + 3\left(\tfrac{19}{7}\right) - 9 = 0 \implies x = \tfrac{6}{7}.$$

解：$(x, y, z) = \left(\tfrac{6}{7}, \tfrac{17}{7}, \tfrac{19}{7}\right).$

本部分中发展的理论将直接应用于第二部分中的密码分析问题。一类称为算术化导向密码的密码哈希函数被设计为具有紧凑的代数描述，这使得它们的内部计算可以表示为素域上的低次多项式系统。该系统的簇是与已知输出一致的输入集合。第二部分将展示如何构建该系统，计算其Gröbner basis，并恢复输入，并提供SageMath中的工作实现。

• 原文链接： hexens.io/blog/groebner-...
• 登链社区 AI 助手，为大家转译优秀英文文章，如有翻译不通的地方，还请包涵～