証明． 1について： \(f(x)=x^{q^n}-x\) について \(f'(x)=-1\) なので、 \(\gcd(f,f')=1\) である。 よって、 \(f\) は無平方である。

2について： \(\mathbb{F}_q[x]/(g)\cong\mathbb{F}_{q^d}\) である。 \(x\in\mathbb{F}_q[x]\) の、 \(\mathbb{F}_{q^d}\) における像を \(\alpha\) とおく。 \[\begin{array}{ccccc} \mathbb{F}_q[x] & \longrightarrow & \mathbb{F}_q[x]/(g) & \stackrel{\sim}{\longrightarrow} & \mathbb{F}_{q^d} \\ x & \longmapsto & \overline{x} & \longmapsto & \alpha \end{array}\] フェルマーの小定理より、 \(\alpha^{q^d}=\alpha\) である。 \(d\mid n\) より、 \[\alpha^{q^n}=\alpha^{q^{d+d+\cdots+d}}=\alpha^{q^d q^d\cdots q^d}=\Bigl(\cdots\bigl((\alpha^{q^d})^{q^d}\bigr)^{\cdots}\Bigr)^{q^d}=\alpha\] である。 よって \[\alpha^{q^n}-\alpha=0\] であり、これは \(\mathbb{F}_q[x]/(g)\) で見ると \[\overline{x}^{q^n}-\overline{x}=0\] で、これは \(\mathbb{F}_q[x]\) で見ると \[x^{q^n}-x\in(g)\] を意味する。 よって、 \(x^{q^n}-x\) は \(g\) で割り切れる。

3について： まず、 \(\mathbb{F}_{q^n}\) は多項式 \(x^{q^n}-x\) の最小分解体である。 つまり、 \(\mathbb{F}_{q^n}\) は \(\mathbb{F}_{q}\) に \(x^{q^n}-x\) の全ての根を添加したものである。 このことは、次の3つからわかる：\(\mathbb{F}_{q^n}\) の元は全て多項式 \(x^{q^n}-x\) の根であり、 \(x^{q^n}-x\) は無平方であり、 \(x^{q^n}-x\) の根の個数は最大でも \(q^n\) 個である。

次に、\(\mathbb{F}_{q^d}\) が \(\mathbb{F}_{q^n}\) の部分体であることを言う。 同型 \(\mathbb{F}_q[x]/(g)\cong\mathbb{F}_{q^d}\) を使い、 \(\mathbb{F}_{q^d}\) の元 \(\alpha\) を、次のように取る： \[\begin{array}{ccccc} \mathbb{F}_q[x] & \longrightarrow & \mathbb{F}_q[x]/(g) & \stackrel{\sim}{\longrightarrow} & \mathbb{F}_{q^d} \\ x & \longmapsto & \overline{x} & \longmapsto & \alpha \end{array}\] \(g\) は \(x^{q^n}-x\) の因数なので、 \(\alpha\) は \(x^{q^n}-x\) の根である。 従って、 \(\mathbb{F}_q(\alpha)=\mathbb{F}_{q^d}\) は \(\mathbb{F}_{q^n}\) の部分体である。

\(\mathbb{F}_{q^n}\) を \(\mathbb{F}_{q^d}\) 上の線形空間とみなした時の次元を \(m:=\dim_{\mathbb{F}_{q^d}}\mathbb{F}_{q^n}\) とすると、 元の個数について \[q^n=\bigl(q^d\bigr)^m\] が成り立つので、 \(n=md\) である。 つまり、 \(d\) は \(n\) の約数である。

証明． \(h=h_1\cdots h_l\) の状況では、中国剰余定理より、環の同型として \[ \mathbb{F}_q[x]/(h) \cong\mathbb{F}_q[x]/(h_1)\times\cdots\times\mathbb{F}_q[x]/(h_l) \cong\mathbb{F}_{q^d}\times\cdots\times\mathbb{F}_{q^d} \] が成り立つ（前半が中国剰余定理、後半は直積の各成分について有限体の性質を使った）。 この対応を \(\varphi\colon\mathbb{F}_q[x]/(h)\stackrel{\sim}{\longrightarrow}\mathbb{F}_{q^d}\times\cdots\times\mathbb{F}_{q^d}\) と書き、さらにその第 \(j\) 射影を \(\varphi_j\colon\mathbb{F}_q[x]/(h)\to\mathbb{F}_{q^d}\) と書くことにする。 （もちろん、我々は個々の \(h_j\) を知らないので、この \(\varphi\) や \(\varphi_j\) は実際の計算アルゴリズムには利用できない。しかし、アルゴリズムが成功する確率の計算には利用できる）

ここで、 \(\mathbb{F}_q[x]\) の \(dl\) 次未満の多項式を一つ選ぶことは、環 \(\mathbb{F}_q[x]/(h)\) の元を一つ選ぶことに相当する。 そこで、 \(u\in\mathbb{F}_q[x]\) を \(u\ne 0\), \(\deg u<dl\) となるように取ったとする。 \[\begin{array}{ccccc} \mathbb{F}_q[x]&\to&\mathbb{F}_q[x]/(h)&\stackrel{\sim}{\longrightarrow}&\mathbb{F}_{q^d}\times\cdots\times\mathbb{F}_{q^d} \\ u&\mapsto&\overline{u}&\mapsto&\varphi(\overline{u})=(\varphi_1(\overline{u}),\ldots,\varphi_l(\overline{u})) \end{array}\] を考える。 この第 \(j\) 成分 \(\varphi_j(\overline{u})\) を \(u_j\) とおく。

