Artículo
On the bit complexity of polynomial system solving
Fecha de publicación:
04/2019
Editorial:
Academic Press Inc Elsevier Science
Revista:
Journal Of Complexity
ISSN:
0885-064X
e-ISSN:
1090-2708
Idioma:
Inglés
Tipo de recurso:
Artículo publicado
Clasificación temática:
Resumen
We describe and analyze a randomized algorithm which solves a polynomial system over the rationals defined by a reduced regular sequence outside a given hypersurface. We show that its bit complexity is roughly quadratic in the Bézout number of the system and linear in its bit size. The algorithm solves the input system modulo a prime number p and applies p-adic lifting. For this purpose, we establish a number of results 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 of solutions of the input system and effective arithmetic Nullstellensätze.
Archivos asociados
Licencia
Identificadores
Colecciones
Articulos(SEDE CENTRAL)
Articulos de SEDE CENTRAL
Articulos de SEDE CENTRAL
Citación
Gimenez, Nardo Ariel; Matera, Guillermo; On the bit complexity of polynomial system solving; Academic Press Inc Elsevier Science; Journal Of Complexity; 51; 4-2019; 20-67
Compartir
Altmétricas