Finding Small Roots of Multivariate Polynomial Modulo an Integer
I am trying to apply Coppersmith's attack to find small roots of an example polynomial
$f(x,y) = (8x+7)(8y+7) - N \pmod{8}$
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 the above polynomial, and others of the same form?
In this example, the results should be $x = 2$ and $y = 8$.
Relevant papers:
http://honors.cs.umd.edu/reports/lowexprsa.pdf (http://honors.cs.umd.edu/reports/lowe...)
http://www.jscoron.fr/publications/bivariate.pdf (http://www.jscoron.fr/publications/bi...)
Thanks, and your time and effort are greatly appreciated.
Is your example really representative of your needs? Because in the example you provide, there are two features that allow you to compute the roots efficiently:
You look for roots modulo $8$: With two variables taking $8$ different values each, you can use a brute force algorithm and test the $64$ pairs $(x,y)$.
I edited the OP a bit. Unfortunately I don't have enough Karma to create clickable hyperlinks, but I put some relevant papers in the description. The first paper is where the example came from, and it uses the Coppersmith method described in the second link to obtain those roots. For univariate polynomials, Coppersmith's attack is already implemented via the .small_roots() method. However, this is not the case for multivariate polynomials, where I get a NotImplementedError. As such, I was asking to see if there was a potential workaround.
If you work modulo 8, your polynomial f is constant, right ?
I believe so. However, the objective is to find $x$ and $y$ such that $(8x+7)(8y+7)−N \pmod{8} = 0$.
$x = 2$ and $y = 8$ are thus roots of the polynomial. The goal of this problem is to find small integer zeroes of bivariate polynomials modulo a given integer via Lattice Basis Reduction (as shown here: https://en.wikipedia.org/wiki/Coppersmith_method (https://en.wikipedia.org/wiki/Coppers...)).
In the context of the RSA cryptosystem, $(8x+7)$ and $8y+7& would be the prime factors of the modulus N.
The posted link http://honors.cs.umd.edu/reports/lowexprsa.pdf gives us an other story. Citing it "Actually Theorem 2 all together isn’t very fun, but it does provide the framework to produce a corollary that is immensely helpful..." and this Cor can be simply understood in a simple case. Let $N = pq= 2017\cdot 2027=4088459< 2^{24}$. We want the two (prime) factors. Fix $r=64\ge 2^{24/4}$. Assume we know $p_0=33$, the rest of $p$ modulo $r$. Then $q_0=43$ is... We search integer solutions for $$ (64x+33)(64y+43) = 4088459\ .$$ And of course integer not modulo $64$, since we arranged it is so while computing $q_0$ !
And here we can start the brute force search.