|
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.
|