# 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

$$
\begin{align\*}
g\_{i,j}(x)&=N^{h-j}f(x)^jx^i&0\leq i\<d,0\leq j\<h\\
g\_{i,h}(x)&=f(x)^hx^i&0\leq i\<t
\end{align\*}
$$

The lattice$$L$$generated by these polynomials would have

$$
\dim(L)=dh+t=n\quad\text{vol}(L)=N^{\frac{dh(h+1)}{2}}B^{\frac{(n-1)n}2}
$$

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

$$
B<\sqrt{\frac{4\delta-1}4}\left(\frac1n\right)^{\frac1{n-1}}N^{\frac{2\beta h}{n-1}-\frac{dh(h+1)}{n(n-1)}}
$$

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

$$
B<\sqrt{\frac{4\delta-1}4}\left(\frac1n\right)^{\frac1{n-1}}N^{\frac{(h-1)\beta^2}{dh-\beta}}
$$

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$$.