離散數學/有限域

介紹

回憶上一節我們考慮了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(α)中常數的階數 - 我們已經在模運算中研究了這些常數。