TL;DR: is there any library for multivariate polynomial root finding over the integers?
I'm trying to implement an attack on RSA with known bits of p by using Coppersmith, such as shown in this paper. In my case I have three blocks of lost bits, so it should be fine. The idea of Coppersmith is to first build and reduce a lattice, which is the costly part, and then convert some of the rows of the lattice back to polynomials that should have solutions over the integers that match the bits we're looking for. Finding the roots of a set of multivariate polynomials should have a very small cost when compared to lattice reduction.
However, I'm encountering a nasty surprise in my program. Lattice reductions take much (MUCH) less time than multivariate root finding, which is the limiting factor of my implementation. As of now I'm using a Sage script to solve the system, but it is too slow. Is there any library for integer multivariate root finding? At this point I don't care whether it's Python, C, C++, Fortran or whatever, I just want something fast that works for large integers.
Thanks in advance!
