Linear Hensel Lifting for Fp[x,y] and Z[x] with Cubic Cost
Michael Monagan · 2019
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]. There are two versions of Hensel lifting: Linear Hensel Lifting (LHL) and Quadratic Hensel Lifting (QHL). For polynomials in Z[x], if classical quadratic algorithms for multiplication and division are used, 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]. 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.