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, Probabilistic algorithms in finite fields, Proc. 22nd Annual Sympos. Foundations of Computer Science, 1981, pp. 394-398.
- 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
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