Finding Small Roots of Multivariate Polynomial Modulo an Integer in Sage (Coppersmith's Attack on RSA)

Question

I am trying to implement Coppersmith's attack to find small roots of an example bivariate polynomial.

$f(x,y) = (8x+7)(8y+7) - N \pmod{8}$

In this example, the results should be $x = 2$ and $y = 8$ (obviously you could brute force it, but that's besides the point).

For univariate polynomials, Coppersmith's attack is implemented via the .small_roots() function. However, it is to my understanding that finding small roots of a multivariate polynomial modulo an integer is not implemented in Sage. Is there any workaround code / method that will allow for small root finding of multivariate polynomials?

Relevant papers:

http://honors.cs.umd.edu/reports/lowexprsa.pdf

http://www.jscoron.fr/publications/bivariate.pdf

Thanks, and your time and effort are greatly appreciated.

Answer 1

If you calculate modulo $8$, your polynomial becomes constant: $f(x, y) = 1-N \pmod{8}$

So something is wrong about what you are trying to do!