3-1 多項式算法

1　次数を割る因子

$\mathbb F_q$ 上のモニック既約多項式 $h$ の次数を $d$、根を $\alpha$ とする。$\mathbb F_q[\alpha]$ は $q^d$ 元の体なので、第2章の考えから $\alpha^{q^d}=\alpha$。一方、$\alpha,\alpha^q,\ldots$ の最小の反復周期を $r$ とする。軌道の積 $\prod_{j=0}^{r-1}(X-\alpha^{q^j})$ の係数はFrobeniusで固定されるので $\mathbb F_q$ に属する。これは $\alpha$ を根に持つから $d\leq r$。逆に $\alpha^{q^d}=\alpha$ より $r\mid d$。従って $r=d$。
$h\mid X^{q^n}-X$ となるのは $\alpha^{q^n}=\alpha$ のとき、つまり $d\mid n$ のときである。導関数は $-1$ なので重根がない。従って
$$X^{q^n}-X=\prod_{\substack{h\text{ モニック既約}\\\deg h\mid n}}h(X).\tag{1}$$

2　既約多項式を数える

次数 $n$ のモニック既約多項式の個数を $N_q(n)$ とする。式 (1) の両辺の次数を比べると
$$q^n=\sum_{d\mid n}dN_q(d).\tag{2}$$
例えば $q=2$ では $N_2(1)=2$ なので、$n=2$ に対して $4=2+2N_2(2)$、すなわち $N_2(2)=1$。$n=3$ では $8=2+3N_2(3)$ から $N_2(3)=2$。実際、三次の既約式は $X^3+X+1$ と $X^3+X^2+1$ の二つで、どちらも $0,1$ を根に持たない。三次式は体上で可約なら一次因子を持つので、この判定で足りる。
一般の個数は、『体とGalois理論』の有限体の章にあるMöbius反転で $N_q(n)=n^{-1}\sum_{d\mid n}\mu(d)q^{n/d}$ と求められる。同章には各次数での存在証明と既約判定条件も置いた。

3　既約判定を剰余計算に直す

次数 $n$ のモニック多項式 $f$ に対し、$n$ の相異なる素因数 $\ell$ を全て走らせる。次の二条件は $f$ の既約性と同値である。

1. $X^{q^n}-X\equiv0\pmod f$。
2. 各 $\ell$ について $\gcd(f,X^{q^{n/\ell}}-X)=1$。

証明。 $f$ が既約なら式 (1) から条件1を満たし、次数 $n$ は $n/\ell$ を割らないので条件2も満たす。逆に条件1から、$f$ の既約因子は重複せず、その次数 $d$ は全て $n$ を割る。もし $d< n$ の因子があれば、$n/d>1$ のある素因数 $\ell$ に対して $d\mid n/\ell$。式 (1) よりその因子は $X^{q^{n/\ell}}-X$ も割り、条件2に反する。よって全ての既約因子の次数は $n$。$f$ 自身の次数も $n$ なので因子は一つで、$f$ は既約。□
$q=2$、$f=X^4+X+1$ を調べる。商では $X^4=X+1$ だから、$X^8=X^2+1$、$X^{16}=X^4+1=X$。条件1が成立する。$4$ の素因数は $2$ だけで、標数2では $X^4-X=X^4+X$。従って $f=(X^4-X)+1$ より $\gcd(f,X^4-X)=1$。条件2も成立し、$f$ は既約である。

4　小さい例

$q=2,n=2$ なら $X^4-X=X(X+1)(X^2+X+1)$。右辺の次数は $1+1+2=4$。$X^2+X+1$ は $\mathbb F_2$ に根がないので既約であり、四元体を作った多項式と一致する。
演習。 $X^2+X+1$ が $X^8-X$ を割るか。
解答。 次数2は3を割らないので式 (1) により割らない。根 $\alpha$ でも $\alpha^8=\alpha^2\ne\alpha$ と確認できる。
演習。 $g=X^4+X^2+1\in\mathbb F_2[X]$ は上の判定条件のどこで失敗するか。
解答。 $g=(X^2+X+1)^2$ は重複因子を持つ。一方 $X^{16}-X$ は導関数が $-1=1$ で平方因子を持たない。従って $g$ は $X^{16}-X$ を割らず、条件1で失敗する。
演習。 $\mathbb F_q$ 上のモニック既約二次式の個数を式 (2) から求めよ。
解答。 $q^2=N_q(1)+2N_q(2)=q+2N_q(2)$ なので $N_q(2)=q(q-1)/2$。
演習。 $\mathbb F_2[X]$ で $X^{16}-X$ のモニック既約因子を全て列挙せよ。
解答。 式 (1) により次数は1、2、4だけで、個数はそれぞれ2、1、3。したがって
$$X^{16}-X=X(X+1)(X^2+X+1)(X^4+X+1)(X^4+X^3+1)(X^4+X^3+X^2+X+1).$$
四次の三式は $0,1$ を根に持たず、唯一の既約二次式 $X^2+X+1$ で割った余りも順に $1,X,X+1$ と非零なので既約である。右辺は式 (1) の次数別の全因子を含み、次数も16で一致する。
一般理論は『体とGalois理論』の有限体の章へ接続する。計算量の評価は本書では扱わない。