A lifting and recombination algorithm for rational factorization of sparse polynomials

Martin Weimann (1, 2)

1 UNICAEN - Université de Caen Normandie
2 LMNO - Laboratoire de Mathématiques Nicolas Oresme

We propose a new lifting and recombination scheme for rational bivariate polynomial factorization that takes advantage of the Newton poly-tope geometry. We obtain a deterministic algorithm that can be seen as a sparse version of an algorithm of Lecerf, with now a polynomial complexity in the volume of the Newton polytope. We adopt a geometrical point of view, the main tool being derived from some algebraic osculation criterions in toric varieties.

Domains: Mathematics [math]; Commutative Algebra [math.AC]; Algebraic Geometry [math.AG]

Martin Weimann. A lifting and recombination algorithm for rational factorization of sparse polynomials. Journal of Complexity, 2010, 26 (6), pp.608-628. ⟨10.1016/j.jco.2010.06.005⟩. ⟨hal-02137320⟩