証明． 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} が示したいことであった。