# Coppersmith's method implementation

suppose i have two equations: $$(m)^{3} \bmod n = c_{0}$$ $$(m + 2^{k}r + d) \bmod n = c_{1}$$ The values($c_{0}, c_{1}, k, d$) are known. I wanted to retrieve r (ofc $|r| < n^{\frac{1}{9}})$ Using resultant on equations gives me equation of 9 degree.: $$w(x) = x^{9} + 3(c_{1} - c_{0})x^{6} + (3c_{0}^{2} + 21c_{0}c_{1} + 3c{1}^{2})x^{3} + (c_{1} - c_{0})^3 \bmod n = 0$$ , where x is $2^{k}r + d$ (as usual with coppersmith method). After substitute x with $2^{k}r + d$ and change polynomial to monic i have polynomial of 9 degree w(r).

My question is that: How can i use coppersmith attack? I tried sagemath small_root() but it dosnt return r(it return it only in special case when d = 0, and polynomial of 9 can be cast to polynomial of 3- bc it have only nonzero coefficient on $r^3, r^6, r^9$. Can my goal be achieved by changing implementation of small_root or by other mathematic transformation?

Example:

N = 55555
R = Zmod(N)
P.<x> = PolynomialRing( R, implementation='NTL' )

for k in range(1,5):
f     = (x-7)^k*(x-5)*(x-43)*(x-273)    # 7, 43, 273 are here for making 2 a root
d     = f.degree()
roots = [ r for r in R if f(r) == R(0) ]
info  = ( str(roots) if len(roots)<10
else str(roots[:10]) + ( '... (totally %s roots)' % len(roots) ) )
print "k=%s" % k
print "          ROOTS: %s" % info
print "    SMALL ROOTS: %s" % f.small_roots()


Code above doesnt return 2 even if it meet condition for Coppersmith's method.

Coppersmith's method, parameterized by $\epsilon$, finds all roots $\le \frac{1}{2} n^{\beta^2/\delta - \epsilon}$ to a polynomial $f(x)$ of degree $\delta$ modulo an unknown factor of $n$ of size $\ge n^\beta$. In your case, $\beta = 1$ and $\delta = \{4,5,6,7\}$.
Sage defaults $\epsilon = \beta/8$, which in your case would be $0.125$. However, $55555^{1^2/\{4,5,6,7\} - 0.125}$ is, respectively, $\{1.96, 1.13, 0.79, 0.61\}$. Only the first (almost) respects the bound. But if you tweak small_roots with an appropriate $\epsilon$, e.g., f.small_roots(epsilon=0.02), you should get more satisfactory answers.