A softly optimal Monte Carlo algorithm for solving bivariate polynomial systems over the integers

We give an algorithm for the symbolic solution of polynomial systems in Z[X,Y]Z[X,Y]. Following previous work with Lebreton, we use a combination of lifting and modular composition techniques, relying in particular on Kedlaya and Umans’ recent quasi-linear time modular composition algorithm.The main contribution in this paper is an adaptation of a deflation algorithm of Lecerf, that allows us to treat singular solutions for essentially the same cost as the regular ones. Altogether, for an input system with degree dd and coefficients of bit-size hh, we obtain Monte Carlo algorithms that achieve probability of success at least 1−1/2P1−1/2P, with running time d2+εÕ(d2+dh+dP+P2) bit operations, for any ε>0ε>0, where the Õ notation indicates that we omit polylogarithmic factors.