Univariate Coppersmith algorithm

Problem to be solved

We aim to find a root of the polynomial modulo some integer $N$.

More precisely, consider a polynomial $p(x)$ of degree $k$. If there is $x_0$ such that

$|x_0| < \frac{1}{2}N^{\frac{1}{k} - \epsilon}$

and

$p(x_0) = 0 \; mod \; N$

then the Coppersmith algorithm (opens new window) can find $x_0$ in time polynomial in $log N$, $k$, and $\frac{1}{\epsilon}$.

By setting $\epsilon = \frac{1}{log N}$ and exhaustively searching the few unknown high bits of $x_0$, we can extend the range to $x_0 < N^{\frac{1}{k}}$.

Coppersmith algorithm

Let’s define for each $0 \leq i < k, 1 \leq j < h$:

$q_{ij}(x) = x^i p(x)^j$

Let’s define

$X = \frac{1}{2}N^{\frac{1}{k} - \epsilon}$

We have $(h - 1) k = hk - k$ of these polynomials.

We build a matrix of size $(2hk - k) \times (2hk - k)$. In the top left $hk \times hk$ submatrix, we have the following elements on the diagonal:

$\frac{1}{\sqrt{hk}}, \frac{1}{\sqrt{hk}} X^{-1}, ..., \frac{1}{\sqrt{hk}} X^{-(hk-1)}$

Let’s observe the example where $h = 3, k = 2$, and $p(x) = x^2 + ax + b$.

We have $p(x)^2 = x^4 + cx^3 + dx^2 + ex + f$. Let’s denote the following matrix by $M$:

$\begin{pmatrix} \frac{1}{\sqrt{hk}} & & & & & & b & 0 & f & 0 \\ & \frac{1}{\sqrt{hk}} X^{-1} & & & & & a & b & e & f \\ & & \frac{1}{\sqrt{hk}} X^{-2} & & & & 1 & a & d & e \\ & & & \frac{1}{\sqrt{hk}} X^{-3} & & & 0 & 1 & c & d \\ & & & & \frac{1}{\sqrt{hk}} X^{-4} & & 0 & 0 & 1 & c \\ & & & & & \frac{1}{\sqrt{hk}} X^{-5} & 0 & 0 & 0 & 1 \\ & & & & & & N & & & \\ & & & & & & & N & & \\ & & & & & & & & N^2 & & \\ & & & & & & & & & N^2 \end{pmatrix}$

The upper left submatrix is diagonal and has dimensions $hk \times hk$. The upper right submatrix has dimensions $hk \times (hk - k)$. Note that the number of rows is $hk$ because the biggest degree of the polynomials is $(k-1) + (h-1)k = k - 1 + hk - k = hk - 1$.

The lower left submatrix is all $0$ and is of dimension $(hk - k) \times hk$. The bottom right submatrix is diagonal and is of dimension $(hk - k) \times (hk - k)$.

Note that

$det(M) = N^{\frac{(h-1)hk}{2}} X^{\frac{-hk(hk-1)}{2}} (\frac{1}{\sqrt{hk}})^{hk}$

We have $X = \frac{1}{2} N^{\frac{1}{k} - \epsilon}$ and we choose $h$ such that:

$h - 1 \geq (hk - 1)(\frac{1}{k} - \epsilon)$

$hk \geq 7$

Then, it can be shown that $hk < 2^{\frac{hk-1}{2}}$. Thus:

$det(M) > (N^{h-1} X^{-(hk-1)} 2^{\frac{-(hk-1)}{2}})^{\frac{hk}{2}}$

From our choice of $X:$

$det(M) > (N^{(h-1)-(hk-1)(\frac{1}{k} - \epsilon)} 2^{\frac{(hk-1)}{2}})^{\frac{hk}{2}}$

The condition $h - 1 \geq (hk - 1)(\frac{1}{k} - \epsilon)$ gives us:

$det(M) > 2^{\frac{hk(hk-1)}{4}}$

Let $x_0 < X$ be a modular root of $p(x)$. Then:

$p(x_0) = y_0 N$

for some integer $y_0$. Let’s define a vector

$v = (1, x_0, x_0^2, x_0^3, x_0^4, x_0^5, -y_0, -y_0 x_0, -y_0^2, -y_0^2 x_0)$

Let

$s = vM$

We can see that the last $hk - k$ coordinates of $s$ are $0$:

$s = (\frac{1}{\sqrt{hk}}, \frac{x_0}{X \sqrt{hk}}, \frac{x_0^2}{X^2 \sqrt{hk}}, ..., \frac{x_0^5}{X^5 \sqrt{hk}}, 0, 0, 0, 0)$

We can also see:

$||s|| = (\frac{1}{hk} + \frac{x_0^2}{X^2 hk} + ... + \frac{x_0^5}{X^5 hk})^{\frac{1}{2}}$

and

$||s|| \le (\frac{1}{hk} + \frac{1}{hk} + ... + \frac{1}{hk})^{\frac{1}{2}} = 1$

