Toric Factorisation of Bivariate Polynomials

Toric Factorisation of Bivariate Polynomials

Although there exists now fast algorithms for factoring bivariate polynomials, most of them apply to polynomials that are generic with respect to the total degree, with a complexity that depends on it. Nevertheless, when the polynomial is sparse, the degree reveals to be a poor complexity indicator, and one should rather consider finer geometric invariants. In that talk, I will prove the existence of a deterministic algorithm that, given f Q[x, y] generic with respect to its ∈ Newton polytope, and given the rational univariate factorizations of its exterior facet polynomials, computes the rational factorization of f in small polynomial time with respect to the volume of the Newton polytope. When the input polynomial is sparse enough, my algorithm improves the fastest actual ones. The proof uses residual criterions for algebraic osculation at the toric infinity, and combines cohomological properties of toric varieties with the irreducibility criterion of Ruppert.