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

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]**Eric Bach and Victor Shoup,*Factoring polynomials using fewer random bits*, J. Symbolic Comput.**9**(1990), no. 3, 229–239. MR**1056625**, 10.1016/S0747-7171(08)80011-9**[2]**M. Ben-Or,*Probabilistic algorithms in finite fields*, Proc. 22nd Annual Sympos. Foundations of Computer Science, 1981, pp. 394-398.**[3]**David G. Cantor and Hans Zassenhaus,*A new algorithm for factoring polynomials over finite fields*, Math. Comp.**36**(1981), no. 154, 587–592. MR**606517**, 10.1090/S0025-5718-1981-0606517-5**[4]**Daniel H. Greene and Donald E. Knuth,*Mathematics for the analysis of algorithms*, 3rd ed., Progress in Computer Science and Applied Logic, vol. 1, Birkhäuser Boston, Inc., Boston, MA, 1990. MR**1103115****[5]**John Knopfmacher,*Analytic arithmetic of algebraic function fields*, Lecture Notes in Pure and Applied Mathematics, vol. 50, Marcel Dekker, Inc., New York, 1979. MR**545904****[6]**Donald E. Knuth,*The art of computer programming. Vol. 2*, 2nd ed., Addison-Wesley Publishing Co., Reading, Mass., 1981. Seminumerical algorithms; Addison-Wesley Series in Computer Science and Information Processing. MR**633878****[7]**Maurice Mignotte,*Mathematics for computer algebra*, Springer-Verlag, New York, 1992. Translated from the French by Catherine Mignotte. MR**1140923****[8]**Victor Shoup,*On the deterministic complexity of factoring polynomials over finite fields*, Inform. Process. Lett.**33**(1990), no. 5, 261–267. MR**1049276**, 10.1016/0020-0190(90)90195-4**[9]**Igor E. Shparlinski,*Computational and algorithmic problems in finite fields*, Mathematics and its Applications (Soviet Series), vol. 88, Kluwer Academic Publishers Group, Dordrecht, 1992. MR**1249064**

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:
http://dx.doi.org/10.1090/S0002-9947-1995-1277121-X

Article copyright:
© Copyright 1995
American Mathematical Society