Bivariate Coppersmith algorithm

The bivariate Coppersmith algorithm (opens new window) is a technique to solve polynomial equations of the form $p(x, y) = 0$ over the integers $\mathbb{Z}$, given that the solutions are within specific bounds: $|x| < X$ and $|y| < Y$.

Suppose $p(x, y) = \sum_{ij} p_{ij}x^i y^j$ has degree $\delta$ in each variable. Define $D = max_{ij} |p_{ij|}X^i Y^j$. The algorithm finds a solution $(x, y)$ (if it exists) provided that:

$XY < D^\frac{2}{3\delta}$

The definitions of $X, Y, D$ appear circular, but it’s not a problem, the condition implies there is $p_{ij}$ such that:

$X^\frac{3\delta}{2} Y^\frac{3\delta}{2} < |p_{ij}| X^i Y^j$

$X^{\frac{3\delta}{2} - i} Y^{\frac{3\delta}{2} - j} < |p_{ij}|$

where $\frac{3\delta}{2} - i$ and $\frac{3\delta}{2} - j$ are strictly positive.

We select an integer $k > \frac{1}{4\epsilon}$. For each pair of integers $(i, j)$ with $0 \leq i < k$ and $0 \leq j < k$, we form the polynomial $q_{ij} = x^i y^j p(x, y)$.

Let’s say we have

$p(x, y) = a_{00} + a_{10} y + a_{01} x + a_{11} xy$

Our polynomial has a degree $\delta = 1$ in each variable separately.

Let’s take $k = 2$. Our shifted polynomials are then: $p(x, y), y p(x, y), x p(x, y), x y p(x, y)$.

We construct the matrix $M_1$ where the polynomials are in the right part positioned vertically:

$\begin{pmatrix} 1 & & & & & & & & & a_{00} & 0 & 0 & 0 \\ & Y^{-1} & & & & & & & & a_{10} & a_{00} & 0 & 0 \\ & & Y^{-2} & & & & & & & 0 & a_{10} & 0 & 0 \\ & & & X^{-1} & & & & & & a_{01} & 0 & a_{00} & 0 \\ & & & & X^{-1} Y^{-1} & & & & & a_{11} & a_{01} & a_{10} & a_{00} \\ & & & & & X^{-1} Y^{-2} & & & & 0 & a_{11} & 0 & a_{10} \\ & & & & & & X^{-2} & & & 0 & 0 & a_{01} & 0 \\ & & & & & & & X^{-2} Y^{-1} & & 0 & 0 & a_{11} & a_{01} \\ & & & & &&& & X^{-2} Y^{-2} & 0 & 0 & 0 & a_{11} \end{pmatrix}$

The left-hand block $M_1$ is of dimension $(\delta + k)^2 \times (\delta + k)^2$. The right-hand block of $M_1$ is of dimension $(\delta + k)^2 \times k^2$. If the coefficients of $p$ share no nontrivial common factor, we can use elementary row operations to transform the right-hand block into an identity matrix at the bottom and zeros at the top. (let’s denote the matrix that performs this transformation by $T$):

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

$M_1 = T M_2$

Let’s denote the top-block (the rows which have the last $k^2$ entries all zero) of $M_2$ by $M_3$.

Let’s define

$r = (1, y, y^2, x, x y, x y^2, x^2, x^2 y, x^2 y^2)$

$s = r M_1 = r T M_2$

Note that $det(T) = 1.$

We can see that the entries of $s$ corresponding to the left-hand block of $M_1$ are smaller than $1$. The last $k^2$ of $s$ are $0$.

Thus, in our case, where the left-hand block of $M_1$ has $(k + 1)^2$ columns:

$||s||^2 \leq (\delta + k)^2$

$||s|| \leq \delta + k$

The vector $s$ lies in the lattice spanned by the rows of $M_3$.

We apply the LLL algorithm (opens new window) to $M_3$, followed by the Gram-Schmidt orthogonalization on the LLL reduced matrix. This process yields the matrix $L$. Let’s denote the rows of $L$ by $b_i$.

