9.1 有限體#

導言：所有代數碼的舞台#

第 6、7 章反覆出現 \(\mathbb{F}_2\) 、 \(\mathbb{F}_q\) 、 \(\mathbb{F}_{256}\) ——有限體。它是元素個數有限的「可加可乘可除」的代數系統。編碼理論的幾乎所有構造（線性碼、循環碼、BCH、RS、極化碼的背後、乃至密碼學 AES 的 S-box）都發生在有限體上。本節系統建立有限體理論：構造、唯一性、多項式求根、以及它為什麼恰好是編碼需要的形狀。

從 \(\mathbb{F}_p\) 到 \(\mathbb{F}_{p^m}\)#

素數體#

\(p\) 為素數時， \(\mathbb{Z}/p\mathbb{Z}\) 是體：記 \(\mathbb{F}_p\) 。加法/乘法模 \(p\) ；非零元素可逆（費馬小定理 \(a^{p-1} \equiv 1\) ）。

例題： \(\mathbb{F}_5\) 的逆元表#

（ \(2 \times 3 = 6 \equiv 1\) ， \(4 \times 4 = 16 \equiv 1\) 。）

為什麼 \(p\) 必須是素數#

\(p = 6\) ： \(2 \times 3 = 6 \equiv 0\) ——非零元素相乘得零（零因子），乘法不成群，除法崩潰。素性 = 無零因子 = 可逆性，這是 \(\mathbb{Z}/p\) 的基本事實。

擴張體： \(\mathbb{F}_{p^m}\) 的構造#

\(\mathbb{Z}/4\mathbb{Z}\) 不是體，但元素個數 4 的體存在：取 \(\mathbb{F}_2\) 上的不可約多項式 \(f(x) = x^2 + x + 1\) ，定義

（ \(\alpha\) 是 \(f\) 的根，滿足 \(\alpha^2 + \alpha + 1 = 0\) 。）乘法用 \(\alpha^3 = 1\) 循環。4 個元素的體只有這一種（在同構意義下）。

一般定理（Galois, 1830；Lidl & Niedereiter 教科書化）：

1. 有限體的元素個數必為素數冪 \(p^m\) 。
2. 對每個素數冪 \(p^m\) ，恰有一個 \(p^m\) 元體（同構唯一）。
3. \(\mathbb{F}_{p^m}^*\) 是 \(p^m - 1\) 階循環群（存在本原元 \(\alpha\) 生成所有非零元）。
4. \(\mathbb{F}_{p^m}\) 包含 \(\mathbb{F}_{p^n}\) iff \(n \mid m\) 。

性質 3 是 RS/BCH 碼「用 \(\alpha^j\) 做求值點與根」的根據（7.2 節）：循環性使根的位置可系統枚舉。

多項式在有限體中的行為#

求根與最小多項式#

\(\alpha \in \mathbb{F}_{p^m}\) 的最小多項式 \(m_\alpha(x)\) 是 \(\mathbb{F}_p\) 上以 \(\alpha\) 為根的最低次多項式（首一、不可約）。共軛性： \(\alpha, \alpha^p, \alpha^{p^2}, \dots\) 有相同最小多項式（Frobenius 自同構 \(x \mapsto x^p\) ）。這組共軛元素稱分圓陪集：

7.2 節 BCH 碼「 \(\alpha^1, \alpha^2\) 共用 \(m_1(x)\) 」的原理即此：相鄰的冪常在同陪集，故 \(g(x)\) 的次數增長比根數慢——這是 BCH 碼率高於樸素預期的秘密。

例題： \(\mathbb{F}_{16}\) 的分圓陪集（ \(p=2, m=4\) ， \(n = 15\) ）#

五個陪集覆蓋 \(0..14\) 。 \(\delta = 5\) 的 BCH 碼需根 \(\alpha^1..\alpha^4\) ——全在 \(C_1\) ！故 \(g(x) = m_1(x)\) 單獨給 \(\deg g = 4\) 、 \([15, 11, 3]\) 碼； \(\delta = 5\) （根 \(\alpha^1..\alpha^4\) 加 \(\alpha^5\) ）時 \(g = m_1 m_3\) ， \([15, 7, 5]\) （7.2 節例題）。陪集表直接決定碼參數。

編碼中的有限體實務#

\(\mathbb{F}_{256}\) ：位元組的世界#

\(256 = 2^8\) ，一個體元素 = 一個位元組。不可約多項式標準（AES 用 \(x^8 + x^4 + x^3 + x + 1\) ；RS/QR 常用 \(x^8 + x^4 + x^3 + x^2 + 1\) ）。乘法用 log/antilog 表（本原元指數表）：查表 + 模 255 加法，硬體/軟體皆極快——7.3 節 RS 解碼的 \(\mathbb{F}_{256}\) 運算全部走查表。

線性代數的平行宇宙#

\(\mathbb{F}_{p^m}\) 上的矩陣理論（高斯消去、行列式、特徵值）幾乎照搬，但有奇事：

• 特徵多項式可能無特徵向量（ \(\mathbb{F}_2\) 上 \(x^2+x+1\) 型）。
• Frobenius： \(\det(A)^p = \det(A^p)\) 型恆等式。
• 加法群是 \((\mathbb{Z}/p)^m\) ，與乘法群（循環）完全不同構。

