Remote Access Transactions of the American Mathematical Society
Green Open Access

Transactions of the American Mathematical Society

ISSN 1088-6850(online) ISSN 0002-9947(print)

 
 

 

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 $ {\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 [Enhancements On Off] (What's this?)

  • [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)

Similar Articles

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

American Mathematical Society