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 factorbofNsuch that b<Nβand some monic polynomialfof degreedsuch that f(x0)=0(modb)for some x0<Ndβ2. Then we can findx0in time polynomial in logN,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. ∥f(Bx)∥2≤d+1b≤d+1Nβis sufficient for a root less thanBto 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 latticeLgenerated by these polynomials would have
dim(L)=dh+t=nvol(L)=N2dh(h+1)B2(n−1)n
As we require the shortest vector to have length at most nNβh, repeating the computations from the previous section, we obtain
B<44δ−1(n1)n−11Nn−12βh−n(n−1)dh(h+1)
It turns out that the maxima of n−12βh−n(n−1)dh(h+1)is dβ2as n,h→∞. One way to achieve this is by settingn=βdhand we obtain
B<44δ−1(n1)n−11Ndh−β(h−1)β2
and this indeed achieves the O(Ndβ2)bound. Similar to the Coppersmith algorithm, one chooses a sufficiently big h,nsuch 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 ofn−12βh−n(n−1)dh(h+1)is indeed dβ2. We can assume that d≥2,h≥1,0<β≤1,n≥2. Since n−1h(2β−dnh+1)and n−1h<nh+1, the maximum occurs when h,n→∞and n−1h,nh+1→x, hence we have reduced this to maximizing 2βx−dx2which achieves its maximum of dβ2 at x=dβ.