多項式の因数分解
有理係数の範囲での一次因子は何れも有理根テストによって見つけることができる。すなわち、因数分解したい多項式が a n x n + a n − 1 x n − 1 + ⋯ + a 1 x + a 0 {\textstyle a_{n}x^{n}+a_{n-1}x^{n-1}+\cdots +a_{1}x+a_{0}} であるとき、取りうる任意の一次因子 b 1 x − b 0 {\textstyle b_{1}x-b_{0}} は、b1 が an の整数因子かつ b0 は a0 の整数因子でなければならない。そのような整数因子すべての組み合わせについて有効か否か確かめて、有効な因子については筆算(英語版)などして分解を得る。もとの多項式が次数 2 以上の因子を少なくとも二つ含む積であるならば、先に述べた仕方では部分的な分解しか得られないが、そうでなければ完全に一次因子のみの積に分解できることになる。特に、非一次因子がちょうど一つである場合には、それは全ての一次因子を分解し尽くした残りの部分の多項式として取り出せる。三次多項式の場合には、それが完全に因数分解できるならば有理根テストを用いるだけでその分解が決定できる(それは一つの一次因子と二次の既約因子との積であるか、さもなくば三つの一次因子の積である)ことは注目に値する。
Kaltofen, Erich (1990), “Polynomial Factorization 1982-1986”, in D. V. Chudnovsky; R. D. Jenks, Computers in Mathematics, Lecture Notes in Pure and Applied Mathematics, 125, Marcel Dekker, Inc.
Kaltofen, Erich (1992), “Polynomial Factorization 1987–1991”, Proceedings of Latin ’92, Springer Lect. Notes Comput. Sci., 583, Springer, http://www4.ncsu.edu/~kaltofen/bibliography/92/Ka92_latin.pdf 2012年10月14日閲覧。
Ivanyos, Gabor; Marek, Karpinski; Saxena, Nitin (2009), “Schemes for Deterministic Polynomial Factoring”, Proc. ISSAC 2009: 191–198, arXiv:0804.1974, doi:10.1145/1576702.1576730
↑ FT Schubert: De Inventione Divisorum Nova Acta Academiae Scientiarum Petropolitanae v.11, p. 172-182(1793)
↑ 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).
↑ van der Waerden 1970, §5.4, 5.6.
↑ M. van Hoeij: Factoring polynomials and the knapsack problem. Journal of Number Theory, 95, 167-189, (2002).