A new bivariate Hensel lifting algorithm for n factors

We present a new algorithm for performing Linear Hensel Lifting of bivariate polynomials over the finite field F_p for some prime p. Our algorithm lifts n monic, univariate polynomials to recover the factors of a polynomial A(x,y) in F_p[x,y] which is monic in x, and bounded by degrees d_x = deg(A,x) and d_y = deg(A,y). Our algorithm improves upon Bernardin's algorithm in [2] and reduces the number of arithmetic operations in F_p from O(n d_x^2 d_y^2) to O(d_x^2 d_y + d_x d_y^2) for p >= d_x. Experimental results in C verify that our algorithm compares favorably with Bernardin's for large degree polynomials.