【A-23-4】 用GF(p)上的n次不可约多项式构造p^n阶有限域GF(p^n)
Theorem 5 设 p是素数, 用 GF(p)[X] 表示以GF(p)中的元素为系数的多项式的集合. 设 ρ(x) ∈ GF(p)[X] 为GF(p)上的 n(>1) 次不可约多项式. 则
(i) GF(p)[X] 被划分成的 p^n 个模ρ(x)的剩余类的集合F 连同两个运算 ＋ 和 · 构成p^n阶有限域 GF(p^n),
(ii) ρ(x) 在这个有限域上有根 [x], 即 ρ([x])=[0], 此处[x]∈F, 即 [x]={g(x) | g(x) ∈ GF(p)[X], g(x) ≡ x (mod ρ(x)}.
证: (i) 已在 【A-23-1】, 【A-23-2】 和 【A-23-3】 验证.
只需证(ii). 显然 ρ(x) ≡ 0 (mod ρ(x)), 所以 [ρ(x)]=[0]. 根据 【A-22-3】定义的 以多项式为模的剩余类的运算, 所以 [ρ(x)]=ρ([x]), 所以 ρ([x])=[0].
(Theorem 5 证完)
利用Theorem 5的证明, 不失一般性, 同样可以证明:
Corollary 2 设L为 p^s阶有限域GF(p^s). 用 L[X] 表示以L中的元素为系数的多项式的集合. 设σ(x) 为 L 上的 t(>1) 次不可约多项式. 则
(i) L[X] 被划分成的(p^s)^t=p^st 个模σ(x)的剩余类的集合R 连同两个运算 ＋ 和 · 构成p^st阶有限域 GF(p^st),
(ii) σ(x) 在这个有限域上有根 [x], 即 σ([x])=[0], 此处[x]∈R, 即 [x]={g(x) | g(x) ∈ L[X], g(x) ≡ x (mod σ(x)}.
(待续)

【A-24-1】 补充有限域的性质
Lemma 23 设S 为有限域K的子集(subset). 则 S是K的子域(subfield) 当且仅当 对任意 a, b(b≠0) ∈ S, 必有 a-b ∈ S, ab^(-1) ∈ S.
证: 必要性显然.
只证充分性. 当 lemma 的条件满足时, 显然S符合【A-1】的 (2), (3), (4). 以下证明S符合【A-1】的 (1), (5), (6).
任意取定 c ∈ S, 根据lemma 的条件, c-c ∈ S, 即 0 ∈ S. 于是S含有加法单位元. 任意取定 d(d≠0)∈ S, 根据lemma 的条件, dd^(-1) ∈ S, 即 1 ∈ S. 于是S含有乘法单位元. 这就证明了S符合【A-1】的(5).
根据lemma 的条件, 0-c ∈ S, 于是 -c ∈ S. 根据lemma 的条件, 1d^(-1) ∈ S, 即 d^(-1) ∈ S. 这就证明了S符合【A-1】的(6).
已证 -d∈ S, 根据lemma 的条件, c-(-d) ∈ S. 所以 c+d=c-(-d) ∈ S. 已证 d^(-1)∈ S 根据lemma 的条件, c(d^(-1))^(-1) ∈ S. 所以 cd=c(d^(-1))^(-1) ∈ S. 这就证明了S符合【A-1】的(1).
综合上述, S符合【A-1】的(1), (2), (3), (4), (5), (6). 所以S是K的子域.
(Lemma 23 证完)
(待续)

【A-24-2】 补充有限域的性质
Lemma 24 设L为 有限域, 其特征(characteristic)为 p. 则
(i) (x+y)^p=x^p+y^p, 此处x和y代表未定元(indeterminate),
(ii) (x-y)^p=x^p-y^p.
证: (i) 运用 二项式定理（Binomial theorem）, 展开(x+y)^p. 由 Lemma 2, p作为有限域的特征(characteristic), 必为素数.
因为p是素数, 容易发现: 除了 x^py^0 和 x^0y^p 这两项以外, 在(x+y)^p 的展开式中的其余项 x^iy^j (i+j=p, i,j>0) 的系数都是p 的倍数, 因此消失(这是因为: 有限域L的特征为p). 所以 (x+y)^p=x^p+y^p.
(ii) 运用 (i), 可知 x^p=(x-y)^p+y^p. 所以 (x-y)^p=x^p-y^p.
(Lemma 24 证完)
(待续)

【A-25-1】 补充有限域上的多项式的性质
设f(x) 为有限域L上的多项式, f(x)=a_0 + a_1x + ··· + a_n^n, 此处x 为未定元(indeterminate), 每一个 a_j ∈ L.
定义 f(x) 的形式微商(Formal derivative): f'(x)= a_1 + 2a_2x + ··· + na_nx^(n-1).
Lemma 25 设f(x), g(x) 为有限域L上的多项式. 则
(i) (af(x))'=af'(x), 此处 a ∈ L 为常量
(ii) (f(x)+g(x))'=f'(x)+g'(x),
(iii) (f(x)·g(x))'=f'(x)·g(x)+f·g'(x).
证: 容易直接验证. (注:从形式上看这三个关系式在微积分学中是常见的. 但这里的多项式是有限域上的, 而且这里的形式微商的定义与微积分学无关. 所以Lemma 25必须直接验证.)
(待续)

【A-25-2】 补充有限域上的多项式的性质
Lemma 26 设f(x) 为有限域L上的多项式, a ∈ L 是方程f(x)=0 的根. 如果 a 是方程f(x)=0 的重根, 则 a 必是f'(x)=0 的根.
证: 由于 a ∈ L 是方程f(x)=0 的重根, 所以 f(x)可以表示成 f(x)=(x-a)^kg(x), 此处 k>1, g(x) 为有限域L上的多项式, g(a) ≠ 0. 运用 Lemma 25, f'(x)=k(x-a)^(k-1)g(x)+(x-a)^kg'(x).
显然 f'(a)=0, 即 a 是f'(x)=0 的根.
(Lemma 26 证完)
(待续)

【A-26-1】 p^n阶有限域GF(p^n)的存在
给定的任一素数p和任意给定的正整数n, 记 p^n=q. 考察GF(p)上的方程 x^q-x=0, 此处 0 表示 GF(p) 的加法单位元. 将 x^q-x 分解成GF(p)上的不可约因式的乘积: x^q-x=g_1(x)···g_k(x), 此处每一个 g_j是GF(p)上的不可约多项式. 如果g_1(x),...,g_k(x)中有次数>1的, 设其为g_u, deg(g_u)=v(v>1). 用 GF(p)[X] 表示以GF(p)中的元素为系数的多项式的集合. 注意到 g_u(x) ∈ GF(p)[X] 为GF(p)上的 v次不可约多项式. 依据 Theorem 5, 则 GF(p)[X] 被划分成的 p^v 个模g_u(x)的剩余类的集合 L 连同两个运算 ＋ 和 · 构成p^v阶有限域 GF(p^v), 而且g_u(x) 在有限域L上有根. 所以方程 x^q-x=0 在有限域L上增加一个根.
(待续)

【A-26-2】 p^n阶有限域GF(p^n)的存在
将 x^q-x 分解成L上的不可约因式的乘积: x^q-x=h_1(x)···h_t(x), 此处每一个 h_j是L 上的不可约多项式. 如果h_1(x),...,h_t(x)中有次数>1的, 设其为h_c, deg(h_c)=d(d>1). 用 L[X] 表示以L中的元素为系数的多项式的集合.注意到 h_c(x) ∈ L[X] 为L上的 d次不可约多项式. 依据 Corollary 2, 则 L[X] 被划分成的 p^d 个模h_c(x)的剩余类的集合 K 连同两个运算 ＋ 和 · 构成p^vd阶有限域 GF(p^vd), 而且h_c(x) 在有限域K上有根. 所以方程 x^q-x=0 在有限域K上增加一个根. 继续进行上述推导, 直到x^q-x 在某个有限域上分解q个一次因式的乘积. 记这个有限域为R. 注意到 x^q-x 的 形式微商 即 (x^q-x)'=qx^(q-1)-1. 由于 有限域R 的特征(characteristic)等于p 以及 q=p^n, 所以 qx^(q-1)消失, 所以 (x^q-x)'=qx^(q-1)-1=-1. 根据 Lemma 26, 方程x^q-x=0没有重根, 换句话说, 方程x^q-x=0的q个根彼此互异. 记这q个(彼此互异)根的集合为 S. 显然S是R的子集.
(待续)

【A-26-3】 p^n阶有限域GF(p^n)的存在
Lemma 27 有限域R的子集S为p^n阶有限域.
证: 设 a, b(b≠0) ∈ S. 则 a^q=a, b^q=b. 两式相减得到, a^q-b^q=a-b. 注意到q=p^n, 运用 Lemma 24, 可知 a^q-b^q=(a-b)^q. 综合上述, (a-b)^q=a-b, 即 (a-b)^q-(a-b)=0. 所以 a-b ∈ S.
由于 b^q=b, 所以 b^(-q)=b^(-1). 注意到, a^q=a, 所以 a^qb^(-q)=ab^(-1), 即 (ab^(-1))^q=ab^(-1). 所以 (ab^(-1))^q-ab^(-1)=0. 所以 ab^(-1) ∈ S.
根据 Lemma 23, S 是R的子域. 【A-26-2】已证 S 由q个彼此互异的根组成. 所以 S为q(q=p^n)阶有限域.
(Lemma 27 证完)
由 【A-26-1】, 【A-26-2】 的推导 及 Lemma 27, 得到 【A-21-1】所说的最终结果:
Theorem 6 对于任意给定的素数p和任意给定的正整数n, 存在 p^n阶有限域GF(p^n).
(待续)

根据 Theorem 6, 对于任意给定的素数p和任意给定的正整数n, 存在 p^n阶有限域GF(p^n).
以下是关p^n阶有限域GF(p^n)的例子.
当p=1时, p阶有限域GF(p)个的例子已在 【A-17】, 【A-18】, 【A-19】, 【A-20】 出现. 所以只需, 当p>1时, p^n阶有限域GF(p^n)的例子.
【A-27-1】 构造4阶域 GF(2^2)
用 GF(2)[X] 表示 GF(2)上的多项式的集合.
注意到 ρ(x) = 1 + x + x^2 是 GF(2)上的 2 次不可约多项式(irreducible polynomial). 根据 Theorem 5, 2^2 个模ρ(x)的剩余类的集合 F 连同两个运算 ＋ 和 · 构成一个 GF(2^2).
根据 Lemma 19, 这2^2 个模ρ(x)的剩余类的集合是 F={[a + bx]| a, b ∈ GF(2)}. 则 F={[0], [1], [x], [1+x]}
为表示简单, 记 x=A, 1+x=B. 所以, F={[0], [1], [A], [B]}
(待续)

【A-27-2】 构造4阶域 GF(2^2)
【A-27-2】 构造4阶域 GF(2^2)
以下是加法+运算表:
+ |[0][1][A][B]
---+------------
[0]|[0][1][A][B]
[1]|[1][0][B][A]
[A]|[A][B][0][1]
[B]|[B][A][1][0]
以下是乘法·运算表:
· |[0][1][A][B]
---+------------
[0]|[0][0][0][0]
[1]|[0][1][A][B]
[A]|[0][A][B][1]
[B]|[0][B][1][A]
(待续)

【A-28-1】 构造8阶域 GF(2^3)
用 GF(2)[X] 表示 GF(2)上的多项式的集合.
注意到 ρ(x) =1 + x + x^3 是 GF(2)上的 3 次不可约多项式(irreducible polynomial). 根据 Theorem 5, 2^3 个模ρ(x)的剩余类的集合 F 连同两个运算 ＋ 和 · 构成一个 GF(2^3).
根据 Lemma 19, 这2^3 个模ρ(x)的剩余类的集合是 F={[a + bx + cx^2]| a, b, c ∈ GF(2)}.
则 F={[0], [1], [x], [1+x], [x^2], [1+x^2], [x+x^2], [1+x+x^2]}
为表示简单, 记 x=A, 1+x=B, x^2=C, 1+x^2=D, x+x^2=E, 1+x+x^2=F. 所以, F={[0], [1], [A], [B], [C], [D], [E], [F]}
(待续)

【A-28-2】 构造8阶域 GF(2^3)
以下是加法+运算表:
+ |[0][1][A][B][C][D][E][F]
---+------------------------
[0]|[0][1][A][B][C][D][E][F]
[1]|[1][0][B][A][D][C][F][E]
[A]|[A][B][0][1][E][F][C][D]
[B]|[B][A][1][0][F][E][D][C]
[C]|[C][D][E][F][0][1][A][B]
[D]|[D][C][F][E][1][0][B][A]
[E]|[E][F][C][D][A][B][0][1]
[F]|[F][E][D][C][B][A][1][0]
(待续)

【A-28-3】 构造8阶域 GF(2^3)
以下是乘法·运算表:
· |[0][1][A][B][C][D][E][F]
---+------------------------
[0]|[0][0][0][0][0][0][0][0]
[1]|[0][1][A][B][C][D][E][F]
[A]|[0][A][C][E][B][1][F][D]
[B]|[0][B][E][D][F][C][1][A]
[C]|[0][C][B][F][E][A][D][1]
[D]|[0][D][1][C][A][F][B][E]
[E]|[0][E][F][1][D][B][A][C]
[F]|[0][F][D][A][1][E][C][B]
(待续)

【A-29-1】 构造9阶域 GF(3^2)
注意到 ρ(x) = 2 + x + x^2 是 GF(3)上的 2 次不可约多项式(irreducible polynomial). 根据 的 Theorem 5, 3^2 个模ρ(x)的剩余类连同两个运算 ＋ 和 · 构成一个 9阶域 GF(3^2).
根据 的 Lemma 19, 这3^2 个模ρ(x)的剩余类可表为 F={[a + bx ]| a, b ∈ GF(3)}. 则
F={[0], [1], [2], [x], [1+x], [2+x], [2x], [1+2x], [2+2x]}
为表示简单, 记 x=A, 1+x=B, 2+x=C, 2x=D, 1+2x=E, 2+2x=F. 所以, F={[0], [1], [2], [A], [B], [C], [D], [E], [F]}
(待续)

【A-29-2】 构造9阶域 GF(3^2)
以下是加法+运算表:
+ |[0][1][2][A][B][C][D][E][F]
---+---------------------------
[0]|[0][1][2][A][B][C][D][E][F]
[1]|[1][2][0][B][C][A][E][F][D]
[2]|[2][0][1][C][A][B][F][D][E]
[A]|[A][B][C][D][E][F][0][1][2]
[B]|[B][C][A][E][F][D][1][2][0]
[C]|[C][A][B][F][D][E][2][0][1]
[D]|[D][E][F][0][1][2][A][B][C]
[E]|[E][F][D][1][2][0][B][C][A]
[F]|[F][D][E][2][0][1][C][A][B]
(待续)