例題： \(\mathbb{F}_{16}\) 中的 RS 碼小樣#

\(\mathbb{F}_{16}\) 、 \(n = 15\) 、RS(15, 9)： \(d = 7\) 、 \(t = 3\) 。訊息 9 個 4-bit 符號 → 多項式 → 求值於 \(\alpha^0..\alpha^{14}\) 。CD 的 CIRC 用 \(\mathbb{F}_{256}\) 的 RS(32, 28) 與 RS(28, 24)，每層 \(t = 2\) 符號、經交錯後合計抗 4000 位元刮痕（7.2 節）。

有限體為什麼「恰好」適合編碼#

三個原因：

1. 可逆除法使多項式根、Vandermonde 求逆、BM 演算法全部可用——有理域 \(\mathbb{Q}\) 也能，但元素是固定大小（ \(m\) 位元），硬體/軟體確定性運算，無捨入誤差。
2. 循環乘法群給「根的位置系統化」——BCH/RS 的構造語言。
3. 離散性使錯誤是「符號錯」而非「實數小偏差」，與通道模型（BSC/符號錯誤）精確對接。

對照：實數編碼（歐氏空間格碼，lattice codes）是另一條線（AWGN 上逼近極限，10.3 節），但儲存與數位系統的主戰場始終是有限體。

歷史前因後果#

誰、何時、為什麼#

• 1830 Galois：死前一年完成有限體理論（Galois 體）。原動力是方程式可解性，不是編碼——數學的美等了 120 年。
• 1857–1930 Dedekind、Weber、Steinitz：體論系統化。
• 1960 Reed–Solomon：直接使用 Galois 理論構造工程碼。
• 1965–1983 Lidl–Niederreiter《Finite Fields》：教科書化。
• 2001 AES（Rijndael）：S-box 即 \(\mathbb{F}_{256}\) 上的求逆 + 仿射變換——有限體成為安全性的核心（9.3 節）。

解決了什麼問題#

1. 確定性代數：無浮點誤差的「可除運算」，使編解碼可硬體化、可驗證。
2. 構造語言：本原元 + 分圓陪集 = 碼的量產系統。
3. 密碼原語：S-box、橢圓曲線（ \(\mathbb{F}_p\) / \(\mathbb{F}_{2^m}\) 上）的基礎。

引發什麼新問題#

1. 體的大小 vs 碼長：RS 碼長 \(\le q - 1\) ，大體昂貴——代數幾何碼（10.3 節）以曲線突破。
2. 運算安全：有限體運算的側信道（時間/功耗洩漏）是密碼實作的攻擊面（9.3 節）。
3. 量子：有限體上的多項式運算在量子電路的角色（Shor 演算法的數論核心在 \(\mathbb{Z}/N\) ，量子糾錯碼則建在 \(\mathbb{F}_4\) / \(\mathbb{F}_2\) 上，10.3 節）。

與其他領域的關聯#

抽象代數全譜#

群（乘法群循環、加法群初等交換）、環（ \(\mathbb{F}_q[x]\) 主理想域 → 循環碼理想，7.1 節）、體（本節）、Galois 理論（子體格 \(n \mid m\) ）。有限體是抽象代數的「最小完整劇場」。

數論#

費馬小定理、本原根、離散對數（密碼學的難題基礎，9.3 節）、分圓陪集（數論原創、編碼借用）。

計算機科學#

CRC/LFSR（ \(\mathbb{F}_2\) ）、AES S-box（ \(\mathbb{F}_{256}\) ）、Reed–Solomon（儲存與 QR）、以及理論計算機：RS 碼的求值觀點使多項式成為「可驗證編碼」原語（PCP、STARK，7.3 節）。

組合設計#

有限體構造正交拉丁方、射影幾何、實驗設計（田口方法）、以及 MDS 碼的組合特徵（6.2 節）——代數與組合在此握手。

小結與思考題#

有限體 = 唯一的 \(p^m\) 元可除代數；循環乘法群與分圓陪集是 BCH/RS 的構造引擎； \(\mathbb{F}_{256}\) 是位元組級工程的標準舞台。學好本節，第 6–7 章的所有「代數魔法」都會變成可推導的機械步驟。

思考題

1. 在 \(\mathbb{F}_7\) 中求 \(3^{-1}\) 與 \(5^{-1}\) ，並驗證。
2. 構造 \(\mathbb{F}_8\) （ \(x^3 + x + 1\) 不可約）：寫出 8 個元素、 \(\alpha\) 的冪表、以及 \(\alpha^7 = 1\) 的驗證。
3. \(\mathbb{F}_{2^6}\) （ \(n = 63\) ）的分圓陪集：列出 \(s = 1\) 與 \(s = 5\) 的陪集元素。
4. 為什麼 \(\mathbb{Z}/4\) 、 \(\mathbb{Z}/6\) 不是體？由零因子論證。
5. AES 的 S-box 為什麼需要 \(\mathbb{F}_{256}\) 的乘法逆？用「S-box 必須高度非線性且可逆」的設計需求論證。

下一節：圖論觀點——因子圖與訊息傳遞，LDPC/Turbo 的數學骨架。