Sharp precision in Hensel lifting for bivariate polynomial factorization |
| |
Authors: | Gré goire Lecerf. |
| |
Affiliation: | Laboratoire de mathématiques (UMR 8100 CNRS), université de Versailles Saint-Quentin-en-Yvelines, 45 avenue des États-Unis, 78035 Versailles, France |
| |
Abstract: | Popularized by Zassenhaus in the seventies, several algorithms for factoring polynomials use a so-called lifting and recombination scheme. Concerning bivariate polynomials, we present a new algorithm for the recombination stage that requires a lifting up to precision twice the total degree of the polynomial to be factored. Its cost is dominated by the computation of reduced echelon solution bases of linear systems. We show that our bound on precision is asymptotically optimal. |
| |
Keywords: | Polynomial factorization Hensel lifting |
|
| 点击此处可从《Mathematics of Computation》浏览原始摘要信息 |
|
点击此处可从《Mathematics of Computation》下载全文 |