## Distinct degree factorizations for polynomials over a finite field

HTML articles powered by AMS MathViewer

- by Arnold Knopfmacher and Richard Warlimont PDF
- Trans. Amer. Math. Soc.
**347**(1995), 2235-2243 Request permission

## Abstract:

Let ${\widetilde {\mathbb {F}}_q}[X]$ denote the multiplicative semigroup of monic polynomials in one indeterminate $X$, over a finite field ${\mathbb {F}_q}$. We determine for each fixed $q$ and fixed $n$ the probability that a polynomial of degree $n$ in ${\mathbb {F}_q}[X]$ has irreducible factors of distinct degrees only. These results are of relevance to various polynomial factorization algorithms.## References

- Eric Bach and Victor Shoup,
*Factoring polynomials using fewer random bits*, J. Symbolic Comput.**9**(1990), no. 3, 229–239. MR**1056625**, DOI 10.1016/S0747-7171(08)80011-9
M. Ben-Or, - 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**, DOI 10.1090/S0025-5718-1981-0606517-5 - 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**, DOI 10.1007/978-0-8176-4729-2 - 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** - Donald E. Knuth,
*The art of computer programming. Vol. 2*, 2nd ed., Addison-Wesley Series in Computer Science and Information Processing, Addison-Wesley Publishing Co., Reading, Mass., 1981. Seminumerical algorithms. MR**633878** - Maurice Mignotte,
*Mathematics for computer algebra*, Springer-Verlag, New York, 1992. Translated from the French by Catherine Mignotte. MR**1140923**, DOI 10.1007/978-1-4613-9171-5 - Victor Shoup,
*On the deterministic complexity of factoring polynomials over finite fields*, Inform. Process. Lett.**33**(1990), no. 5, 261–267. MR**1049276**, DOI 10.1016/0020-0190(90)90195-4 - 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**, DOI 10.1007/978-94-011-1806-4

*Probabilistic algorithms in finite fields*, Proc. 22nd Annual Sympos. Foundations of Computer Science, 1981, pp. 394-398.

## Additional Information

- © Copyright 1995 American Mathematical Society
- 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