多項式因式分解（polynomial factorization）

把 60 分解成 2 * 2 * 3 * 5，是把一個數拆成它不可約的積木。多項式因式分解對多項式做同樣的事：它把 x^4 - 1 改寫成 (x - 1)(x + 1)(x^2 + 1)，一個在所選數系中無法再拆的因子乘積。這是質因數分解的符號對應，也是電腦代數系統的招牌能力之一。

什麼算「不可約」取決於係數住在哪裡。在有理數上，x^2 + 1 無法分解；在複數上它裂成 (x - i)(x + i)。出人意料的是，分解整係數多項式遠比分解整數（密碼學的根基）容易——有高效的演算法存在。現代的因式分解器分成聰明的幾個階段：先用多項式與其導數的多項式最大公因式取出重複因子（無平方因子分解）；再把無平方部分在一個小質數模下分解，那裡有限體方法（柏勒坎普與坎托-薩森豪斯演算法）跑得飛快；最後用亨澤爾提升（牛頓法的 p 進版本）把那些模下的因子提升回整係數因子。「在質數模下分解再提升」這套策略貫穿了大半的精確計算。

因式分解在凡是想要精確結構之處都重要：化簡表達式、找精確根、積分有理函數（部分分式需要分母被分解）、以及符號地解方程。誠實的告誡很熟悉。因式分解確實比最大公因式更難，在高次、多變數的多項式上可能很慢，而答案完全取決於你問的係數定義域——在有理數、實數、複數上「不可約」會給出同一多項式的三種不同分解。而且一如電腦代數的常態，中間係數可能膨脹，這正是為什麼工作被推進有限體再提升回來。