Matlab中的有限域计算

1 有限域基础知识

1.1 有限域（Galois域）的构造

令 $p$ 为一个素数. 则对任意的一个正整数 $n$，存在一个特征为 $p$，元素个数为 $p^{n}$ 的有限域 $GF(p^{n})$.

注：任意一个有限域，其元素的个数一定为 $p^{n}$，其中 $p$ 为一个素数（有限域的特征），$n$ 为一个正整数.

例1（有限域 $GF(p)$） 令 $p$ 为一个素数，集合

GF(p)=Zp={0,1,2,…,p−1}.

$$GF(p)=\mathbb{Z}_{p}=\{0,1,2,\dots,p-1\}.$$

在 $GF(p)$ 上定义加法 $\oplus$ 和乘法 $\odot$ 分别为模 $p$ 加法和模 $p$ 乘法，即任意的 $a,b\in GF(p)$，

a⊕b=(a+b)modp, a⊙b=(a⋅b)modp

$$a\oplus b=(a+b)\mod p,\ a\odot b=(a\cdot b)\mod p$$
则 为一个有 $p$ 个元素的有限域，其中零元素为 $0$，单位元为 $1$.

令 $a$ 为 $GF(p)$ 中的一个非零元素. 由于 $gcd(a,p)=1$，因此，存在整数 $b,c$，使得 $ab+pc=1$. 由此得到 $a$ 的逆元为 $a^{-1}=b\mod p$.

域 $GF(p)$ 称为一个素域(prime field).

例注1： 给定 $a$ 和 $p$，例1中的等式 $ab+pc=1$ 可以通过扩展的欧几里得除法得到，从而求得 $GF(p)$ 中任意非零元素的逆元.

例2（有限域 $GF(p^{n})$） 从 $GF(p)$ 出发，对任意正整数 $n$，$n\geq 2$，我们可以构造元素元素个数为 $p^{n}$ 的有限域 $GF(p^{n})$ 如下：
令 $g(x)$ 为一个 $GF(p)$ 上次数为 $n$ 的不可约多项式，集合

GF(pn)=GF(p)[x]/⟨g(x)⟩={a0+a1x+a2x2+⋯+an−1xn−1 | ai∈GF(p),0≤i≤n−1}

$$GF(p^{n})=GF(p)[x]/\langle g(x)\rangle=\{a_{0}+a_{1}x+a_{2}x^{2}+\cdots+a_{n-1}x^{n-1}\ |\ a_{i}\in GF(p), 0\leq i\leq n-1\}$$

在 $GF(p^{n})$ 上定义加法 $\oplus$ 和乘法 $\odot$ 分别为模 $g(x)$ 加法和模 $g(x)$ 乘法，即任意的 $a(x),b(x)\in GF(p^{n})$，

a(x)⊕b(x)=a(x)+b(x), a(x)⊙b(x)=(a(x)⋅b(x))modg(x)

$$a(x)\oplus b(x)=a(x)+b(x),\ a(x)\odot b(x)=(a(x)\cdot b(x))\mod g(x)$$
则 为一个有 $p^{n}$ 个元素，特征为 $p$ 的有限域，其中零元素为 $GF(p)$ 中的 $0$，单位元为 $GF(p)$ 中的 $1$.

令 $a(x)$ 为 $GF(p^{n})$ 中的一个非零元素. 由于 $gcd(a(x),g(x))=1$，因此，存在 $GF(p)$ 上的多项式 $b(x),c(x)$，使得 $a(x)b(x)+g(x)c(x)=1$. 由此得到 $a(x)$ 的逆元为 $a^{-1}(x)=b(x)\mod g(x)$.

域 $GF(p^{n})$ 称为 $GF(p)$ 的（$n$ 次）扩域(extension field)，而 $GF(p)$ 称为 $GF(p^{n})$ 的子域(subfield).

例注2.1： 给定 $GF(p)$ 上的多项式 $a(x)$ 和 $g(x)$，例2中的等式 $a(x)b(x)+g(x)c(x)=1$ 可以通过扩展的欧几里得除法得到，从而求得 $GF(p^{n})$ 中任意非零元素的逆元.

例注2.2：设 $GF(q)$ 是一个含有 $q$ 个元素的有限域. 对任意正整数 $n$, $GF(q)$ 上的 $n$ 次不可约多项式一定存在. 更进一步，$GF(q)$ 上首项系数为 $1$ 的 $n$ 次不可约多项式的个数为

