これは有限体上で実装された多項式の因数分解の記事です。
まず有名なのはバーレカンプの因数分解法です。
これははっきり行って非効率。
多項式時間でできるとは言っても余りにも遅すぎる。
そこで、GCDを使った多項式の因数分解を提案した。
実はこれ海外では常識になっているとGPTから教わったんですが、私はその発明者と同じように見つけたことになります。
検索で調べても全く出てこない方法です。
GCD、 多項式、因数分解
で検索すれば出てきますが、GCDを使うと知らなければそもそも検索しようがない。
なので、1次資料として英語の分厚いアルゴリズム時点でも持ってないとわからない。
自分はBen-Orの規約性判定テストを実装しているときに気が付きました。
さて、どんな方法かというと、まずある次数までのすべての多項式の積は
$$x^p-x$$
と書けることです。
これを、因数分解したい多項式とのGCDを計算すれば一発です。
後は因数がなくなるまで商を取って繰り返せば因数分解の出来上がりです。
ただしべき乗因子がある場合、これは別の方法で因数分解しなければならない。
無平方分解へと行き着くわけです。
最初に米上因子を取り除くこともできます。
$$GCD(f,f')$$
を計算すればいいのです。$f'$は$f$の形式的微分。
これで次数の高い多項式でも定義帯が大きな場合でも高速に因数分解できます。
みんなで因数分解しよう！