Skip to main content

A new bivariate Hensel lifting algorithm for n factors

Resource type
Thesis type
(Thesis) M.Sc.
Date created
2019-08-13
Authors/Contributors
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.
Document
Identifier
etd20463
Copyright statement
Copyright is held by the author.
Permissions
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