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

A recent bivariate factorisation algorithm appeared in Abu-Salem et al. [Abu-Salem, F., Gao, S., Lauder, A., 2004. Factoring polynomials via polytopes. In: Proc. ISSAC’04. pp. 4–11] based on the use of Newton polytopes and a generalisation of Hensel lifting. Although possessing 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 et al. [Abu-Salem, F., Gao, S., Lauder, A., 2004. Factoring polynomials via polytopes. In: Proc. ISSAC’04. pp. 4–11] 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(d4) and O(d2) 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 non-zero terms of the input polynomial, so that the input size becomes dependent 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 given a degree d sparse polynomial whose number of terms t satisfies t