`fff' では, 有限体上の 1 変数多項式に対し, 無平方分解, DDF, 因数分解, 多項式の既約判定などの関数が定義されている.
いずれも, 結果は [因子, 重複度] のリストとなるが, 因子は monic となり, 入力多項式の主係数は捨てられる. 無平方分解は, 多項式とその微分との GCD の計算から始まるもっとも一般的な アルゴリズムを採用している.
有限体上での因数分解は, DDF の後, 次数別因子の分解の際に, Berlekamp アルゴリズムで零空間を求め, 基底ベクトルの最小多項式を求め, その根 を Cantor-Zassenhaus アルゴリズムにより求める, という方法を実装している.
Go to the first, previous, next, last section, table of contents.