离散数学/有限域

介绍

回忆上一节我们考虑了F[x]/<m(x)>的情况，类似于模运算，但使用多项式，当我们查看模n的数字时，如果n是素数，则只有当Z_n是域时，我们才有一个域。

我们能对F[x]/<m(x)>说类似的话吗？事实上，如果m(x)是不可约的，那么F[x]/<m(x)>就是一个域。

本节将讨论这类域，被称为有限域。

定义

我们有对象F[x]/<m(x)>，其中这是F[x]中被多项式m(x)除的多项式集合。

在F[x]/<m(x)>中的元素中，我们可以很容易地定义加法、减法、乘法、除法等等，就像通常一样，但使用模m(x)的约简来获得所需的余数。

我们有F[x]/<m(x)>是一个带有单位元的交换环，如果m(x)是不可约的，那么F[x]/<m(x)>就是一个域。

如果m(x)的度数为n，那么

$\mathbf {F} [x]/\langle m(x)\rangle =\{a_{n-1}x^{n-1}+a_{n-2}x^{n-2}+\dots +a_{0}x^{0}|a_{i}\in \mathbf {F} \}$

如果F是Z_p（所以p是素数），那么$|\mathbf {F} [x]/\langle m(x)\rangle |=p^{n}$

性质

现在回想一下复数C，我们"发明"了符号i来代表方程x²+1=0的根。事实上，我们有C=R[x]/<x²+1>。

当我们有一个一般的有限域时，我们也可以这样做。我们经常写成F[x]/<m(x)>=F(α)，其中α是m(x)的"根" - 我们定义α为m(x)的根。

F(α)实际上是最小的包含F和α的域。

有限域定理

我们有一些关于有限域的定理。

1. 如果F是一个有限域，|F|=q，那么q=p^k，其中k $\geq$ 1 且p是素数。
2. 然后存在一个首一不可约多项式m(x)，其度数为k，使得F=Z_p[x]/<m(x)>=Z_p(α)，其中α是m(x)在Z_p上的根
3. 存在一个元素γ∈F，使得γ的阶数（使得γⁿ=1的最小元素n）为q-1，所以γ在F中是本原的，我们可以从γ的幂生成F（非零）的元素，即F={0, γ⁰=1, γ¹, ..., γ^q-2, γ^q-1=1}
4. F是一个向量空间，在Z_p上的维度为k。它有基{1, α, α²,...,α^n-1}，其中n是m(x)的度数，所以我们有F={a_n-1α^n-1+...+a₀α⁰|a_i∈F}
5. 如果a∈F，a+...+a p次（pa）为0。
6. 如果m₂(x)是任何其他在Z_p上的度数为k的不可约多项式，那么F是同构的（基本等于，只是符号改变）到Z_p/<m₂(x)> - 所以写这个域的所有方法基本上都是一样的。所以本质上只有一个大小为q=p^k的域，我们将其表示为GF(p^k)（GF表示伽罗瓦域）。

一些例子

让我们看几个贯穿这些概念的例子。

复数

复数，简而言之，是形如

$a+bi$

的数字，其中i是方程x²+1=0的解

这些数字实际上形成了一个域，但是它不是一个有限域。

取m(x)=x²+1，域F为R。然后我们可以形成复数为F/<m(x)>。现在F/<m(x)> = { a+bx | a, b ∈ R}，因为余数的度数必须小于m(x) - 也就是2。

那么(a+bx)(c+dx)=ac+bdx²+(ad+bc)x。

但请记住，我们是在F/<m(x)>中工作的。所以模x²+1的x²可以写成(x²+1)-1=-1，将-1代入上式得到一个相当熟悉的表达式。

如果我们令符号i为"x²+1的根"，那么i²+1=0且i²=-1。其余域公理由此得出。然后我们可以说复数C=R/<x²+1>=R(i)。

Z_p情况

一般情况下，我们仍然可以对某些字段执行此操作。以Z₃为例，选择m(x)=x²+x+2。m(x)是不可约的 - m(0)=2，m(1)=4=1，m(2)=4+2+2=8=2。

所以Z₃/<x²+x+2>是一个有限域。假设α是m(x)的根。然后Z₃(α) = { a+bα|a, b ∈ Z₃}。由于Z₃/<x²+x+2>是有限的，我们可以列出它的所有元素。我们有常数项，然后是α项，然后是α+常数项，等等。我们有 {0, 1, 2, α, α+1, α+2, 2α, 2α+1, 2α+2}。

现在我们有α²+α+2=0，那么

α²=-α-2

α²=2α-2=2α+1

(请记住系数在Z₃中！我们正在Z₃/<m(x)>中工作)

我们可以验证乘法在mod m(x)下有效 - 例如

(1+2α)(2+α) = 2 + α+4α+2α²

通常将系数简化为mod 3，我们得到

(1+2α)(2+α) = 2 + 2α + 2α²

现在使用上面α²的公式

(1+2α)(2+α)

= 2 + 2α + 2(2α+1)

= 2 + 2α+4α+2

= 2 + 6α+2

= 2 + 2 = 4 = 1

自己验证乘法和其他操作是否也起作用。

本原元素

回顾模运算，在一个域中，数字a模n的阶数是指a^k-1=1在Z_n中的最小幂，其中k是该域的大小。由于阶数是在域上定义的，因此我们考虑F[x]/<m(x)>中是否存在本原元素 - 确实存在。如果我们有F(α)，就像在Z_n中一样，α是本原的当且仅当α的阶数为q-1，其中q是F[x]/<m(x)>中的元素数量。

以Z₂/<x²+x+1>为例。α（x²+x+1的根）是本原的吗？

首先，如果α是x²+x+1的根，

α²+α+1=0

α²=-α-1=α+1

现在，让我们计算α的幂

1, α

α²=α+1

α³=α(α²)=α(α+1)=α²+α=(α+1)+α=1

回想一下，该域的大小为4（Z_n中的n，在本例中为2，提高到多项式次数的幂，在本例中为2）。现在我们有α³=α^4-1=1，并且α是本原的。

我们通常希望查看F(α)中α的幂，以查看它们是否为本原的，因为我们已经了解了F(α)中常数的阶数 - 我们已经在模运算中研究了这些常数。