> For the complete documentation index, see [llms.txt](https://cryptohack.gitbook.io/cryptobook/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://cryptohack.gitbook.io/cryptobook/lattices/applications/extensions-of-coppersmith-algorithm.md).

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


---

# Agent Instructions
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.

## Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter, and the optional `goal` query parameter:

```
GET https://cryptohack.gitbook.io/cryptobook/lattices/applications/extensions-of-coppersmith-algorithm.md?ask=<question>&goal=<endgoal>
```

`ask` is the immediate question: it should be specific, self-contained, and written in natural language.
`goal` is optional and describes the broader end goal you are ultimately trying to accomplish on behalf of the user. GitBook uses it to tailor the answer towards what is most useful for that goal.

The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.