On the bit complexity of polynomial system solving

NARDO GIMÉNEZ; GUILLERMO MATERA

Montreal

Congreso; Mathematical Congress of the Americas 2017; 2017

Mathematical Council of the Americas

We describe a probabilistic algorithm which solves a polynomial system over the rationals defined by a reduced regular sequence. Its bit complexity is roughly quadratic in the Bézout number of the system and linear in its bit size. Our algorithm solves the input system modulo a prime number p and applies p-adic lifting. Our approach is based on a new result on the bit length of a "lucky" prime p, namely one for which the reduction of the input system modulo p preserves certain fundamental geometric and algebraic properties of the original system. These results rely on the analysis of Chow forms associated to the set ofsolutions of the input system and effective arithmetic Nullstellensätze.