|
|
|
|
|
|
|
|
[GaL00a]
Shuhong Gao and Alan G.B. Lauder,
``Hensel lifting and polynomial factorisation,''
To appear in Mathematics of Computation . (17 pages)
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.
Click
here for PS file (396k)
Click
here for PDF file (150k)