On the degrees of irreducible factors of polynomials over a finite field

被引：5

作者：

Knopfmacher, A ^{[1
]}

机构：

[1] Univ Witwatersrand, Dept Appl & Computat Math, ZA-2050 Wits, South Africa

来源：

DISCRETE MATHEMATICS | 1999年 / 196卷 / 1-3期

关键词：

D O I：

10.1016/S0012-365X(98)00174-5

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

Let (F) over tilde(q)[X] denote the multiplicative semigroups of monic polynomials in one indeterminate X, over a finite field F-q. We determine for each fixed q, the asymptotic average number of distinct degrees of the irreducible factors of a polynomial of degree n in (F) over tilde(q)[X]. The results are of relevance to various polynomial factorization algorithms. (C) 1999 Elsevier Science B.V. All rights reserved.

引用

页码：197 / 206

页数：10

共 13 条

[1] FACTORING POLYNOMIALS USING FEWER RANDOM BITS [J].

BACH, E ;

SHOUP, V .

JOURNAL OF SYMBOLIC COMPUTATION, 1990, 9 (03) :229-239

[2]

BENOR M, 1981, P 22 IEEE S FDN COMP, P394

[3]

CANTOR DG, 1981, MATH COMPUT, V36, P587, DOI 10.1090/S0025-5718-1981-0606517-5

[4] SINGULARITY ANALYSIS OF GENERATING-FUNCTIONS [J].

FLAJOLET, P ;

ODLYZKO, A .

SIAM JOURNAL ON DISCRETE MATHEMATICS, 1990, 3 (02) :216-240

[5] GAUSSIAN LIMITING DISTRIBUTIONS FOR THE NUMBER OF COMPONENTS IN COMBINATORIAL STRUCTURES [J].

FLAJOLET, P ;

SORIA, M .

JOURNAL OF COMBINATORIAL THEORY SERIES A, 1990, 53 (02) :165-182

[6]

FLAJOLET P, 1996, LECT NOTES COMPUTER, V1099, P232, DOI DOI 10.1007/3-540-61440-0_131

[7] DISTINCT DEGREE FACTORIZATIONS FOR POLYNOMIALS OVER A FINITE-FIELD [J].

KNOPFMACHER, A ;

WARLIMONT, R .

TRANSACTIONS OF THE AMERICAN MATHEMATICAL SOCIETY, 1995, 347 (06) :2235-2243

[8] COUNTING IRREDUCIBLE FACTORS OF POLYNOMIALS OVER A FINITE-FIELD [J].

KNOPFMACHER, A ;

KNOPFMACHER, J .

DISCRETE MATHEMATICS, 1993, 112 (1-3) :103-118

[9]

Knuth DE, 1981, ART COMPUTER PROGRAM, V2

[10] ON THE DETERMINISTIC COMPLEXITY OF FACTORING POLYNOMIALS OVER FINITE-FIELDS [J].

SHOUP, V .

INFORMATION PROCESSING LETTERS, 1990, 33 (05) :261-267

← 1 2 →