Nq(n)=1n∑d|nμ(nd)qd=1n∑d|nμ(d)qn/d

$$N_{q}(n)=\frac{1}{n}\sum_{d|n}\mu(\frac{n}{d})q^{d}=\frac{1}{n}\sum_{d|n}\mu(d)q^{n/d}$$
其中 $\mu$ 为Moebius函数，定义为

μ(m)=⎧⎩⎨1(−1)k0如果m=1如果m=p1p2⋯pk,其中p1,p2,…,pk为互不相同的素数其它

$$\mu(m)=\begin{cases}1 & 如果 m=1\\ (-1)^{k} & 如果 m=p_{1}p_{2}\cdots p_{k},其中 p_{1},p_{2},\dots,p_{k}为互不相同的素数\\ 0 & 其它\end{cases}$$

1.2 有限域的性质

令 $GF(q)$ 是一个含有 $q$ 个元素的有限域，$F^{*}_{q}=GF(q)\setminus\{0\}$ 为有限域 $GF(q)$ 中所有非零元素构成的集合. 则在乘法之下 $F^{*}_{q}$ 是一个有限循环群. 循环群 $F^{*}_{q}$ 的一个生成元称为有限域 $GF(q)$ 的一个本原元.

若 $\alpha\in GF(q)$ 为一个本原元，则

GF(q)={
0,1,α,α2,…,αq−2}

$$GF(q)=\{0,1,\alpha,\alpha^{2},\dots,\alpha^{q-2}\}$$
并且 $\alpha^{q-1}=1$，即 $\alpha^{q}=\alpha$.

定义：设 $GF(q)$ 是一个含有 $q$ 个元素的有限域，$GF(p)$ 是 $GF(q)$ 的一个含有 $p$ 个元素的子域（$p$ 不一定为素数），$\alpha\in GF(q)$. 则 $GF(p)$ 上以 $\alpha$ 为根，首项系数为 $1$，并且次数最低的多项式称为 $\alpha$ 在 $GF(p)$ 上的极小多项式(minimal polynomial of $\alpha$ over $GF(p)$).

特别地，若 $\alpha\in GF(q)$ 为 $GF(q)$ 的一个本原元，则 $\alpha$ 在 $GF(p)$ 上的极小多项式称为 $GF(p)$ 上的一个本原多项式(primitive polynomial for $GF(q)$ over $GF(p)$).

定义注1：对任意的 $\alpha\in GF(q)$， $\alpha$ 在 $GF(p)$ 上的极小多项式存在并且唯一，并且 $\alpha$ 在 $GF(p)$ 上的极小多项式为 $GF(p)$ 上的一个不可约多项式.

定义注2：设 $\alpha\in GF(q)$， 则 $\alpha$ 和 $\alpha^{p}$ 在 $GF(p)$ 上具有相同的极小多项式. 更进一步，集合

B(α)={
α,αp,αp2,αp3,…,αpi,…}

$$B(\alpha)=\{\alpha,\alpha^{p},\alpha^{p^{2}},\alpha^{p^{3}},\dots,\alpha^{p^{i}},\dots\}$$
中的元素具有相同的极小多项式. 设 $q=p^{n}$，则 $\alpha^{p^{n}}=\alpha$. 因此，集合 $B(\alpha)$ 中互不相同的元素的个数（记为 $r$）不超过 $n$. 可以证明， $\alpha$ 为 $GF(q)$ 的一个本原元当且仅当 $r=n$.

定理：设 $GF(q)$ 是一个含有 $q$ 个元素的有限域，$GF(p)$ 是 $GF(q)$ 的一个含有 $p$ 个元素的子域. 设 $\alpha\in GF(q)$，$r$ 为满足 $\alpha^{p^{r}}=\alpha$ 的最小正整数. 则 $\alpha$ 在 $GF(p)$ 上的极小多项式 $g(x)$ 是一个 $r$ 次不可约多项式，并且

B(α)={α,αp,αp2,…,αpr−1}

$$B(\alpha)=\{\alpha,\alpha^{p},\alpha^{p^{2}},\dots,\alpha^{p^{r-1}}\}$$

中的元素为 $g(x)$ 在 $GF(q)$ 上的所有不同的根，即

g(x)=(x−α)(x−αp)(x−αp2)⋯(x−αpr−1).

