ASKSAGE: Sage Q&A Forum - Latest question feedhttp://ask.sagemath.org/questions/Q&A Forum for SageenCopyright Sage, 2010. Some rights reserved under creative commons license.Thu, 29 Jun 2017 22:30:13 -0500Finding Small Roots of Multivariate Polynomial Modulo an Integerhttp://ask.sagemath.org/question/38135/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://www.jscoron.fr/publications/bivariate.pdf
Thanks, and your time and effort are greatly appreciated.SanguiniusThu, 29 Jun 2017 22:30:13 -0500http://ask.sagemath.org/question/38135/Finding Small Roots of Multivariate Polynomials Modulo an Integerhttp://ask.sagemath.org/question/38134/finding-small-roots-of-multivariate-polynomials-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) \pmod{8}$
It is to my understanding that finding small roots of a multivariate polynomial modulo an integer is not implemented in Sage. However, is there a workaround code / method that will allow for small root finding of the above polynomial, and others of the same form?
Thanks, and your time and effort are greatly appreciated.
SanguiniusThu, 29 Jun 2017 22:28:46 -0500http://ask.sagemath.org/question/38134/