Gröbner Bases in Cryptanalysis Part 1: The Underlying Algebra

A Gröbner basis is a canonical generating set for a polynomial ideal with powerful computational properties. Given a system of polynomial equations, computing a Gröbner basis with respect to a lexicographic monomial order reduces it to a sequence of univariate polynomials that can be solved by standard root-finding.

This is Part 1 of a two-part article that develops a Gröbner basis attack on arithmetization-oriented ciphers, a class of hash functions designed for use inside zero-knowledge proof systems. Part 1 builds the necessary algebraic machinery: what a Gröbner basis is, how it is computed, and why it solves polynomial systems. Part 2 will show how a hash function becomes a polynomial system and how that machinery breaks it.

The definitions and theorems in this post follow Cox, Little, and O'Shea, Ideals, Varieties, and Algorithms (4th ed., Springer, 2015). Chapters 1 and 2 cover all the material in this post.

Polynomial Rings and Affine Varieties

The starting point is to make precise what we mean by a system of polynomial equations and its solution set.

Definition. Let $k$ be a field and $x_1, \ldots, x_n$ indeterminates. A monomial in $x_1, \ldots, x_n$ is a product of the form

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

The total degree of $x^\alpha$ is $|\alpha| = \alpha_1 + \cdots + \alpha_n$. A polynomial $f$ in $x_1, \ldots, x_n$ with coefficients in $k$ is a finite $k$-linear combination of monomials:

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

The set of all such polynomials, equipped with the usual addition and multiplication, forms a commutative ring denoted $k[x_1, \ldots, x_n]$, called the polynomial ring in $n$ variables over $k$.

The solution set of a system of polynomial equations is the fundamental geometric object we need.

Definition. Let $f_1, \ldots, f_s \in k[x_1, \ldots, x_n]$. The affine variety defined by $f_1, \ldots, f_s$ is the set of all common zeros:

$$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 \}.$$

Example. In $\mathbb{R}^2$, the variety $V(x_1^2 + x_2^2 - 1)$ is the unit circle. The variety $V(x_1 - x_2,\, x_1^2 - 1)$ is the finite set $\{(1,1),(-1,-1)\}$.

Ideals

A system of polynomial equations can be described by many different collections of polynomials. Multiplying any $f_i$ by an arbitrary polynomial $h$, or replacing $f_1$ with $f_1 + h \cdot f_2$, does not change the solution set. This suggests that the solution set depends not on the particular generators chosen, but on a larger algebraic object they generate. That object is an ideal.

Definition. A subset $I \subseteq k[x_1, \ldots, x_n]$ is an ideal if:

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$.

Definition. Given $f_1, \ldots, f_s \in k[x_1, \ldots, x_n]$, the ideal generated by $f_1, \ldots, f_s$ is

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

This is the smallest ideal containing $f_1, \ldots, f_s$.

The key observation is that different generating sets for the same ideal define the same variety. This is not obvious from the definition of a variety, but it follows immediately from the ideal structure.

Lemma. If $\langle f_1, \ldots, f_s \rangle = \langle g_1, \ldots, g_t \rangle$, then $V(f_1, \ldots, f_s) = V(g_1, \ldots, g_t)$.

This lemma means we are free to replace any generating set for an ideal with any other generating set, including a Gröbner basis, without changing the variety. Solving the system with a convenient generating set is equivalent to solving it with the original one.

We also record the ideal associated to a given variety, which will appear in the construction of the field equations.

Definition. Given an affine variety $V \subseteq k^n$, the ideal of $V$ is

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

The ideal $I(V)$ captures every polynomial relation that vanishes on $V$ and is in general strictly larger than any particular generating set $\langle f_1, \ldots, f_s \rangle$ used to define $V$.

Monomial Orderings

To compute with polynomials in $k[x_1, \ldots, x_n]$, we need a notion of leading term: the term we try to cancel first when performing polynomial division. In the univariate case, the leading term is simply the one of highest degree. In the multivariate case, there is no single natural choice, and different choices lead to Gröbner bases with different properties.

Definition. A monomial ordering on $k[x_1, \ldots, x_n]$ is a total ordering $>$ on the set of monomials satisfying:

1. if $x^\alpha > x^\beta$ then $x^\alpha \cdot x^\gamma > x^\beta \cdot x^\gamma$ for all $\gamma \in \mathbb{Z}_{\geq 0}^n$,
2. $>$ is a well-ordering: every nonempty set of monomials has a least element.

Condition 2 implies that $1 = x^{(0,\ldots,0)}$ is the smallest monomial under any monomial ordering, and together with condition 1 it guarantees that any sequence of reductions eventually terminates.

There are three orderings used in practice. Their computational and structural properties differ significantly, and the choice of ordering is central to the efficiency of the attack.

Definition (Lexicographic Order, lex). $x^\alpha >_{\mathrm{lex}} x^\beta$ if the leftmost nonzero entry of $\alpha - \beta \in \mathbb{Z}^n$ is positive.

Example. In $k[x_1, x_2, x_3]$: $x_1^2 x_3 >_{\mathrm{lex}} x_1 x_2^5 >_{\mathrm{lex}} x_2^4 x_3^2$. The variable $x_1$ dominates unconditionally, regardless of the degrees of $x_2$ and $x_3$. This makes lex order behave like a dictionary, and it is precisely this property that makes it suitable for elimination: a lex Gröbner basis will contain elements involving only $x_2, x_3$, then only $x_3$, allowing us to solve the system one variable at a time.

Definition (Graded Lexicographic Order, grlex). $x^\alpha >_{\mathrm{grlex}} x^\beta$ if $|\alpha| > |\beta|$, or if $|\alpha| = |\beta|$ and $x^\alpha >_{\mathrm{lex}} x^\beta$.

Example. In $k[x_1, x_2, x_3]$: $x_1 x_2 x_3 >_{\mathrm{grlex}} x_1^2 x_3$ since $|\alpha| = 3 > 2 = |\beta|$. Total degree is compared first; lex breaks ties.

Definition (Graded Reverse Lexicographic Order, grevlex). $x^\alpha >_{\mathrm{grevlex}} x^\beta$ if $|\alpha| > |\beta|$, or if $|\alpha| = |\beta|$ and the rightmost nonzero entry of $\alpha - \beta$ is negative.

Example. In $k[x_1, x_2, x_3]$, among degree-2 monomials: $x_1^2 >_{\mathrm{grevlex}} x_1 x_2 >_{\mathrm{grevlex}} x_1 x_3 >_{\mathrm{grevlex}} x_2^2 >_{\mathrm{grevlex}} x_2 x_3 >_{\mathrm{grevlex}} x_3^2$.

With a monomial ordering fixed, we can designate the distinguished term of each polynomial.

Definition. Fix a monomial ordering $>$ and let $f = \sum_\alpha c_\alpha x^\alpha \neq 0$.

• The multidegree of $f$ is $\mathrm{multdeg}(f) = \max_>\{\alpha \mid c_\alpha \neq 0\}$.
• The leading monomial is $\mathrm{LM}(f) = x^{\mathrm{multdeg}(f)}$.
• The leading coefficient is $\mathrm{LC}(f) = c_{\mathrm{multdeg}(f)} \in k$.
• The leading term is $\mathrm{LT}(f) = \mathrm{LC}(f) \cdot \mathrm{LM}(f)$.