$$g(x)=(x-\alpha)(x-\alpha^{p})(x-\alpha^{p^{2}})\cdots(x-\alpha^{p^{r-1}}).$$

注：$r$ 的计算方法如下：设 $\alpha$ 在 $F^{*}_{q}$ 中的阶为 $k$. 集合

Z∗k={m | 0≤m≤k−1,gcd(m,k)=1}

$$\mathbb{Z}^{*}_{k}=\{m\ |\ 0\leq m\leq k-1, gcd(m,k)=1\}$$
在模 $k$ 乘法运算下是一个含有 $\varphi(k)$ 个元素的有限群（其中 $\varphi$ 为欧拉(Euler)函数）. 则 $r$ 等于 $p\mod k$ 在 $\mathbb{Z}^{*}_{k}$ 中的阶.

推论：设 $GF(q)$ 是一个含有 $q$ 个元素的有限域，$GF(p)$ 是 $GF(q)$ 的一个含有 $p$ 个元素的子域. 设 $|GF(q)|=p^{n}$，即 $q=p^{n}$. 设 $\alpha\in GF(q)$ 为 $GF(q)$ 的一个本原元，则 $\alpha$ 在 $GF(p)$ 上的极小多项式 $g(x)$ 的次数为 $n$，并且

g(x)=(x−α)(x−αp)(x−αp2)⋯(x−αpn−1).

$$g(x)=(x-\alpha)(x-\alpha^{p})(x-\alpha^{p^{2}})\cdots(x-\alpha^{p^{n-1}}).$$
更进一步， $\alpha,\alpha^{p},\alpha^{p^{2}},\dots,\alpha^{p^{n-1}}$ 均为 $GF(q)$ 的本原元.

注：设 $GF(p)$ 是一个含有 $p$ 个元素的有限域，$n$ 是任意一个正整数，则 $GF(p)$ 上的 $n$ 次本原多项式一定存在. 更进一步，$GF(p)$ 上的首项系数为 $1$ 的 $n$ 次本原多项式的个数为 $\frac{\varphi(p^{n}-1)}{n}$，其中 $\varphi$ 为欧拉函数.

例3 考虑二元域 $GF(2)$ 上的不可约多项式 $p(\alpha)=\alpha^{3}+\alpha+1$，构造有限域

GF(23)=GF(2)[α]/⟨p(α)⟩={
0,1,α,α+1,α2,α2+1,α2+α,α2+α+1}.

$$GF(2^{3})=GF(2)[\alpha]/\langle p(\alpha)\rangle=\{0,1,\alpha,\alpha+1,\alpha^{2},\alpha^{2}+1,\alpha^{2}+\alpha,\alpha^{2}+\alpha+1\}.$$

容易验证， $\alpha,\alpha^{2},\alpha^{3},\alpha^{4},\alpha^{5},\alpha^{6}$ 都是 $GF(2^{3})$ 的本原元. $GF(2)$ 上的首项系数为 $1$ 的 $3$ 次本原多项式有两个，分别为
(i) $\alpha,\alpha^{2},\alpha^{4}$ 在 $GF(2)$ 上的极小多项式

g(x)=(x+α)(x+α2)(x+α4)=x3+x+1

$$g(x)=(x+\alpha)(x+\alpha^{2})(x+\alpha^{4})=x^{3}+x+1$$
(ii) $\alpha^{3},\alpha^{5},\alpha^{6}$ 在 $GF(2)$ 上的极小多项式

g(x)=x3+x2+1

$$g(x)=x^{3}+x^{2}+1$$

有限域 $GF(p)$ 上的本原多项式一定是 $GF(p)$ 上的不可约多项式；但是，$GF(p)$ 上的不可约多项式不一定是 $GF(p)$ 上的本原多项式.

定理：设 $GF(q)$ 是一个含有 $q$ 个元素的有限域，$GF(p)$ 是 $GF(q)$ 的一个含有 $p$ 个元素的子域， $g(x)$ 是 $GF(p)$ 上的一个不可约多项式. 则 $g(x)$ 为 $GF(p)$ 上的本原多项式当且仅当 $g(x)$ 在 $GF(q)$ 上的根都是 $GF(q)$ 的本原元.

下面例子说明不可约多项式不一定是本原多项式.

例4 考虑二元域 $GF(2)$ 上的不可约多项式 $p(x)=x^{4}+x^{3}+x^{2}+x+1$，构造有限域

