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
BACH, E
SHOUP, V
[J]. 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
FLAJOLET, P
ODLYZKO, A
[J]. SIAM JOURNAL ON DISCRETE MATHEMATICS, 1990, 3 (02) : 216 - 240
[5] GAUSSIAN LIMITING DISTRIBUTIONS FOR THE NUMBER OF COMPONENTS IN COMBINATORIAL STRUCTURES
FLAJOLET, P
SORIA, M
[J]. 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
KNOPFMACHER, A
WARLIMONT, R
[J]. TRANSACTIONS OF THE AMERICAN MATHEMATICAL SOCIETY, 1995, 347 (06) : 2235 - 2243
[8] COUNTING IRREDUCIBLE FACTORS OF POLYNOMIALS OVER A FINITE-FIELD
KNOPFMACHER, A
KNOPFMACHER, J
[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
SHOUP, V
[J]. INFORMATION PROCESSING LETTERS, 1990, 33 (05) : 261 - 267

← 1 2 →