10.2 有限体上での 1 変数多項式の演算

‘fff’ では, 有限体上の 1 変数多項式に対し, 無平方分解, DDF, 因数分解, 多項式の既約判定などの関数が定義されている.

いずれも, 結果は [因子, 重複度] のリストとなるが, 因子は monic となり, 入力多項式の主係数は捨てられる.

無平方分解は, 多項式とその微分との GCD の計算から始まるもっとも一般的な アルゴリズムを採用している.

有限体上での因数分解は, DDF の後, 次数別因子の分解の際に, Berlekamp アルゴリズムで零空間を求め, 基底ベクトルの最小多項式を求め, その根 を Cantor-Zassenhaus アルゴリズムにより求める, という方法を実装している.

この文書は12月 21, 2024にtexi2html 5.0を用いて生成されました。