ここでもし、ある \(j\) について \(u_j=0\) となり、別の \(j'\) について \(u_{j'}\ne0\) となったならば、 \(u\) から \(h\) の自明でない因数を構成できる。 具体的には、 \(u\) は \(h_j\) で割り切れ、 \(h_{j'}\) で割り切れない。 つまり、 \(\gcd(h,u)\) は \(h_j\) を因数として含み、 \(h_{j'}\) を含まない \(h\) の因数である。

しかしそのようなラッキーはなかなか起きない。 そこで、全ての \(j\) について \(u_j\ne 0\) となった場合を考える。 これは \(\gcd(h,u)=1\) の場合に相当する。

\(u_j\in\mathbb{F}_{q^d}\) はフェルマーの小定理 \(u_j^{q^d}=u_j\) を満たす。 さらに、 \(u_j\ne 0\) であれば、 \(u_j^{q^d-1}=1\) である。 \(q\) が奇数であるという仮定より、その平方根 \(u_j^{(q^d-1)/2}\) を考えることができ、これは \(\pm1\) である： \[u_j^{(q^d-1)/2}=\pm 1\]

\(\mathbb{F}_{q^d}\) の 0 でない元であって、 \(\frac{q^d-1}{2}\) 乗が \(1\) となるようなものはちょうど半分、つまり \(\frac{q^d-1}{2}\) 個存在し、 \(\frac{q^d-1}{2}\) 乗が \(-1\) となるようなものは残りの半分、つまり \(\frac{q^d-1}{2}\) 個存在する（後述の補題）。

よって、 \(u\) をランダムに選べば、 \(u_j^{(q^d-1)/2}\) が 1 となる確率と \(-1\) となる確率はちょうど半々（\(1/2\) ずつ）である（\(u\) をランダムに選んだ時に \(u_j\) がランダムに選ばれるのというのは、中国剰余定理の帰結である）。

特に、 \(\varphi(\overline{u})^{(q^d-1)/2}=(u_1^{(q^d-1)/2},\ldots,u_l^{(q^d-1)/2})\) は \((\pm1,\ldots,\pm1)\) となり、しかも成分の符号が全て一致（\((1,\ldots,1)\) または \((-1,\ldots,-1)\) となる）する確率は \(\frac{2}{2^{l}}=2^{1-l}\) である。 \[\begin{array}{ccc} \mathbb{F}_q[x]/(h)&\stackrel{\sim}{\longrightarrow}&\mathbb{F}_{q^d}\times\cdots\times\mathbb{F}_{q^d} \\ \overline{u}^{(q^d-1)/2}&\mapsto&\varphi(\overline{u})^{(q^d-1)/2}=(\pm1,\ldots,\pm1) \\ \overline{u}^{(q^d-1)/2}-1&\mapsto&\varphi(\overline{u})^{(q^d-1)/2}-1=(0\text{ or }{-2},\ldots,0\text{ or }{-2}) \end{array}\] さらに、 \(\varphi(\overline{u})^{(q^d-1)/2}\) に 1 を足すと、そこそこの確率で「ある \(j\) について第 \(j\) 成分が 0 となり、別の \(j'\) について第 \(j'\) 成分が非 0 となる」 \((0\text{ or }2,\ldots,0\text{ or }2)\) を得る。 こうなればアルゴリズムは成功で、 \(\gcd(h,u^{(q^d-1)/2}+1)\) を計算すれば \(h\) の自明でない因数が得られる。

アルゴリズムが失敗、つまり \((0,\ldots,0)\) か \((2,\ldots,2)\) が得られた場合は、 \(\gcd(h,u^{(q^d-1)/2}+1)\) はそれぞれ \(h\) または \(1\) となる。

証明． 乗法群 \(\mathbb{F}_q^\times\) 上の群の自己準同型 \(f\), \(g\) を \[\begin{array}{cccc} &\mathbb{F}_q^\times&\to&\mathbb{F}_q^\times \\ f\colon&x&\mapsto&x^d \\ g\colon&x&\mapsto&x^{(q-1)/d} \end{array}\] と定める。

\(\operatorname{Ker}f=\{x\in\mathbb{F}_q^\times\mid x^d=1\}\), \(\operatorname{Ker}g=\{x\in\mathbb{F}_q^\times\mid x^{(q-1)/d}=1\}\) より、元の個数について \(\#(\operatorname{Ker}f)\le d\), \(\#(\operatorname{Ker}g)\le \frac{q-1}{d}\) が成り立つ。

\(f\circ g=g\circ f=1\) であるので、 \(\operatorname{Im}g\subset\operatorname{Ker}f\), \(\operatorname{Im}f\subset\operatorname{Ker}g\) である。

準同型定理より、 \(\mathbb{F}_q^\times/\operatorname{Im}g\cong \operatorname{Ker}g\) であり、 元の個数について \[q-1=\#(\mathbb{F}_q^\times)=\#(\operatorname{Im}g)\cdot \#(\operatorname{Ker}g)\le\#(\operatorname{Ker}f)\cdot\#(\operatorname{Ker}g)\le d\cdot\frac{q-1}{d}=q-1\] が成り立つ。 よって \[\#(\operatorname{Ker}f)=d, \#(\operatorname{Ker}g)=\frac{q-1}{d}\] である。

この \(\#(\operatorname{Ker}g)=\frac{q-1}{d}\) が示したいことであった。