GF(24)=GF(2)[x]/⟨p(x)⟩={
a+bx+cx2+dx3 | a,b,c,d∈GF(2)}.

$$GF(2^{4})=GF(2)[x]/\langle p(x)\rangle=\{a+bx+cx^{2}+dx^{3}\ |\ a,b,c,d\in GF(2)\}.$$

显然， $x\in GF(2^{4})$. 由于 $x^{5}=1$，即 $x$ 的阶为 $5$，因此， $x$ 不是 $GF(2^{4})$ 的本原元. 于是， $p(x)$ 不是 $GF(2)$ 上的本原多项式. 另外，可以验证 $x+1$ 是 $GF(2^{4})$ 的本原元.

2 Matlab 中的有限域计算函数

Matlab 中自带的有限域的计算是在 $GF(2^{m})$ 上进行的，即在二元域 $GF(2)$ 的扩域中进行计算，其中 $1\leq m\leq 16$.

由 “1.1 有限域的构造” 的 “例2” 可知，我们只需先找到一个 $GF(2)$ 上的 $m$ 次不可约多项式 $g(x)$，得到集合 $GF(2)[x]/\langle g(x)\rangle$，然后定义其上的加法和乘法分别为模 $g(x)$ 加法和模 $g(x)$ 乘法，即得到有限域 $GF(2^{m})$.

然而，这样得到的有限域 $GF(2^{m})$ 中，元素 $x$ 未必是本原元，这将给后面的（乘法）运算带来很多麻烦. 因此，在不可约多项式 $g(x)$ 的挑选上，我们最好选择一个本原多项式. 这其实就是 Matlab 中的做法.

Matlab 中 $GF(2^{m})$ 的元素： 在 Matlab 中 $GF(2^{m}):=GF(2)[D]/\langle p(D)\rangle$，其中 $p(D)$ 为一个 $GF(2)$ 上的 $m$ 次本原多项式.

GF(2m)={am−1Dm−1+am−2Dm−2+⋯+a1D+a0, | ai∈GF(2),0≤i≤m−1}

$$GF(2^{m})=\{a_{m-1}D^{m-1}+a_{m-2}D^{m-2}+\cdots+a_{1}D+a_{0},\ |\ a_{i}\in GF(2), 0\leq i\leq m-1\}$$

因此，每个 $GF(2^{m})$ 中的元素 本质上是一个次数小于 $m$ 的多项式，每个元素和多项式之间有“1-1”对应关系. 例如，取 $m=3$ 和本原多项式 $p(D)=D^{3}+D+1$，则我们得到有限域 $GF(2^{3})$，其中的元素和多项式之间的对应关系如下：

$GF(2^{3})$	$GF(2)[D]/\langle p(D)\rangle$	二进制
0	$0$	000
1	$1$	001
2	$D$	010
3	$D+1$	011
4	$D^{2}$	100
5	$D^{2}+1$	101
6	$D^{2}+D$	110
7	$D^{2}+D+1$	111

$GF(2)$ 上的多项式由系数组成的二进制所对应的（十进制）数字来表示. 例如，多项式 $p(D)=D^{3}+D+1$ 的系数组成的二进制为 $1011$，因此，多项式 $p(D)$ 表示为数字 $11$.

2.1 定义有限域数组

在 Matlab 中，函数 gf 用来定义一个有限域数组，函数申明如下：

X_GF = GF(X,M,PRIM_POLY) 

函数创建有限域 $GF(2^{M})$ 上的一个数组，使用的 $GF(2)$ 上的 M 次本原多项式为 PRIM_POLY； M 是一个 $1$ 至 $16$ 之间的整数；数组 X 中的元素为 $0$ 至 $2^{M}-1$ 之间的数.

例如，生成有限域 $GF(2^{3})$ 中的所有元素，并令本原多项式为 $p(D)=D^{3}+D^{2}+1$.

>> GF8 = gf(0:7,3,13) GF8 = GF(2^3) array. Primitive polynomial = D^3+D^2+1 (13 decimal) Array elements = 0 1 2 3 4 5 6 7 

如果不指定本原多项式，则 Matlab 将使用默认本原多项式. 例如

>> gf(0:7,3) ans = GF(2^3) array. Primitive polynomial = D^3+D+1 (11 decimal) Array elements = 0 1 2 3 4 5 6 7 

在这里例子中，Matlab 使用了 $3$ 次本原多项式 $D^{3}+D+1$.