Example. For $f = 4x_1^2 x_2 + 3x_2^3 - x_1 \in \mathbb{Q}[x_1, x_2]$ under $>_{\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$.

The Multivariate Division Algorithm

With a notion of leading term in hand, we can generalise polynomial long division to the multivariate setting.

Theorem. Fix a monomial ordering $>$ and an ordered $s$-tuple $F = (f_1, \ldots, f_s)$. Then every $f \in k[x_1, \ldots, x_n]$ can be written as

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

where $a_i, r \in k[x_1, \ldots, x_n]$, no monomial of $r$ is divisible by any $\mathrm{LT}(f_i)$, and $\mathrm{multdeg}(f) \geq \mathrm{multdeg}(a_i f_i)$ whenever $a_i f_i \neq 0$. The polynomial $r$ is the remainder on division of $f$ by $F$, written $\overline{f}^F$.

The algorithm proceeds greedily: at each step, if the current leading term is divisible by some $\mathrm{LT}(f_i)$, it is cancelled; otherwise it is moved to the remainder.

This generalisation, however, has two serious defects that do not appear in the univariate case.

First, the remainder $\overline{f}^F$ need not be unique: reordering $f_1, \ldots, f_s$ can produce a different remainder for the same $f$. Second, and more critically, $\overline{f}^F = 0$ does not imply $f \in \langle f_1, \ldots, f_s \rangle$. A polynomial can be a member of an ideal yet fail to reduce to zero when divided by a generating set, simply because the right cancellations do not happen in the right order.

These two defects are not minor inconveniences. They mean that arbitrary generating sets are computationally useless for ideal membership testing and system solving. Gröbner bases are defined as exactly the generating sets for which both defects disappear.

Gröbner Bases

Before defining a Gröbner basis, we need to know that every ideal has a finite generating set to begin with, without this, the notion of a "basis" would be ill-defined. This is the content of the Hilbert Basis Theorem.

Theorem (Hilbert Basis Theorem). Every ideal $I \subseteq k[x_1, \ldots, x_n]$ has a finite generating set.

The proof uses the ascending chain condition: any chain $I_1 \subseteq I_2 \subseteq \cdots$ of ideals must eventually stabilise. This will also guarantee that Buchberger's algorithm, which enlarges a generating set step by step, always terminates.

Definition. For an ideal $I \subseteq k[x_1, \ldots, x_n]$, the leading term ideal is

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

The leading term ideal collects the leading terms of every element of $I$, not just those of a generating set. The gap between $\langle \mathrm{LT}(f_1), \ldots, \mathrm{LT}(f_s) \rangle$ and $\mathrm{LT}(I)$ is precisely what causes the division algorithm to fail. A Gröbner basis closes this gap.

Definition. A finite set $G = \{g_1, \ldots, g_t\} \subset I$ is a Gröbner basis for $I$ if

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

Equivalently, for every nonzero $f \in I$, there exists $g_i \in G$ such that $\mathrm{LT}(g_i)$ divides $\mathrm{LT}(f)$.

Every nonzero ideal has a Gröbner basis, and every Gröbner basis is a generating set for $I$. The following two lemmas confirm that Gröbner bases fix both defects identified previously.

Lemma. Let $G$ be a Gröbner basis for $I$. Then every $f \in k[x_1, \ldots, x_n]$ has a unique remainder $\overline{f}^G$, independent of the ordering of elements of $G$ in the division algorithm. This remainder is called the normal form of $f$ with respect to $G$, written $\mathrm{NF}(f, G)$.

Lemma. Let $G$ be a Gröbner basis for $I$. Then

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

Together, these lemmas say that once we have a Gröbner basis, ideal membership becomes a deterministic single computation. Since we know that $V(G) = V(I)$, we can replace any generating set with a Gröbner basis and solve the resulting system instead.

The S-Polynomial and Buchberger's Algorithm

To compute a Gröbner basis, we need a criterion that detects whether a given generating set is already one. The key observation is that the only way a generating set can fail to be a Gröbner basis is if some combination of its elements produces a polynomial whose leading term is not divisible by any of the generators' leading terms. The S-polynomial is designed to expose exactly these combinations.

Definition. Let $f, g \in k[x_1, \ldots, x_n]$ be nonzero, with $\alpha = \mathrm{multdeg}(f)$ and $\beta = \mathrm{multdeg}(g)$. Set $x^\gamma = \mathrm{lcm}(\mathrm{LM}(f), \mathrm{LM}(g))$, where $\gamma_i = \max(\alpha_i, \beta_i)$. The S-polynomial of $f$ and $g$ is

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

The leading terms of $f$ and $g$ cancel by construction, producing a polynomial of strictly lower degree. If this polynomial reduces to zero modulo the current generating set, it contributes nothing new to the ideal and no new generator is needed. If it does not reduce to zero, its remainder is a new ideal element whose leading term is missing from $\langle \mathrm{LT}(G) \rangle$, witnessing that $G$ is not yet a Gröbner basis.

Example. Let $f = x_1^3 - 2x_1 x_2$ and $g = x_1^2 x_2 - 2x_2^2 + x_1$ in $\mathbb{Q}[x_1, x_2]$ under $>_{\mathrm{lex}}$. Then $\mathrm{lcm}(\mathrm{LM}(f), \mathrm{LM}(g)) = x_1^3 x_2$, and

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

Theorem (Buchberger's Criterion). A generating set $G = \{g_1, \ldots, g_t\}$ for an ideal $I$ is a Gröbner basis if and only if

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

This criterion directly yields an algorithm: start with the given generators, compute all pairwise S-polynomials, add any nonzero remainder as a new generator, and repeat until no new generators appear.

Buchberger's Algorithm.

Input: $F = \{f_1, \ldots, f_s\}$
Output: A Gröbner basis $G \supseteq F$

Set $G := F$
Repeat:
$\quad$ Set $G' := G$
$\quad$ For each pair $\{p, q\} \subseteq G'$:
$\quad\quad$ Compute $r := \overline{S(p,q)}^{G'}$
$\quad\quad$ If $r \neq 0$, set $G := G \cup \{r\}$
Until $G = G'$
Return $G$

Termination follows from the ascending chain condition: each nonzero remainder strictly enlarges $\langle \mathrm{LT}(G) \rangle$, and this chain must stabilise.

Minimal and Reduced Gröbner Bases

Buchberger's algorithm terminates with a Gröbner basis, but typically one containing redundant elements. We shrink it in two steps.

Definition. A Gröbner basis $G$ is minimal if every $p \in G$ is monic and $\mathrm{LT}(p) \notin \langle \mathrm{LT}(G \setminus \{p\}) \rangle$.

Definition. A Gröbner basis $G$ is reduced if every $p \in G$ is monic and no monomial of $p$ is divisible by $\mathrm{LT}(q)$ for any other $q \in G$.

A reduced Gröbner basis is obtained from any Gröbner basis by first removing redundant elements to make it minimal, then fully reducing each remaining element modulo the others. The result is unique.

Theorem. Fix a monomial ordering. Every nonzero ideal $I \subseteq k[x_1, \ldots, x_n]$ has a unique reduced Gröbner basis.

This uniqueness means the reduced Gröbner basis is a canonical invariant of the ideal and the chosen ordering. Two polynomial systems generate the same ideal if and only if their reduced Gröbner bases coincide. For our purposes, it guarantees that the computation is deterministic: no matter how Buchberger's algorithm processes the S-polynomials, the final reduced basis is always the same.

Solving a Polynomial System with a Gröbner Basis

We now have all the pieces. The following procedure solves a system of polynomial equations $f_1 = \cdots = f_s = 0$ over a field $k$.

Step 1: Form the ideal. Collect the system into $I = \langle f_1, \ldots, f_s \rangle \subset k[x_1, \ldots, x_n]$. Finding $V(I)$ is equivalent to finding $V(f_1, \ldots, f_s)$.

Step 2: Add field equations. If $k = \mathbb{F}_p$, every element of $\mathbb{F}_p$ satisfies $a^p - a = 0$. Adding the field equations $x_i^p - x_i$ for each variable to the generating set restricts the variety to $\mathbb{F}_p^n$ and ensures the ideal is zero-dimensional, meaning $V(I)$ is a finite set.

Step 3: Choose a monomial ordering and compute a Gröbner basis. Apply Buchberger's algorithm with lex order, placing the variable of primary interest first. The resulting basis $G$ generates the same ideal and satisfies $V(G) = V(f_1, \ldots, f_s)$.

Step 4: Read off the univariate polynomial. Because lex order forces earlier variables to be eliminated as aggressively as possible, the Gröbner basis $G$ will contain an element $g \in k[x_n]$ involving only the last variable. Its roots over $k$ are the only possible values of $x_n$ in any solution.

Step 5: Back-substitute. For each root $a_n$ of $g$, substitute $x_n = a_n$ into the remaining elements of $G$ and repeat: find the univariate polynomial in $x_{n-1}$, extract its roots, substitute, and continue until all variables are determined. The full solution set $V(I)$ is recovered.

---

Example

Consider the following system over $\mathbb{Q}$ in variables $x > y > z$:

$$\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}$$

Computing the Gröbner basis. We apply Buchberger's algorithm, processing S-polynomials until all reduce to zero.

S-polynomial of $f_1$ and $f_2$. Both have leading term $x$, so $\mathrm{lcm}(\mathrm{LM}(f_1), \mathrm{LM}(f_2)) = x$ and:

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

This does not reduce to zero modulo $\{f_1, f_2, f_3\}$, so we add $g_1 = y - 2z + 3$ to the basis.

S-polynomial of $f_1$ and $f_3$. Here $\mathrm{LM}(f_1) = x$ and $\mathrm{LM}(f_3) = x^2$, so $\mathrm{lcm} = x^2$ and:

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

We reduce this modulo the current basis $\{f_1, f_2, f_3, g_1\}$. The leading term $xy$ is divisible by $\mathrm{LT}(f_1) = x$, so we subtract $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.$$

The leading term $xz$ is again divisible by $\mathrm{LT}(f_1)$, so we subtract $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.$$

The leading term $-6x$ is divisible by $\mathrm{LT}(f_1)$, so we subtract $-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.$$

Dividing through by $-2$ gives $y^2 + yz - 6y + z^2 - 6z + 11$. The leading term is now $y^2$, divisible by $\mathrm{LT}(g_1) = y$. Subtracting $y \cdot g_1$:

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

Subtracting $3z \cdot g_1$:

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

Subtracting $-9 \cdot g_1$:

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

No element of the current basis has a leading term dividing $z^2$, so this remainder is a new generator: $g_2 = 7z^2 - 33z + 38$.

Verifying the remaining S-polynomials. At this point the basis is $G = \{f_1, f_2, f_3, g_1, g_2\}$. We must check all remaining pairs. Seven of them can be dismissed immediately by the coprimality criterion: if the leading monomials of two polynomials are coprime, their S-polynomial always reduces to zero.

The only non-trivial remaining pair is $(f_2, f_3)$. We have $\mathrm{lcm}(\mathrm{LM}(f_2), \mathrm{LM}(f_3)) = x^2$, so:

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

Reducing by $f_1$ three times to eliminate $x$ terms:

$\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.$

Reducing by $g_1$ three times to eliminate $y$ terms:

$\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.$

All S-polynomials reduce to zero, confirming the basis is a Gröbner basis.

Reducing to minimal form. The current basis is $\{f_1, f_2, f_3, g_1, g_2\}$ with leading terms $x, x, x^2, y, 7z^2$. Since $\mathrm{LT}(f_2) = x$ is divisible by $\mathrm{LT}(f_1) = x$, and $\mathrm{LT}(f_3) = x^2$ is also divisible by $\mathrm{LT}(f_1) = x$, both $f_2$ and $f_3$ are redundant and are removed. Making $g_2$ monic by dividing by 7 gives $z^2 - \frac{33}{7}z + \frac{38}{7}$. The minimal basis is:

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

Reducing to reduced form. We fully reduce each element modulo the others, ensuring no monomial in any element is divisible by the leading term of another.

For $f_1 = x + y + z - 6$: the monomial $y$ is divisible by $\mathrm{LT}(g_1) = y$, so we subtract $g_1$:

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

No remaining monomial is divisible by $y$ or $z^2$, so this is fully reduced.

For $g_1 = y - 2z + 3$: no monomial is divisible by $\mathrm{LT}(f_1) = x$ or $\mathrm{LT}(g_2) = z^2$. No change.

For $z^2 - \frac{33}{7}z + \frac{38}{7}$: no monomial is divisible by $x$ or $y$. No change.

The reduced Gröbner basis in lex order is:

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

The triangular structure is the polynomial analogue of row echelon form. The variable $x$ has been eliminated from the second and third equations, and $y$ has been eliminated from the third. This is the Elimination Theorem in action.

Step 4: Solve the univariate polynomial. The third equation involves only $z$:

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

giving $z = 2$ or $z = \tfrac{19}{7}$.

Step 5: Back-substitute. For each value of $z$, substitute into the second equation to find $y$, then into the first to find $x$.

Case $z = 2$:

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

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

Solution: $(x, y, z) = (3, 1, 2)$.

Case $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}.$

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

---

The theory developed in this part will be applied directly in Part 2 to a problem in cryptanalysis. A class of cryptographic hash functions called arithmetization-oriented ciphers is designed to have a compact algebraic description, which makes their internal computation expressible as a low-degree polynomial system over a prime field. The variety of that system is the set of inputs consistent with a known output. Part 2 will show how to construct that system, compute its Gröbner basis, and recover the input, with a working implementation in SageMath.