3
$\begingroup$

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.

$\endgroup$
3
$\begingroup$
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.

$\endgroup$
  • $\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$ – Alex Meiburg Sep 17 '16 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$ – Alex Meiburg Sep 18 '16 at 0:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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