Efficient Multivariate Factorization over Finite Fields - Abstract

Laurent Bernardin, ETH Zürich

Mike Monagan, SFU Canada

We describe the Maple implementation of multivariate factorization over general finite fields. Our first implementation is available in Maple V Release 3. We give selected details of the algorithms and show several ideas that were used to improve its efficiency. Most of the improvements presented here are incorporated in Maple V Release 4. In particular, we show that we needed a general tool for implementing computations in GF(p^k)[x_1,x_2,...,x_v]. We also needed an efficient implementation of our algorithms in Zp[y][x] because any multivariate factorization may depend on several bivariate factorizations. The efficiency of our implementation is illustrated by the ability to factor bivariate polynomials with over a million monomials over a small prime field.