The Coppersmith algorithm can be made even more general. There are two main extensions, first to an unknown modulus, then to multivariate polynomials.
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 factorofsuch that and some monic polynomialof degreesuch that for some . Then we can findin time polynomial in .
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. is sufficient for a root less thanto 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 latticegenerated by these polynomials would have
As we require the shortest vector to have length at most , repeating the computations from the previous section, we obtain
It turns out that the maxima of is as . One way to achieve this is by settingand we obtain
and this indeed achieves the bound. Similar to the Coppersmith algorithm, one chooses a sufficiently big such that the remainding bits can be brute forced in constant time while the algorithm still remains in polynomial time.
1) We show that the maximum ofis indeed . We can assume that . Since and , the maximum occurs when and , hence we have reduced this to maximizing which achieves its maximum of at .