如果不指定次数 M 和本原多项式 PRIM_POLY，则生成二元域 $GF(2)$ 中的元素.

>> gf(0:1) ans = GF(2) array. Array elements = 0 1 

生成的有限域中的数组可以参与运算（+、、.、.^、\等). 注意：参与运算的操作数必须来自同一个有限域，用于生成有限域的本原多项式也必须相同！

一个典型的例子是计算有限域的乘法表如下：

>> GF8 = gf(0:7,3) GF8 = GF(2^3) array. Primitive polynomial = D^3+D+1 (11 decimal) Array elements = 0 1 2 3 4 5 6 7 >> GF8'*GF8 ans = GF(2^3) array. Primitive polynomial = D^3+D+1 (11 decimal) Array elements = 0 0 0 0 0 0 0 0 0 1 2 3 4 5 6 7 0 2 4 6 3 1 7 5 0 3 6 5 7 4 1 2 0 4 3 7 6 2 5 1 0 5 1 4 2 7 3 6 0 6 7 1 5 3 2 4 0 7 5 2 1 6 4 3 >> GF8 = gf(0:7,3,13) GF8 = GF(2^3) array. Primitive polynomial = D^3+D^2+1 (13 decimal) Array elements = 0 1 2 3 4 5 6 7 >> GF8'*GF8 Warning: Lookup tables not defined for this order 2^3 and primitive polynomial 13. Arithmetic still works correctly but multiplication, exponentiation, and inversion of elements is faster with lookup tables. Use gftable to create and save the lookup tables. > In gf.gettables at 35 In gf.mtimes at 20 ans = GF(2^3) array. Primitive polynomial = D^3+D^2+1 (13 decimal) Array elements = 0 0 0 0 0 0 0 0 0 1 2 3 4 5 6 7 0 2 4 6 5 7 1 3 0 3 6 5 1 2 7 4 0 4 5 1 7 3 2 6 0 5 7 2 3 6 4 1 0 6 1 7 2 4 3 5 0 7 3 4 6 1 5 2 

在这里我们用两个不同的本原多项式构造有限域 $GF(2^{3})$，得到两张不同的乘法表.

注1：当我们计算 $GF(2)[D]/\langle D^{3}+D^{2}+1\rangle$ 的乘法表时，Matlab 给产生一个警告 “Warning: Lookup tables not defined for this order 2^3 and primitive polynomial 13.” 从警告中我们可以看出，Matlab 中有限域的乘法是通过查表来完成的，这样可以显著地提高计算的速度. 我们可以通过命令 gftable 来创建并保存查找表格.
注2：用本原多项式 $D^{3}+D+1$ 和 $D^{3}+D^{2}+1$ 生成两个不同的元素个数为 $8$ 的有限域，然而这两个有限域是同构的. 一般地，我们有如下有限域同构定理：

定理： 任意两个元素个数相同的有限域一定同构.

与本原元多项式相关的函数

primpoly

函数 primpoly 用于计算 $GF(2)$ 上的本原多项式，函数申明如下：

PR = PRIMPOLY(M, OPT, 'nodisplay') 

其中 M 为本原多项式的次数，其取值为 $2$ 至 $16$ 之间的整数；选项 OPT 的定义如下：

OPT = 'min' 给出一个权值最小的本原多项式 OPT = 'max' 给出一个权值最大的本原多项式 OPT = 'all' 给出所有的本原多项式 OPT = L 给出所有权值为L的本原多项式 

字符串 ‘nodisplay’ 用于关闭默认的本原多项式显示方式.

例如，输出 $GF(2)$ 上所有次数为 $3$ 的本原多项式.

>> primpoly(3,'all') Primitive polynomial(s) = D^3+D^1+1 D^3+D^2+1 ans = 11 13 >> primpoly(3,'all','nodisplay') ans = 11 13 

isprimitive

函数 isprimitive 用来检查 $GF(2)$ 上的多项式是否为本原多项式，函数申明如下：

CK = ISPRIMITIVE(A) 

其中 A 为一个表示多项式的数字，并且表示的多项式的次数不能超过 $16$. 如果 A 为本原多项式，则返回 $1$；否则返回 $0$.

例如，检查多项式 $D^{3}+D^{2}+1$ 和 $D^{3}+D^{2}+D+1$ 是否为本原多项式如下：

>> isprimitive(13) ans = 1 >> isprimitive(15) ans = 0 

其它函数

见 Matlab 帮助.