附录H 伽罗华域GF(2^m)¶
若有有限个符号，其数目是一个素数的幂，并且定义有加法和乘法，则称这个有限符号的域为有限域。若有限域中的符号数目为 \(2^{m}\) , 则称此有限域为伽罗华域，记为 \(GF(2^{m})\) 。例如，若仅有两个符号 “0” 和 “1”, 以及它们如下的加法和乘法定义:
则称其为 GF (2)，又称二元域。
下面，先从二元域和一个 m 次多项式 \(p(x)\) 开始。设 \(\alpha\) 是方程式 \(p(x)=0\) 的根，即设 \(p(\alpha)=0\) 。若适当地选择 \(p(x)\) ，使得 \(\alpha\) 的各次幂，直到 \(2^{m}-2\) 次幂，都不相同，并且 \(\alpha^{2^{m}-1}=1\) 。这样， \(0,1,\alpha,\alpha^{2},\cdots,\alpha^{2^{m}-1}\) 就构成 \(\mathrm{GF}(2^{m})\) 的所有元素，域中的每个元素还可以用元素 \(1,\alpha,\alpha^{2},\cdots,\alpha^{m-1}\) 的和来表示。例如，m=4 和 \(p(x)=x^{4}+x+1\) ，则可以得到 \(\mathrm{GF}(2^{4})\) 中的所有元素，如表 H-1 所列。
| 表H-1 | GF(24)中的所有元素 |
| 0 | $\alpha^{7} = \alpha(\alpha^{3} + \alpha^{2}) = \alpha^{4} + \alpha^{3} = \alpha^{3} + \alpha + 1$ |
| 1 | $\alpha^{8} = \alpha(\alpha^{3} + \alpha + 1) = \alpha^{4} + \alpha^{2} + \alpha = \alpha^{2} + 1$ |
| $\alpha$ | $\alpha^{9} = \alpha(\alpha^{2} + 1) = \alpha^{3} + \alpha$ |
| $\alpha^{2}$ | $\alpha^{10} = \alpha(\alpha^{3} + \alpha) = \alpha^{4} + \alpha^{2} = \alpha^{2} + \alpha + 1$ |
| $\alpha^{3}$ | $\alpha^{11} = \alpha(\alpha^{2} + \alpha + 1) = \alpha^{3} + \alpha^{2} + \alpha$ |
| $\alpha^{4} = \alpha + 1$ | $\alpha^{12} = \alpha(\alpha^{3} + \alpha^{2} + \alpha) = \alpha^{4} + \alpha^{3} + \alpha^{2} = \alpha^{3} + \alpha^{2} + \alpha + 1$ |
| $\alpha^{5} = \alpha(\alpha + 1)$ | $\alpha^{13} = \alpha(\alpha^{3} + \alpha^{2} + \alpha + 1) = \alpha^{4} + \alpha^{3} + \alpha^{2} + \alpha = \alpha^{3} + \alpha^{2} + 1$ |
| $\alpha^{6} = \alpha(\alpha^{2} + \alpha) = \alpha^{3} + \alpha^{2}$ | $\alpha^{14} = \alpha^{4} + \alpha^{3} + \alpha = \alpha^{3} + 1$ |
这时， \(p(\alpha)=\alpha^{4}+\alpha+1=0\) ，或 \(\alpha^{4}=\alpha+1\) 。表中的 \(2^{4}=16\) 个元素都不相同，而且有 \(\alpha^{15}=\alpha(\alpha^{3}+1)=\alpha^{4}+\alpha=1\) 。GF (\(2^{m}\)) 中的元素 \(\alpha\) 称为本原元。一般说来，若 GF (\(2^{m}\)) 中任意一个元素的幂能够生成 GF (\(2^{m}\)) 的全部非零元素，则称它为本原元。例如， \(\alpha^{4}\) 是 GF (\(2^{4}\)) 的本原元。