$L = \begin{pmatrix} & & & & & b_1 & & & & \\ & & & & & b_2 & & & & \\ & & & & & b_3 & & & & \\ & & & & & b_4 & & & & \\ & & & & & b_5 & & & & \end{pmatrix}$

However, let’s consider the transformation of the entire matrix $M_2$. Let’s say

$M_2 = T_1 L'$

where $L'$ contains the submatrix $L$.

$L' = \begin{pmatrix} & & & & & b_1 & & & & 0 & 0 & 0 & 0 \\ & & & & & b_2 & & & & 0 & 0 & 0 & 0 \\ & & & & & b_3 & & & & 0 & 0 & 0 & 0 \\ & & & & & b_4 & & & & 0 & 0 & 0 & 0 \\ & & & & & b_5 & & & & 0 & 0 & 0 & 0 \\ & & & & & & & & & 1 & 0 & 0 & 0 \\ & & & & & & & & & 0 & 1 & 0 & 0 \\ & & & & & & & & & 0 & 0 & 1 & 0 \\ & & & & &&& & & 0 & 0 & 0 & 1 \end{pmatrix}$

We have:

$s = r M_1 = r T M_2 = r T T_1 L'$

We can see that $r T T_1$ is a vector with the last $k^2$ entries being all zero (because this holds for vector $s$). Thus, $s$ lies in the space spanned by the rows of $L$:

$s = \sum_{i}^n c_i b_i$

Note that the Gram-Schmidt orthogonalization (without normalization) preserves the determinant (meaning $det(T_1) = 1$).

The vectors $b_i$ are orthogonal. So if

$||s|| < ||b_n||$

then we know

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

meaning that $c_n = 0$. This also means that $s$ is orthogonal to $b_n$, implying that the inner product of $s$ and $b_n$ is zero. From this, we obtain two new polynomials that evaluate to zero at the same $(x, y)$ as our original polynomial $p$ does.

However, it needs to hold:

$||s|| < ||b_n||$

From the LLL paper, we know that if $M_3$ is square, the following holds:

$||b_n|| \geq |det(M_3)|^{\frac{1}{n}} 2^{\frac{-(n-1)}{4}}$

In our case, $M_3$ is not square.

To estimate $b_n$, Coppersmith defined the matrix

$W = \begin{pmatrix} 1 & & & & & & & & \\ & Y & & & & & & & \\ & & Y^2 & & & & & & \\ & & & X & & & & & \\ & & & & X Y & & & & \\ & & & & & X Y^{2} & & & \\ & & & & & & X^{2} & & \\ & & & & & & & X^{2} Y & \\ & & & & &&& & X^{2} Y^{2} \end{pmatrix}$

The left-hand block of $W M_1$ is the identity. Let $M_4$ be the right-hand block of $W M_1$.

Coppersmith proved that there exists a $k^2 \times k^2$ submatrix in the right-hand block of $W M_1$ whose determinant is at least $D'$ (let’s leave the details of what $D'$ is for now):

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

We remove the corresponding columns in the left-hand block. We obtain:

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

The matrix $A$ has the same determinant as the $k^2 \times k^2$ submatrix, which is at least $D'$.

Let’s take the same columns (as we did above) from the matrix $M_1$ and denote the resulting matrix by $\hat{M_1}$:

$W \hat{M_1} = A$

$det(A) = det(W \hat{M_1}) = det(W) det(\hat{M_1}) \geq D'$

We know:

$det(W) = (XY)^{\frac{k^2(k-1)}{2}}$

So we have:

$det(\hat{M_1}) \geq D' (XY)^{\frac{-k^2(k-1)}{2}}$

We have:

$det(\hat{M_1}) = det(\hat{M_2}) = det(\hat{M_3})$

so we can now use $||b_n|| \geq |det(\hat{M_3})|^{\frac{1}{n}} 2^{\frac{-(n-1)}{4}}$ to estimate $||b_n||$.