# Extensions of Coppersmith algorithm

The Coppersmith algorithm can be made even more general. There are two main extensions, first to an unknown modulus, then to multivariate polynomials.

## Unknown modulus

This extension of Coppersmith allows one to find small roots modulo an unknown some unknown factor of a number. More specifically, suppose that we have some unknown factor$b$of$N$such that $b<N^\beta$and some monic polynomial$f$of degree$d$such that $f(x_0)=0\pmod b$for some $x_0<N^{\frac{\beta^2}d}$. Then we can find$x_0$in time polynomial in $\log N,d$.

One key reason why this is possible is because we dont need to explicitly know the modulus to determine if a small root exists, i.e. $\left\lVert f(Bx)\right\rVert_2\leq\frac b{\sqrt{d+1}}\leq\frac{N^{\beta}}{\sqrt{d+1}}$is sufficient for a root less than$B$to exist. The algorithm here is extremely similar to the Coppersmith algorithm, except we add more polynomials into the lattice. The polynomials that we will use are

The lattice$L$generated by these polynomials would have

As we require the shortest vector to have length at most $\frac{N^{\beta h}}{\sqrt{n}}$, repeating the computations from the previous section, we obtain

It turns out that the maxima of $\frac{2\beta h}{n-1}-\frac{dh(h+1)}{n(n-1)}$is $\frac{\beta^2}d$as $n,h\to\infty$. One way to achieve this is by setting$n=\frac d\beta h$and we obtain

and this indeed achieves the $O\left(N^{\frac{\beta^2}d}\right)$bound. Similar to the Coppersmith algorithm, one chooses a sufficiently big $h,n$such that the remainding bits can be brute forced in constant time while the algorithm still remains in polynomial time.

## Exercises

1) We show that the maximum of$\frac{2\beta h}{n-1}-\frac{dh(h+1)}{n(n-1)}$is indeed $\frac{\beta^2}d$. We can assume that $d\geq2,h\geq1,0<\beta\leq1,n\geq2$. Since $\frac h{n-1}\left(2\beta-d\frac{h+1}{n}\right)$and $\frac h{n-1}<\frac{h+1}n$, the maximum occurs when $h,n\to\infty$and $\frac h{n-1},\frac{h+1}n\to x$, hence we have reduced this to maximizing $2\beta x-dx^2$which achieves its maximum of $\frac{\beta^2}d$ at $x=\frac\beta d$.

Last updated