Factoring Sparse Bivariate Polynomials Using the Priority Queue

We revisit the polytope method for factoring sparse bivariate polynomials over finite fields, and address the bottleneck arising from solving the Hensel lifting equations using the sparse distributed polynomial representation. We revise the analysis when polynomials are represented as such, which reveals how performing the polynomial multiplications and ensuing additions in separate (serialised) phases causes the Hensel lifting phase to suffer from poor work, space, and I/O complexity, and hinges on the size of the intermediary output, as size is defined in the sparse distributed representation. We propose to overlap all polynomial arithmetic in one Hensel lifting step using a MAX priority queue. The overlapping approach adapts not only to the growth in the degree of the input polynomial but also to irregularities in the sparsity of intermediary output. It also results in evading expression swell and reducing the overall work and space complexity by an order of magnitude. When the priority queue is implemented as a cache-oblivious data structure, the overlapping approach achieves an order of magnitude improvement in I/O over the serialised approach, even when the latter is using cache efficient structures to assist in polynomial multiplications and additions. We present empirical results for the polytope method using a max-heap implementation of the global priority queue, which demonstrate extremely superior performance, and specifically against Magma, for sufficiently sparse input polynomials of very high degrees.