|
|||||
|
|
Hensel lifting and bivariate polynomial factorisation over finite fields |
|
| Authors: | Shuhong Gao Alan G. B. Lauder. |
| Affiliation: | Department of Mathematical Sciences, Clemson University, Clemson, SC 29634-0975 ; Mathematical Institute, Oxford University, Oxford OX1 3LB, United Kingdom |
| Abstract: | This paper presents an average time analysis of a Hensel lifting based factorisation algorithm for bivariate polynomials over finite fields. It is shown that the average running time is almost linear in the input size. This explains why the Hensel lifting technique is fast in practice for most polynomials. |
| Keywords: | Bivariate polynomial finite field Hensel lifting factorisation average-case complexity |
| 点击此处可从《Mathematics of Computation》浏览原始摘要信息 | |
| 点击此处可从《Mathematics of Computation》下载全文 | |