FINDING SMALL ROOTS FOR BIVARIATE POLYNOMIALS OVER THE RING OF INTEGERS

In this paper, we propose the first heuristic algorithm for finding small roots for a bivariate equation modulo an ideal I over the ring of integers R. Existing algorithms for solving polynomial equations with size constraints only work for bivariate modular equations over integers, and univariate modular equation over number fields. Both previous algorithms use a relation between the short vector in a skill-fully structured lattice and a size constrained solution. Our algorithm also fol-lows this framework, but we additionally use a polynomial factoring algorithm over number fields to recover a ‘ring’ root of a bivariate polynomial equation. As a result, when an LLL algorithm is employed to find a short vector, we can recover all small roots of a bivariate polynomial modulo I in polynomial time under some constraint.