Distinct degree factorizations for polynomials over a finite field

Authors:
Arnold Knopfmacher and Richard Warlimont

Journal:
Trans. Amer. Math. Soc. **347** (1995), 2235-2243

MSC:
Primary 11T06; Secondary 11T55

DOI:
https://doi.org/10.1090/S0002-9947-1995-1277121-X

MathSciNet review:
1277121

Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: Let denote the multiplicative semigroup of monic polynomials in one indeterminate , over a finite field . We determine for each fixed and fixed the probability that a polynomial of degree in has irreducible factors of distinct degrees only. These results are of relevance to various polynomial factorization algorithms.

**[1]**E. Bach and V. Shoup,*Factoring polynomials using fewer random bits*, J. Symbolic Comput.**9**(1990), 229-239. MR**1056625 (91h:11149)****[2]**M. Ben-Or,*Probabilistic algorithms in finite fields*, Proc. 22nd Annual Sympos. Foundations of Computer Science, 1981, pp. 394-398.**[3]**D. Cantor and H. Zassenhaus,*A new algorithm for factoring polynomials over finite fields*, Math. Comp.**36**(1981), 587-592. MR**606517 (82e:12020)****[4]**D. H. Greene and D. E. Knuth,*Mathematics for the analysis of algorithms*, 3rd ed., Birkhäuser, Basel, 1990. MR**1103115 (92c:68067)****[5]**J. Knopfmacher,*Analytic arithmetic of algebraic function fields*, Marcel Dekker, New York, 1979. MR**545904 (81d:10031)****[6]**D. E. Knuth,*The art of computer programming*, Vol. 2, 2nd ed., Addison-Wesley, Reading, MA, 1981. MR**633878 (83i:68003)****[7]**M. Mignotte,*Mathematics for computer algebra*, Springer-Verlag, Berlin, 1992. MR**1140923 (92i:68071)****[8]**V. Shoup,*On the deterministic complexity of factoring polynomials over finite fields*, Inform. Process. Lett.**33**(1990), 261-267. MR**1049276 (91f:11088)****[9]**I. E. Shparlinski,*Computational and algorithmic problems in finite fields*, Kluwer, Dordrecht, 1992. MR**1249064 (94j:11122)**

Retrieve articles in *Transactions of the American Mathematical Society*
with MSC:
11T06,
11T55

Retrieve articles in all journals with MSC: 11T06, 11T55

Additional Information

DOI:
https://doi.org/10.1090/S0002-9947-1995-1277121-X

Article copyright:
© Copyright 1995
American Mathematical Society