Factorization of polynomials: Difference between revisions

Revision as of 17:39, 5 July 2025

Revision as of 18:45, 5 July 2025

Line 8:

When the long-known finite step algorithms were first put on computers, they turned out to be highly inefficient. The fact that almost any uni- or multivariate polynomial of degree up to 100 and with coefficients of a moderate size (up to 100 bits) can be factored by modern algorithms in a few minutes of computer time indicates how successfully this problem has been attacked during the past fifteen years. (Erich Kaltofen, 1982)

</blockquote>

Computer algebra systems such as Maxima, Maple, and Mathematica include robust implementations that automate the factorization of polynomials, using combinations of known, enhanced, and novel algorithms. These developments significantly reduce what were once complex and time-consuming tasks to operations that take only seconds. Such capabilities were first introduced in the late 1960s and early 1970s, notably through work by Paul S. Wang and others in the MIT Macsyma research group.<ref>{{cite conference |last=Fateman |first=Richard |title=A review of Macsyma: The original computer algebra system |booktitle=Proceedings of the 2008 International Symposium on Symbolic and Algebraic Computation (ISSAC '08) |publisher=ACM |year=2008 |pages=207–210 |doi=10.1145/1390768.1390803}}</ref><ref>{{cite journal |last1=Wang |first1=Paul S. |last2=Rothschild |first2=Richard J. |title=Factoring multivariate polynomials over the integers |journal=Journal of Symbolic Computation |volume=1 |issue=3 |year=1985 |pages=237–258 |doi=10.1016/S0747-7171(85)80030-4}}</ref><ref>{{cite conference |last=Wang |first=Paul S. |title=Early history of computer algebra systems |booktitle=Proceedings of the ACM Symposium on the History of Programming Languages (HOPL III) |year=2007 |publisher=ACM |url=https://doi.org/10.1145/1238844.1238856}}</ref><ref>{{cite web |title=About Maxima |url=https://maxima.sourceforge.io/about.html |website=Maxima Project |access-date=2025-07-05}}</ref>

Modern algorithms and computers can quickly factor [[#Factoring univariate polynomials over the integers|univariate polynomials]] of degree more than 1000 having coefficients with thousands of digits.<ref> An example of degree 2401, taking 7.35 seconds, is found in Section 4 in: Hart, van Hoeij, Novocin: [https://www.math.fsu.edu/~hoeij/papers/issac10/A.pdf ''Practical Polynomial Factoring in Polynomial Time''] ISSAC'2011 Proceedings, pp. 163–170 (2011).</ref> For this purpose, even for factoring over the [[rational number]]s and [[number field]]s, a fundamental step is a [[Factorization of polynomials over finite fields|factorization of a polynomial over a finite field]].