Hensel lifting and bivariate polynomial factorisation over finite fields
Shuhong Gao, Alan G. B. Lauder · Mathematics of Computation · 2001
This paper presents an average time analysis of a Hensel lifting based factorisation algorithm for bivariate polynomials over finite fields. It is shown that the average running time is almost linear in the input size. This explains why the Hensel lifting technique is fast in practice for most polynomials.