Let’s observe the right $(2hk - k) \times (hk - k)$ submatrix. There is a $1$ in each column, so by performing the elementary operations on the rows, we can transform this submatrix into the matrix $M'$:

$\begin{pmatrix} &&&&&& 0 & 0 & 0 & 0 \\&&&&&& 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}$

Let’s check some observations (opens new window) made by Charanjit S. Jutla. $M$ can be written as follows:

$M = \begin{pmatrix} A_1 & B_1 \\ A_2 & B_2 \\ 0 & C \end{pmatrix}$

where $B_2$ is an upper triangular matrix of size $(hk - k) \times (hk - k)$, with all diagonal entries equal to $1$. Using elementary row operations we can transform $M$ to $M'$:

$M' = \begin{pmatrix} A_1' & 0 \\ A_2' & I \\ A_3' & 0 \end{pmatrix}$

where $I$ is an identity matrix of size $(hk - k) \times (hk - k)$. The row operations we are using are subtractions of the rows of

$\begin{pmatrix} A_2 & B_2 \end{pmatrix}$

First, we use these type of subractions to get

$\begin{pmatrix} A_2' & I \end{pmatrix}$

We take the first row and subract the second row multiplied by $a$, and continue this process in a similar manner. We observe that $A_2'$ is also upper triangular. Let’s denote

$\hat M = \begin{pmatrix} A_1' \\ A_3' \end{pmatrix}$

$\hat M$ is upper triangular too. By using row exchanges, we can obtain:

$\tilde{M} = \begin{pmatrix} A_1' & 0 \\ A_3' & 0 \\ A_2' & I \end{pmatrix}$

It holds:

$det(\hat{M}) = det(\tilde{M}) = det(M)$

So, there exists a matrix $H_1$ of dimension $(2hk - k) \times (2hk - k)$ such that:

$H_1 \tilde{M} = M$

We then apply the LLL algorithm (opens new window) to $\hat M$. We get a matrix $\hat L$ such that:

$\hat U \hat L = \hat M$

It holds:

$\tilde{M} = \begin{pmatrix} A_1' & 0 \\ A_3' & 0 \\ A_2' & I \end{pmatrix}$

$= \begin{pmatrix} \hat M & 0 \\ A_2' & I \end{pmatrix}$

$= \begin{pmatrix} \hat U \hat L & 0 \\ A_2' & I \end{pmatrix}$

$= \begin{pmatrix} \hat U & 0 \\ 0 & I \end{pmatrix} \begin{pmatrix} \hat L & 0 \\ A_2' & I \end{pmatrix}$

So we have:

$H_1 \begin{pmatrix} \hat U & 0 \\ 0 & I \end{pmatrix} \begin{pmatrix} \hat L & 0 \\ A_2' & I \end{pmatrix} = M$

$v H_1 \begin{pmatrix} \hat U & 0 \\ 0 & I \end{pmatrix} \begin{pmatrix} \hat L & 0 \\ A_2' & I \end{pmatrix} = v M = s$

We have a vector

$c = (c_1, ..., c_{2hk - k}) = v H_1 \begin{pmatrix} \hat U & 0 \\ 0 & I \end{pmatrix}$

We know that vector $s$ has the last $hk - k$ elements all equal to $0$. Therefore, instead of

$s = c \begin{pmatrix} \hat L & 0 \\ A_2' & I \end{pmatrix}$

we can write

$s = (c_1, ..., c_{hk}) \begin{pmatrix} \hat L & 0 \end{pmatrix}$

Let’s denote the rows of $\hat L$ by $b_i$:

$s = c_1 b_1 + ... + c_{hk} b_{hk}$

Let’s recall how Gram-Schmidt basis is constructed:

$b_i^* = b_i - \sum_{j=1}^{i-1} \mu_{ij} b_j^*$

So:

$b_i = b_i^* + \sum_{j=1}^{i-1} \mu_{ij} b_j^*$

And we have

$s = \sum_{i=1}^{hk} c_i (b_i^* + \sum_{j=1}^{i-1} \mu_{ij} b_j^*) = c_{hk} b_{hk}^* + f_1 b_1^* + ... f_{hk-1} b_{hk-1}^*$

for some $f_1, ..., f_{hk-1}$.

That means

$||s|| \geq |c_{hk} b_{hk}^*|$

because all $b_i^*$ where $i < hk$ are orthogonal to $b_{hk}^*$.

For the LLL algorithm it holds:

$|b_{hk}^*| \geq det(M)^{\frac{1}{hk}} 2^{\frac{-(hk-1)}{4}}$

And from above we know:

$det(M) > 2^{\frac{hk(hk-1)}{4}}$

Thus:

$|b_{hk}^*| \geq 1$

But we saw above that:

$||s|| < 1$

That means:

$c_{hk} = 0$

But $c_{hk}$ is a polynomial in $x_0$. Thus, we have obtained another polynomial that has a root at $x_0$.

This is a polynomial equation in $x_0$ which holds in $\mathbb{Z}$, not just $mod \; N$. We can solve this for $x_0$ in polynomial time.