AMS Home Publications Membership Meetings & Conferences News & Public Outreach Notices of the AMS The Profession Programs Government Relations Education Giving to the AMS About the AMS
MathSciNet® Member Directory Bookstore Journals Employment Services Giving to the AMS
Bookstore MathSciNet® Meetings Journals Membership Employment Services Giving to the AMS About the AMS
The AMS website will be down on Saturday December 11th from 8:30 am to approximately 11:30 am for maintenance.
ISSN 1088-6850(online) ISSN 0002-9947(print)
Journals Home Search My Subscriptions Subscribe
Your device is paired with
for another days.
Previous issue | This issue | Most recent issue | All issues (1900–Present) | Next issue | Previous article | Articles in press | Recently published articles | Next article
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?)
Eric Bach and Victor Shoup, Factoring polynomials using fewer random bits, J. Symbolic Comput. 9 (1990), no. 3, 229–239. MR 1056625, DOI https://doi.org/10.1016/S0747-7171%2808%2980011-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 https://doi.org/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
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 Publishing Co., Reading, Mass., 1981. Seminumerical algorithms; Addison-Wesley Series in Computer Science and Information Processing. MR 633878
Maurice Mignotte, Mathematics for computer algebra, Springer-Verlag, New York, 1992. Translated from the French by Catherine Mignotte. MR 1140923
Victor Shoup, On the deterministic complexity of factoring polynomials over finite fields, Inform. Process. Lett. 33 (1990), no. 5, 261–267. MR 1049276, DOI https://doi.org/10.1016/0020-0190%2890%2990195-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
E. Bach and V. Shoup, Factoring polynomials using fewer random bits, J. Symbolic Comput. 9 (1990), 229-239. M. Ben-Or, Probabilistic algorithms in finite fields, Proc. 22nd Annual Sympos. Foundations of Computer Science, 1981, pp. 394-398. D. Cantor and H. Zassenhaus, A new algorithm for factoring polynomials over finite fields, Math. Comp. 36 (1981), 587-592. D. H. Greene and D. E. Knuth, Mathematics for the analysis of algorithms, 3rd ed., Birkhäuser, Basel, 1990. J. Knopfmacher, Analytic arithmetic of algebraic function fields, Marcel Dekker, New York, 1979. D. E. Knuth, The art of computer programming, Vol. 2, 2nd ed., Addison-Wesley, Reading, MA, 1981. M. Mignotte, Mathematics for computer algebra, Springer-Verlag, Berlin, 1992. V. Shoup, On the deterministic complexity of factoring polynomials over finite fields, Inform. Process. Lett. 33 (1990), 261-267. I. E. Shparlinski, Computational and algorithmic problems in finite fields, Kluwer, Dordrecht, 1992.
Retrieve articles in Transactions of the American Mathematical Society with MSC: 11T06, 11T55
Retrieve articles in all journals with MSC: 11T06, 11T55
Article copyright: © Copyright 1995 American Mathematical Society
Join the AMS
AMS Conferences
News & Public Outreach
Math in the Media
Mathematical Imagery
Mathematical Moments
Data on the Profession
Fellows of the AMS
Mathematics Research Communities
AMS Fellowships
Collaborations and position statements
Appropriations Process Primer
Congressional briefings and exhibitions
About the AMS
Jobs at AMS
Notices of the AMS · Bulletin of the AMS
American Mathematical Society · 201 Charles Street Providence, Rhode Island 02904-2213 · 401-455-4000 or 800-321-4267
AMS, American Mathematical Society, the tri-colored AMS logo, and Advancing research, Creating connections, are trademarks and services marks of the American Mathematical Society and registered in the U.S. Patent and Trademark Office.
© Copyright , American Mathematical Society · Privacy Statement · Terms of Use · Accessibility