Lifting and recombination techniques for absolute factorization (Q2371310): Difference between revisions

Given a field \(K\) the authors consider the problem of factoring bivariate polynomials \(F\) of the polynomial ring \(K[x,y]\) over the algebraic closure \(\overline{K}\) (``absolute factorization''). The ground field \(K\) must have a characteristic zero or one larger than \(d(d-1)+1\), where \(d\) denotes the total degree of \(F\). They further assume that \(F\) is square-free and that for each integer \(d\) a computation tree is given that computes the product of two univariate polynomials of degree at most \(d\) with at most \(M(d)\) operations, independently of the base ring. Improving known results they develop an algorithm which provides the absolute factorization of \(F\) in \(O(d^3 M(d) \log (d))\) arithmetic operations in \(K\). For a test whether \(F\) is absolutely irreducible they get slightly better bounds. The authors also develop probabilistic methods for absolute factorization.