Hensel lifting and bivariate polynomial factorisation over finite fields

被引：0

作者：

Gao, SH ^{[1
]}

Lauder, AGB

机构：

[1] Clemson Univ, Dept Math Sci, Clemson, SC 29634 USA

[2] Univ Oxford, Inst Math, Oxford OX1 3LB, England

来源：

MATHEMATICS OF COMPUTATION | 2002年 / 71卷 / 240期

关键词：

bivariate polynomial; finite field; Hensel lifting; factorisation; average-case complexity;

D O I：

暂无

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

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.

引用

页码：1663 / 1676

页数：14

共 16 条

[1] EUCLIDS ALGORITHM AND COMPUTATION OF POLYNOMIAL GREATEST COMMON DIVISORS
BROWN, WS
[J]. JOURNAL OF THE ACM, 1971, 18 (04) : 478 - &
[2] ON FAST MULTIPLICATION OF POLYNOMIALS OVER ARBITRARY ALGEBRAS
CANTOR, DG
KALTOFEN, E
[J]. ACTA INFORMATICA, 1991, 28 (07) : 693 - 701
[3] The arithmetic of polynomials in a Galois field
Carlitz, L
[J]. AMERICAN JOURNAL OF MATHEMATICS, 1932, 54 : 39 - 50
[4] COLLINS GE, 1979, LECT NOTES COMPUT SC, V72
[5] FLAJOLET P, 1996, LECT NOTES COMPUT SC, V1099
[6] Decomposition of polytopes and polynomials
Gao, S
Lauder, AGB
[J]. DISCRETE & COMPUTATIONAL GEOMETRY, 2001, 26 (01) : 89 - 104
[7] Absolute irreducibility of polynomials via newton polytopes
Gao, SH
[J]. JOURNAL OF ALGEBRA, 2001, 237 (02) : 501 - 520
[8] Geddes K.O., 1992, Algorithms for Computer Algebra
[9] Subquadratic-time factoring of polynomials over finite fields
Kaltofen, E
Shoup, V
[J]. MATHEMATICS OF COMPUTATION, 1998, 67 (223) : 1179 - 1197
[10] MULTIVARIATE POLYNOMIAL FACTORIZATION
MUSSER, DR
[J]. JOURNAL OF THE ACM, 1975, 22 (02) : 291 - 308

← 1 2 →