Bauer-Joux algorithm

The Bauer-Joux algorithm (opens new window) is a technique for solving polynomial equations of the form $p(x, y, z) = 0$ over the integers $\mathbb{Z}$, given that the solutions lie within specific bounds: $|x| < X$, $|y| < Y$, and $|z| < Z.$

Consider the polynomial $p(x, y, z) = 1 + a x y + b y z$.

We choose a set of monomials $S$ by which we will shift the polynomial $p$. Let's say $S = \{1, x\}$. We denote the length of $S$ by $s$.

We define the set $M$ as the collection of all monomials of $p$ and all monomials of $sm \cdot p$ for each $sm \in S$. In our case:

$M = \{1, xy, yz, x, x^2y, xyz\}$

We define the length of $M$ as $m$.

Let $M_1$ represent the following matrix:

$\begin{pmatrix} 1 & & & & & & 1 & 0 \\ & X^{-1} Y^{-1} & & & & & a & 0 \\ & & Y^{-1} Z^{-1} & & & & b & 0 \\ & & & X^{-1} & & & 0 & 1 \\ & & & & X^{-2} Y^{-1} & & 0 & a \\ & & & & & X^{-1} Y^{-1} Z^{-1} & 0 & b \end{pmatrix}$

Let $x_0 < X, y_0 < Y, z_0 < Z$ be a root of $p(x, y, z)$. We define the vector $r_0$ as follows:

$r_0 = (1, x_0 y_0, y_0 z_0, x_0, x_0^2 y_0, x_0 y_0 z_0)$

Let

$s_0 = r_0 M_1$

We can see that the last $s$ coordinates of $r$ are $0$.

Let $L_1$ denote the lattice generated by the rows of $M_1$. By applying elementary row operations, we can transform $M_1$ into a matrix of the following form:

$\begin{pmatrix} & & & & & & 1 & 0 \\ & & & & & & 0 & 1 \\ & & & & & & 0 & 0 \\ & & & & & & 0 & 0 \\ & & & & & & 0 & 0 \\ & & & & & & 0 & 0 \end{pmatrix}$

That means there exists a sublattice $L_1' \subset L_1$ of dimension $m - s$, where the vectors in $L_1'$ have their last $s$ coordinates equal to zero.

Therefore, there exists a unimodular matrix $U$ such that:

$U \begin{pmatrix} & & & & & & 1 & 0 \\ & & & & & & 0 & 1 \\ & & & & & & 0 & 0 \\ & & & & & & 0 & 0 \\ & & & & & & 0 & 0 \\ & & & & & & 0 & 0 \end{pmatrix} = M_1$

We apply the LLL algorithm (opens new window) to the lattice $L_1'$ and then perform Gram-Schmidt orthogonalization to obtain:

$U U_1 \begin{pmatrix} & & & & & & 1 & 0 \\ & & & & & & 0 & 1 \\ & & & b_1 & & & 0 & 0 \\ & & & b_2 & & & 0 & 0 \\ & & & b_3 & & & 0 & 0 \\ & & & b_4 & & & 0 & 0 \end{pmatrix} = M_1$

where $b_1$, $b_2$, $b_3$, and $b_4$ are obtained by first applying the LLL algorithm to $L'$ and then performing Gram-Schmidt orthogonalization on the resulting vectors.

We have:

$r_0 U U_1 \begin{pmatrix} & & & & & & 1 & 0 \\ & & & & & & 0 & 1 \\ & & & b_1 & & & 0 & 0 \\ & & & b_2 & & & 0 & 0 \\ & & & b_3 & & & 0 & 0 \\ & & & b_4 & & & 0 & 0 \end{pmatrix} = r_0 M_1 = s_0$

Since $s_0$ has its last $s$ coordinates equal to zero, the vector $r_0 U U_1$ must have its first $s$ coordinates equal to zero. For $n = 4$ and $s = 2$, this implies that $r_0 U U_1 = (0, 0, c_1, c_2, c_3, c_4)$ and:

$s_0 = \sum_{i=1}^n c_i b_i$

Because of the Gram-Schmidt orthogonalization, the vectors $b_1$, ..., $b_n$ are pairwise orthogonal. We observe that if $||s_0|| < ||b_n||$, then $c_n = 0$, and $s_0$ is orthogonal to $b_n$. In this case, we compute the inner product of $s$ and $b_n$, which yields a new polynomial $p_2$ that has the same root as the polynomial $p$.

Let's assume that the polynomial $p_2$ is not algebraically independent from $p.$ Due to the construction, this would imply that $p_2$ is a linear combination of the columns on the right-hand side of the matrix $M_1$ (consisting of the polynomial $p$ and its shifts). However, since $p_2$ is also orthogonal to these polynomials, this assumption leads to a contradiction. Therefore, $p$ and $p_2$ are algebraically independent.

How to get a third independent polynomial?

We have an ideal $I = (p, p_2)$. Bauer and Joux proved that if the ideal $I$ is prime and $p_3 \in I$, then $p, p_2, p_3$ are algebraically independent.

Let $I_M$ be the set of polynomials from $I$ that are defined over $M$ (i.e., consisting only of monomials from $M$).

We compute the Gröbner basis of $I$ and select only the polynomials that are defined over $M$. This gives us a set $F = \{r_1, ..., r_n\}$.

We define a similar matrix as in the first step above, but this time the polynomials $r_1, ..., r_n$ are on the right-hand side of the matrix:

$\begin{pmatrix} 1 & & & & & & r_1 & ... & r_n \\ & X^{-1} Y^{-1} & & & & & & & \\ & & Y^{-1} Z^{-1} & & & & & & \\ & & & X^{-1} & & & & & \\ & & & & X^{-2} Y^{-1} & & & & \\ & & & & & X^{-1} Y^{-1} Z^{-1} & & & \end{pmatrix}$

In the same way that we constructed $p_2$ above, we construct a new polynomial $p_3$.

By construction, the polynomial $p_3$ is orthogonal to all the polynomials in the set $F.$

If $p_3 \in I$, then it must be a linear combination of the polynomials from $F$. However, it is also orthogonal to all these polynomials, which implies $p_3 = 0$. Since this is not the case, we conclude that $p_3 \notin I$. Therefore, if $I$ is prime, the polynomials $p$, $p_2$, and $p_3$ are algebraically independent.

That means if we obtain $p_3$ through the above construction, it's algebraically indpendent from $p_1$ and $p_2$. But when does this construction succeed?

Remember, we get $p_2$ when $||s_0|| < ||b_n||$.

Bauer and Joux use a similar estimation of $b_n$ as Coppersmith in the bivariate case.

They use shifts of $p$ and $p_2$ as columns in the right-hand side matrix (as $F$ set). Similar to the bivariate case, they select the submatrix with the largest determinant, but here, the $p_2$ column must also be taken into account:

$A = \begin{pmatrix} 1 & & & & & & & \\ & 1 & & & & & & \\ & & 1 & & & & & \\ & & & 1 & & & & \\ & & & & p_2 &x & x & x & x & \\ & & & & p_2& x & x & x & x & \\ & & & &p_2 &x & x & x & x & \\ & & & & p_2& x & x & x & x & \\ & & & & p_2 & & & & \end{pmatrix}$