Programming Research Group Research Report RR-04-07

Fatima Abu Salem, Shuhong Gao and Alan G. B. Lauder

April 2004, 27pp.

Abstract

"We introduce a new approach to multivariate polynomial factorisation which incorporates ideas from polyhedral geometry, and generalises Hensel lifting. Our main contribution is to present an algorithm for factoring bivariate polynomials which is able to exploit to some extent the sparsity of polynomials. We give details of an implementation which we used to factor randomly chosen sparse and composite polynomials of high degree over the binary field."