An efficient sparse adaptation of the polytope method over F_p and a record−high binary bivariate factorisation

Abstract

A recent bivariate factorisation algorithm appeared in (Abu Salem, Gao and Lauder, 2004) based on the use of Newton polytopes and a generalisation of Hensel lifting. Although possessing of a worst case exponential running time like the Hensel lifting algorithm, the polytope method should perform well for sparse polynomials whose Newton polytopes have very few Minkowski decompositions. A preliminary implementation in (Abu Salem, Gao and Lauder, 2004) indeed reflects this property, but does not exploit the fact that the algorithm preserves the sparsity of the input polynomial, so that the total amount of work and space required are O(d⁴) and O(d²) respectively, for an input bivariate polynomial of total degree d. In this paper, we show that the polytope method can be made sensitive to the number of nonzero terms of the input polynomial, so that the input size becomes depedent on both the degree and the number of terms of the input bivariate polynomial. We describe a sparse adaptation of the polytope method over finite fields with prime order, which requires fewer bit operations and memory references for sparse polynomials which are known to be the product of two sparse factors. Under this condition, our refinement reduces the amount of work per extension of a coprime dominating edge factorisation and the total spatial complexity to O(td²+t³d) bit operations and O(t⁰⁽¹⁾d) bits of memory respectively. To the best of our knowledge, the sparse binary factorisations achieved using this adaptation are of the highest degree so far, reaching a world record degree of 20000 for a very sparse bivariate polynomial over F₂.