A new bivariate Hensel lifting algorithm for n factors

Author: 
File(s): 
Date created: 
2019-08-13
Identifier: 
etd20463
Supervisor(s): 
Michael Monagan
Department: 
Science: Department of Mathematics
Keywords: 
Hensel lifting
Polynomial factorization
Modular methods
Arithmetic operations
Bivariate polynomials
Abstract: 

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.

Thesis type: 
(Thesis) M.Sc.
Document type: 
Thesis
Rights: 
This thesis may be printed or downloaded for non-commercial research and scholarly purposes. Copyright remains with the author.
Statistics: