Today's alpacahack daily challenge (super_simultaneous_equations, authored by kurenaif) was a challenge I am very fond of, mainly because it's solution involves one of my favorite solution methods, that is, Gröbner bases.

Here is an abridged version of the challenge

Ring = Zmod(2**64)
Poly.<x0,x1,x2,x3,x4> = PolynomialRing(Ring, 'x', 5)
polynomials = [...] # 11 degree two polynomials

# recover x0, x1, x2, x3, x4 such that all polynomials evaluate to 0

Normally when you get a set of linear equations, you can simply toss them into a matrix and solve them using Gaussian elimination. But instead of nice linear equations, we get a system of non-linear polynomial equations.

One possible idea to remedy this is "linearization", which is essentially to pretend that each unique monomial is it's a unique variable (e.g. x0*x1 might be a, x0^2 would be b, etc...). For a max degree of 2, this creates 15 additional variables, resulting in a system defined over 15 + 5 = 20 variables. This works well for very overdetermined systems, but here, it results in a kernel of dimension 20 - 11 = 9.

So what do we do then?

Ideal quickstart

Suppose we have a set of polynomials $S = {p_0, p_1, ..., p_n}$ and you want to find where they all equal 0. Notice that if we have any random polynomial $r_0$, and $p_0 = 0$, then $r_0 * p_0 = 0$. And thus, for all random polynomials $r_i$, $r_0 * p_0 + r_1 * p_1 + ... + r_n * p_n = 0$ will also equal zero.

The infinite set of all possible polynomial combinations generated by the original equations is called the Ideal generated by $S$.

Notice that there doesn't necessarily exist one unique representation of an ideal, many different generator sets can represent the same ideal. For example, both ${(x - 1)(x + 3), (x - 0)(x - 1)}$ and ${x - 1}$ represent the same ideal (i.e. where the only zero is $x = 1$).

Another important property to mention is dimensionality which can be thought of as what "shape" the solution set takes. For example, if the dimension is 0, the solution set is just a finite set of points. For dimension 1, the solution set forms a 1-dimensional object (i.e. a line). Another way of thinking about this is that the dimension of an ideal is the minimal amount of variables needed to parametrize the solution set (i.e. how many free variables do we need to describe the solution set).

Dimensionality is in a sense the non-linear equivalent of the dimensionality of linear systems. Just like with linear algebra, adding two rows (or polynomials) together does not affect the dimensionality. Ideals though have an extra property that multiplying two polynomials from the generator together and adding it to the ideal does not affect the dimensionality either, this can be derived from the earlier definition of an ideal.

Gröbner bases

A nice way to think about Gröbner basis is as a non-linear equivalent of Gaussian elimination.

There's a lot of beautiful theory which is too complicated to put in this writeup, so put simply, Gröbner bases are "better" generator sets in the sense that they are mathematically "simpler". Another thing to note is that (reduced) Gröbner bases are unique for a given admissible monomial ordering (i.e. how you order the monomials in a polynomial). This is important since different orderings have different computation costs and different properties.

When we find the Gröbner basis of the provided polynomials array, we get a better and more simple set of polynomials. Note that since the provided polynomials array forms an ideal of dimension 0. We can expect that there will be a finite set of solutions (as opposed to the earlier solution set kernel of dim 9).

We find that the resulting array is of the form $[x0 - c0, x1 - c1, x2 - c2, x3 - c3, x4 - c4]$, where the $c_i$s are the points at which all of the polynomials evaluate to 0. Do note that we aren't guaranteed to get this nice factored form for all dimension 0 ideals (depending on which ordering was used, among other things), but for those cases, we can use what's essentially a fancy triangular decomposition to get the solutions.

Do note that Gröbner basis are usually used in the context of Fields (i.e. the complex numbers, or modulo some prime $p$), but this challenge works over $Zmod(2^64)$, which is a Ring. To address this, we either need to require that the Gröbner basis is "strong" or use Hensel lifting. Thankfully, Sagemath handles this for us.

Solve script

answer = dict()
I = Ideal(polynomials)
G = I.groebner_basis()
print(f'{G = }')
for enum, elem in enumerate(G):
	c = -elem.constant_coefficient()
	answer[f'x{enum}'] = c

# ここにあなたの答えを入れてください
# Please input your answers

def make_flag(answer):
    return b"".join([int(answer[i]).to_bytes(8, "big") for i in ["x0", "x1", "x2", "x3", "x4"]])

print(make_flag(answer))

Technical notes and nuances

  • Formally, we'd say that an ideal is a subset of a polynomial ring which is closed under addition and multiplication by any element of the ring.
  • Technically the "shape" of the solution set of an ideal $I$ is the Variety V(I). The ideal $I$ is the set of polynomials.
  • There exist more than one types of "dimension" consider the ideal $I = {x^2 + y^2}$ over $\mathbb{R}$. The solution set is a single point $(0, 0)$ and thus has real dimension 0, but the variety $V(I)$ has Krull dimension 1. The solution set will have dimension 1 when we upgrade from $\mathbb{R}$ to $\mathbb{C}$
  • Gröbner bases are not unique, but reduced Gröbner basis are
  • The reason why we need strong Gröbner bases is since rings have zero divisors (i.e. $2^{63} \cdot 2 \equiv 0 \pmod{2^{64}}$). This causes problems since we can not always divide by the leading coefficients.
  • Sage (or rather, singular) uses a special implementation for rings.
  • Using the lex ordering, even if we do not get the "nice factored form", the set will still be a triangular set, that is, a finite sequence of polynomials such that each successive polynomial introduces one more variable.