Skip to main content

A new bivariate Hensel lifting algorithm for n factors

Resource type
Thesis type
(Thesis) M.Sc.
Date created
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.
Copyright statement
Copyright is held by the author.
This thesis may be printed or downloaded for non-commercial research and scholarly purposes.
Scholarly level
Supervisor or Senior Supervisor
Thesis advisor: Monagan, Michael
Member of collection
Download file Size
etd20463.pdf 691.53 KB

Views & downloads - as of June 2023

Views: 13
Downloads: 0