Finally, Coppersmith!

Finding Small Solutions to Small Degree Polynomials

Univariate Modular Polynomial

The definition of “small roots”: All integers such that and , where B is a suitable bound of and is a univariate polynomial of small degree, is a modulus of unknown factorization.

We assume is monic and the gcd of its coefficients be relatively prime to . We set:

The first approach is essentially due to Hastad. We can take attention to one collection of polynomials:

For each polynomials , and all small root , is an integer. The same will be the true of any integer linear combination of polynomials in .

And we can get a lattice

Apply lattice basis reduction. Because has dimension and determinant , we will find a nonzero vector of length

where is a constant depending on the dimension.

We interpret a vector as a polynomial .

I can not understand …
to be continued