Linear Hensel Lifting for ℤ[x] and 𝔽q[x,y] with Cubic Cost.

Michael Monagan
Department of Mathematics
Simon Fraser University

Thursday July 11th, 9:30am in BLU 10901.

Abstract

Hensel lifting is a key tool that is used to factor polynomials and
compute polynomial GCDs in Z[x], Z[x1,...,xn] and Fq[x1,...,xn] where
Fq is a finite field with q elements.  There are two versions of Hensel
lifting: Linear Hensel Lifting (LHL) and Quadratic Hensel Lifting (QHL).

For polynomials in Z[x], if we use classical quadratic algorithms for
polynomial and integer multiplication and division, LHL and QHL
both have a quartic complexity.  If asymptotically fast arithmetic is used,
up to logarithmic factors, LHL is cubic and QHL is quadratic.

In this work we present cubic algorithms for LHL for Z[x] and Fp[x,y]
which use classical quadratic algorithms.
We present details of C implementations of our cubic algorithms for
Z[x] and Fp[x,y].  We compare both with Magma implementations of QHL
using fast arithmetic.  For both cases, we find that our our cubic LHL
outperforms Magma's fast QHL for a very wide range of input sizes.
Thus our cubic LHL seems to be the best in practice.