序言

---

在本人的其它博文中，介紹了主流的三種公鑰加密算法：RSA、離散對數加密和橢圓曲線加密。出于可讀性上的考慮，文章中盡量減少了代數相關的描述。實際上，他們或多或少都跟有限域扯上了關系，如果能從抽象代數角度去解釋，會更簡潔。

抽象代數基礎

---

抽象代數，其實就是對我們日常使用的代數運算進行了抽象，將其泛化到更一般的領域。小學的時候我們學習加法和乘法，里面有說它們滿足結合律、交換律、分配律。這么多年我們一直把這些性質當成自然而然的東西，但是在抽象代數中，定義某些運算時，他們未必就像在普通加法乘法里那么顯然。

集合

這是高中數學就有的內容。集合具有三個性質：

無序性。集合中的元素是無序的。

唯一性。集合中每個元素都是唯一、不重復的。

確定性。給定一個元素和一個集合，這個元素要么屬于這個集合，要么不屬于這個集合，不存在其它情況。

比較常見的集合有：整數集（$\mathbb{Z}$）、有理數集（$\mathbb{Q}$）、實數集（$\mathbb{R}$）等。

半群

在一個集合S中定義了某種運算（記作加法“+”，但這個加法指代廣泛意義上的運算，并不是指日常使用的加法），那么在這個集合上，如果這種運算滿足以下性質，那么他和集合S共同組成一個半群，記作(S, +)：

封閉性。也就是運算的結果始終在集合S內

結合律。也就是滿足：(a + b) + c= a + (b + c)

例子：如果集合S是全體實數（記作“R”），而運算是實數加法，那么它們共同形成了一個半群，記作(R, +)

幺半群

如果一個半群(S, +)中存在一個元素e，使得S中所有的元素a都滿足：

$$a+e=e+a=a$$

那么這個半群被稱為幺半群，元素e被稱為單位元或者幺元。

例子：(R, +)中，實數0符合這一要求，所以(R, +)是幺半群，0是它的單位元。

群

如果一個幺半群(S, +)中的每一個元素a都有唯一一個元素b與之對應且滿足以下性質：

$$a+b=b+a=e，其中e是單位元$$

那么這個幺半群就是一個群。群中元素a和元素b互為逆元，記作a = -b或者b = -a。逆元存在，也就定義了群上的減法。a減去b，其實就是a加上b的逆元。也就是$$a?b=a+(?b)$$

例子：(R, +)中，每一個正數都和一個負數一一對應，他們的和為0。0取負是它自身。所以(R, +)是一個群。

交換群

如果一個群(S, +)符合交換律，即對于集合中任意元素a和b，滿足：

$$a+b=b+a$$

那么這個群被稱為交換群，又叫阿貝爾群。

例子：兩個實數相加誰先誰后對結果沒影響，滿足交換律，所以(R, +)是一個交換群。

環

在一個交換群(S, +)上， 再定義另外一種運算（記作乘法“?”，同樣地這個乘法也不是指日常使用的乘法），得到(S, +, ?)。如果(S, +, ?)滿足以下性質：

(S, ?)是一個幺半群。

兩種運算滿足分配律，即a(b + c) = ab + ac

那么那么(S, +, ?)形成一個環。此時群(S, +)的單位元被稱為環(S, +, ?)的零元。

例子：實數集R和實數乘法形成一個幺半群(R, ?)，單位元是實數1，而且和實數加法滿足分配律，所以(R, +, ?)是一個環。

除環

如果幺半群(S, ?)里除了零元以外的所有元素都有逆元，那么(S, +, ?)被稱為除環。

為了避免和(S, +)里的逆元混淆，(S, +)里的逆元稱為加法逆元，(S, ?)里的則是乘法逆元。
(S, +, ?)中乘法逆元存在，也就定義了除法，元素a除以元素b實際上就是a乘以b的乘法逆元。也就是
$$a÷b=a{b}^{?1}$$

例子：(R, ?)中，除了實數0（(R, +)的單位元）以外所有數都有倒數，一個數和他的倒數之積為1（單位元），也就是一個實數的倒數就是它的乘法逆元。所以(R, +, ?)是一個除環。但是如果把其中的實數集改為整數集，就不滿足這個性質了，因為大于1的整數倒數不在整數集中，因此沒有乘法逆元。

交換環

如果環(S, +, ?)中，(S, ?)滿足交換律，那么(S, +, ?)被稱為交換環。

例子：實數乘法滿足交換律，所以(R, +, ?)是一個交換環。

域

如果一個環(S, +, ?)，既是除環又是交換環，那么它是一個域。

例子：(R, +, ?)既是除環又是交換環，所以它是一個域，稱為實數域。

有限域

---

實數有無限多個，所以實數域是一個無限域。而如果一個域的元素是有限的，那么他就是一個有限域，又叫伽羅瓦域（就是以那個為愛死于決斗的數學家命名）。

