Factoring bivariate lacunary polynomials without heights

Abstract

We present an algorithm which computes the multilinear factors of bivariate lacunary polynomials. It is based on a new Gap Theorem which allows to test whether a polynomial of the form P(X,X+1) is identically zero in time polynomial in the number of terms of P(X,Y). The algorithm we obtain is more elementary than the one by Kaltofen and Koiran (ISSAC'05) since it relies on the valuation of polynomials of the previous form instead of the height of the coefficients. As a result, it can be used to find some linear factors of bivariate lacunary polynomials over a field of large finite characteristic in probabilistic polynomial time.

25 pages, 1 appendix

References in corpus (2)

• Wronskians and linear independence
• Factoring bivariate lacunary polynomials without heights

Cited by in corpus (6)

• What Can (and Can't) we Do with Sparse Polynomials?
• Bounded-degree factors of lacunary multivariate polynomials
• Factoring bivariate lacunary polynomials without heights
• Pseudorandomness for Multilinear Read-Once Algebraic Branching Programs, in any Order
• Lacunaryx: Computing bounded-degree factors of lacunary polynomials
• Computing low-degree factors of lacunary polynomials: a Newton-Puiseux approach