Finally, Coppersmith!

# Finding Small Solutions to Small Degree Polynomials

## Univariate Modular Polynomial

The definition of “small roots”: All integers $x_0$ such that $|x_0| < B$ and $p(x_0)=0\mod N$, where B is a suitable bound of $x_0$ and $p(x)$ is a univariate polynomial of small degree, $N$ is a modulus of unknown factorization.

We assume $p$ is monic and the gcd of its coefficients be relatively prime to $N$. We set:
$$p(x) = x^d + p_{d-1}x^{d-1} + \cdots + p_2x^2 + p_1x + p_0$$
The first approach is essentially due to Hastad. We can take attention to one collection $C_1$ of polynomials:
$$C_1 = \{x_i,0 \le i < d\} \cup \{p(x)/N\}$$
For each polynomials $q \in C_1$ , and all small root $x_0$, $q(x_0)$ is an integer. The same will be the true of any integer linear combination of polynomials in $C_1$.

And we can get a lattice
$$L = \begin{pmatrix} 1&0&0& \cdots&0&0&p_0 /N \\ 0&B&0& \cdots&0&0&p_1 /N \\ 0&0&B^2&\cdots&0&0&p_2/N \\ &&&\vdots \\ 0&0&0&\cdots&B^{d-2}&0p_{d-2}B^{d-2}/N \\ 0&0&0&\cdots&0&B^{d-1}&p_{d-1}B^{d-1}/N \\ 0&0&0&\cdots&0&0&B^d/N \end{pmatrix}$$
Apply lattice basis reduction. Because $L_1$ has dimension $d+1$ and determinant $N^{-1}B^{d(d+1)/2}$, we will find a nonzero vector $v$ of length
$$|v| < c_1(d)det(L_1)^{1/(d+1)} = c_1N^{-1/(d+1)}B^{d/2},$$
where $c_1(d)$ is a constant depending on the dimension.

We interpret a vector $\mathbb v = (v_0,v_1B,\cdots,v_dB^d)$ as a polynomial $v(x) = \sum v_ix^i$.

I can not understand …
to be continued