In http://link.springer.com/chapter/10.1007%2F3-540-68339-9_14#page-7 is presented a method for finding small solutions to multivariate polynomials. (Although here he mentions that it "is not rigorous", several other papers have cited it and make use of it in practice.) Is there a function or convenient snippet for accomplishing this in Mathematica? Or if not, perhaps at least a reference for how to write this slightly more algorithmically?

Edit: In particular, I need this for the case of solving quadratics in two variables over large composite fields of unknown factorization, efficiently.


1 Answer 1

f = PolynomialMod[Expand[(1 + x) (2 + y) (3 + xy) (2 + z) (4 + z)], 5]

3+3 x+xy+x xy+4 y+4 x y+3 xy y+3 x xy y+z+x z+2 xy z+2 x xy z+3 y z+3 x y z+xy y z+x xy y z+z^2+x z^2+2 xy z^2+2 x xy z^2+3 y z^2+3 x y z^2+xy y z^2+x xy y z^2

FactorSquareFree[f, Modulus -> 5]

(1 + x) (3 + xy) (2 + y) (3 + z + z^2)

As we can see this works. Not sure though that Factor uses the Coppersmith algorithm. Maybe one can use some of the functions employing the LLL scheme such as FindIntegerNullVectorand LatticeReduce to implement it.

  • $\begingroup$ I'll try this out in the morning. It's important that I get reasonable efficiency for large coefficients and moduli. When I tried it with Solve it was definitely operating exponentially slowly. $\endgroup$ Commented Sep 17, 2016 at 11:46
  • $\begingroup$ Upon trying this -- FactorSquareFree requires that the Modulus be prime -- which kind of defeats the purpose of Coppersmith's algorithm. I agree that LatticeReduce will be necessary, but I'm not sure about building the matrix which I will reduce, or interpreting the results. $\endgroup$ Commented Sep 18, 2016 at 0:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.