有限域中元素的個數被稱為有限域的階(order)。有限域的階一定是某個素數p的k次冪（k是正整數）。

有限域$GF(p)$

最常見的有限域莫過于模素數p有限域$GF(p)$。

$GF(p)$是定義在整數集合$\{0,1,...,p?1\}$上的域。$GF(p)$上的加法和乘法分別是模加法和模乘法。

加法和乘法

模加法模乘法和普通的整數加法乘法類似，唯一不同的是，當運算的結果超出范圍時，要將運算結果對素數p取模。比如$GF(7)$定義在$\{0,1,2,3,4,5,6\}$上，它的加法和乘法是這樣的：
$$\begin{array}{rl}1+2=3\mathrm{m}\mathrm{o}\mathrm{d}7& =3\\ 5+6=11\mathrm{m}\mathrm{o}\mathrm{d}7& =4\\ 1?2=2\mathrm{m}\mathrm{o}\mathrm{d}7& =2\\ 4?5=20\mathrm{m}\mathrm{o}\mathrm{d}7& =6\end{array}$$

減法

a減去b，其實就是a加上b的加法逆元，關鍵是找到b的加法逆元。
$$\begin{array}{rl}1?2=1+(?2)=1+5=6\mathrm{m}\mathrm{o}\mathrm{d}7& =6又或者\\ 1?2=?1\mathrm{m}\mathrm{o}\mathrm{d}7& =6\end{array}$$

除法

到了除法，就沒那么直觀了。
a除以b，需要找到b的乘法逆元（在這里又被稱為數論倒數）。即滿足以下式子的整數x：
$$bx=1\mathrm{m}\mathrm{o}\mathrm{d}7$$
也就是解下面的方程：
$$bx=1+7k,其中k\in {\mathbb{Z}}^{+}$$
這個方程的求解需要用到擴展歐幾里得算法，在本人的另一篇博文中有詳細介紹，這里不再贅述。下面直接給出結果：
$$3÷4=3?(4^{?1})=3?2=6\mathrm{m}\mathrm{o}\mathrm{d}7=6$$

有限域$GF(2^m)$

除了$GF(p)$外，常見的有限域還有$GF(2^m)$。它在里德-所羅門編碼（二維碼使用的編碼）以及橢圓曲線加密中都有使用。

$GF(2^m)$正如他的名稱，包含$2^m$個元素。為什么是2的m次方而不是3的m次方或者5的m次方呢？

因為計算機是二進制的，$2^m$個元素恰好跟長度為m的二進制數（$0～2^m?1$）一一對應。比如$GF(2^8)$，剛好跟計算機中8個二進制位，也就是一個字節（0~255）對應。所以它在計算機或者專用硬件上可以有很高的運算效率。

為了方便，我們把$GF(2^m)$中的元素表示成長度為m的二進制形式。下面以m=3為例

加法和減法

$GF(2^m)$上的加法和減法都是異或運算。加法單位元是000。
010和110都是GF(2^3)的元素。那么
$$\begin{array}{rl}010+110=010\oplus 110& =100\\ 010?110=010\oplus 110& =100\end{array}$$
因為長度為m的二進制數異或結果還是長度為m的二進制數，所以不需要考慮結果超出范圍的情況。

乘法

乘法其實就是移位加上異或。乘法單位元是001。
舉個栗子，111乘以101，基于乘法分配律，可以得到：
$$\begin{array}{rl}111?101& =111?100+111?00+111?1\\ & =11100+0000+111\\ & =11100\oplus 111\\ & =11011\end{array}$$
如果直接相乘得到的結果長度不大于m，這就是最終結果。但是這里得到的結果是11011，長度超過了3，那么就要想辦法對它進行處理。怎么處理呢？還是對一個“素數”取模。
需要注意，這里的“素數”并不是普通的素數，而是基于上述乘法，無法由兩個數相乘得到的數。這樣的“素數”可能有多個，不同的選擇會有不同的結果。

對于$GF(2^3)$，1011就是其中一個“素數”。11011對1011取模，過程如下：
$$\begin{array}{rl}11011\mathrm{m}\mathrm{o}\mathrm{d}1011& =11011?1011?10\mathrm{m}\mathrm{o}\mathrm{d}1011\\ & =11011\oplus 10110\mathrm{m}\mathrm{o}\mathrm{d}1011\\ & =1101\mathrm{m}\mathrm{o}\mathrm{d}1011\\ & =1101?1011?1\\ & =1101\oplus 1011\\ & =110\end{array}$$

除法

除法依然是乘以一個倒數，使用的方法同$GF(p)$一樣是擴展歐幾里得算法，這里不作介紹。

參考文獻

環 (代數)
Finite field
Chapter 4. Finite Fields
GF(2^m)arithmetic: summary

總結

以上是生活随笔為你收集整理的谈谈有限域那些事儿的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。