Phân tích đa thức

Trong toán học và đại số máy tính, việc phân tích đa thức  là quá trình diễn đạt một đa thức với hệ số thuộc một trường hoặc là số nguyên thành một tích của các đa thức không thể phân tích được có hệ số trong cùng một miền. Sự phân tích đa thức là một trong những công cụ cơ bản của các hệ thống đại số máy tính.

Lịch sử của việc phân tích đa thức bắt đầu với Hermann Schubert, người năm 1793 mô tả thuật toán phân tích đa thức đầu tiên,^{[cần dẫn nguồn]} và Leopold Kronecker, người đã khám phá lại thuật toán của Schubert vào năm 1882 và mở rộng nó tới đa thức đa biến số và các hệ số trong một phép mở rộng đại số. Nhưng hầu hết các kiến thức về chủ đề này không phát triển cho đến năm 1965 với hệ thống đại số máy tính đầu tiên.Trong một cuộc khảo sát về chủ đề này, Erich Kaltofen đã viết vào năm 1982 (xem các thư mục dưới đây):

Khi các thuật toán bước hữu hạn đã biết trước được đưa ra lần đầu tiên trên máy tính, chúng tỏ ra không hiệu quả. Thực tế là hầu hết bất kỳ một đa thức đơn hoặc nhiều đa thức có bậc lên đến 100 và có các hệ số có kích thước vừa phải (lên tới 100 bit) có thể được tính toán theo các thuật toán hiện đại trong một vài phút của thời gian máy tính cho thấy bài toán này đã được nỗ lực giải quyết trong suốt mười lăm năm qua.

Ngày nay, các thuật toán hiện đại và máy tính có thể nhanh chóng phân tích các đa thức đơn biến với bậc hơn 1000 có hệ số với hàng ngàn chữ số.^[1]

Tham khảo

1. An example of degree 2401, taking 7.35 seconds, is found in Section 4 in: Hart, van Hoeij, Novocin: Practical Polynomial Factoring in Polynomial Time ISSAC'2011 Proceedings, p. 163-170 (2011).

Sách tham khảo

• Fröhlich, A.; Shepherson, J. C. (1955), “On the factorisation of polynomials in a finite number of steps”, Mathematische Zeitschrift, 62 (1): 331–334, doi:10.1007/BF01180640, ISSN 0025-5874
• Trager, B.M., “Algebraic Factoring and Rational Function Integration”, Proc. SYMSAC 76
• Bernard Beauzamy, Per Enflo, Paul Wang (tháng 10 năm 1994). “Quantitative Estimates for Polynomials in One or Several Variables: From Analysis and Number Theory to Symbolic and Massively Parallel Computation”. Mathematics Magazine. 67 (4): 243–257. doi:10.2307/2690843. JSTOR 2690843. (accessible to readers with undergraduate mathematics)
• Cohen, Henri (1993). A course in computational algebraic number theory. Graduate Texts in Mathematics. 138. Berlin, New York: Springer-Verlag. ISBN 978-3-540-55640-4. MR 1228206.
• Kaltofen, Erich (1982), “Factorization of polynomials”, trong B. Buchberger; R. Loos; G. Collins (biên tập), Computer Algebra, Springer Verlag, CiteSeerX 10.1.1.39.7916
• Knuth, Donald E (1997). “4.6.2 Factorization of Polynomials”. Seminumerical Algorithms. The Art of Computer Programming. 2 . Reading, Massachusetts: Addison-Wesley. tr. 439–461, 678–691. ISBN 0-201-89684-2.
• Lenstra, A. K.; Lenstra, H. W.; Lovász, László (1982). “Factoring polynomials with rational coefficients”. Mathematische Annalen. 261 (4): 515–534. doi:10.1007/BF01457454. ISSN 0025-5831. MR 0682664.
• Van der Waerden, Algebra (1970), trans. Blum and Schulenberger, Frederick Ungar.

Đọc thêm

• Kaltofen, Erich (1990), “Polynomial Factorization 1982-1986”, trong D. V. Chudnovsky; R. D. Jenks (biên tập), Computers in Mathematics, Lecture Notes in Pure and Applied Mathematics, 125, Marcel Dekker, Inc., CiteSeerX 10.1.1.68.7461
• Kaltofen, Erich (1992), “Polynomial Factorization 1987–1991”, Proceedings of Latin ’92 (PDF), Springer Lect. Notes Comput. Sci., 583, Springer, truy cập ngày 14 tháng 10 năm 2012
• Ivanyos, Gabor; Marek, Karpinski; Saxena, Nitin (2009), “Schemes for Deterministic Polynomial Factoring”, Proc. ISSAC 2009: 191–198, doi:10.1145/1576702.1576730