環與體計算機

環與體計算機

環與體計算機可在兩類最重要的有限代數結構中執行精確算術：模環 Z_n 和伽羅瓦有限體 GF(p^k)。它處理加法、減法、乘法、除法、乘方、乘法逆元和元素階，並為每個結果提供豐富的結構分析 — 包括單位、零因子、冪零元素、冪等元素、本原根以及完整的顏色編碼 Cayley 表。

Z_n — 模環

對於正整數 n，環 Z_n = {0, 1, 2, …, n − 1} 進行模 n 的加法和乘法運算。一個元素 a 是 Z_n 的單位（即具有乘法逆元）當且僅當 gcd(a, n) = 1，因此乘法群 Z_n* 的階數為 φ(n)，即歐拉函數。

當 n 為合數時，滿足 gcd(a, n) > 1 的元素 a 是零因子：存在 b ≠ 0 使得 a · b ≡ 0 (mod n)。本計算機將自動對每個元素的結構角色進行分類。

尋找逆元 — 擴展歐幾里得算法

如果 gcd(a, n) = 1，擴展歐幾里得算法會產生整數 x, y 滿足 a · x + n · y = 1，由此得出 a⁻¹ ≡ x (mod n)。每當您請求計算逆元時，工具都會顯示生成的貝祖等式。

乘法階

對於單位 a，乘法階 ord(a) 是使得 a^k ≡ 1 (mod n) 的最小正整數 k ≥ 1。根據拉格朗日定理，ord(a) 整除 φ(n)。滿足 ord(a) = φ(n) 的元素稱為本原根，並生成整個單位群。本原根存在的充分必要條件是 n 為 1, 2, 4, p^k, 或 2p^k（其中 p 為奇質數）。

GF(p^k) — 有限（伽羅瓦）體

對於每個質數 p 和正整數 k，在同構意義下存在唯一的具有 p^k 個元素的體：伽羅瓦體 GF(p^k) = 𝔽_p^k。其元素表示為係數在 GF(p) = Z_p 中的次數 < k 的多項式，算術運算是模一個 k 次不可約多項式 f(x) 進行的。

計算機為常見的 (p, k) 組合建議標準不可約多項式，例如 GF(4) 的 x² + x + 1、GF(8) 的 x³ + x + 1、GF(16) 的 x⁴ + x + 1 以及 GF(9) 的 x² + 1。您可以自行指定；工具將透過 Rabin 風格的 gcd 測試驗證其不可約性。

為什麼 f(x) 必須是不可約的？

如果 f(x) 能分解為 g(x)·h(x) 且 deg g, deg h ≥ 1，則 g(x) 和 h(x) 在商環中的像將是非零的零因子 — 商環將僅為一個環，而非一個體。不可約性正是 GF(p)[x] / ⟨f(x)⟩ 成為體的條件。

多項式算術與逆元

加法是逐項模 p 進行。乘法是普通多項式乘法後進行約化：給定 a(x)·b(x)，除以 f(x) 並取餘數 r(x)，其中 deg r < k。乘法逆元來自多項式環 GF(p)[x] 上的擴展歐幾里得算法：尋找 u(x) 和 v(x) 滿足 u(x)·a(x) + v(x)·f(x) = 1。

環與體的一覽對比

如何使用此計算機

1. 選擇結構 — 模整數選 Z_n，擴張體選 GF(p^k)。表單會重新排列以僅顯示相關欄位。
2. 輸入參數 — 模數 n，或者質數 p 和次數 k。對於 GF(p^k)，您可以將不可約多項式留空，計算機將自動填入一個標準多項式。
3. 選擇操作 — 七個選項涵蓋了所有常見任務：加、減、乘、除、乘方、計算逆元或尋找乘法階。
4. 提供運算元 — Z_n 輸入整數，GF(p^k) 輸入如 x^2 + x + 1 的多項式。係數列表形式 (1,1,1) 亦可。
5. 點擊計算。您將看到結果以及逐步計算過程、每個元素的分類，以及當結構足夠小時顯示的 Cayley 表。

計算範例 — GF(8) = GF(2³)

取 f(x) = x³ + x + 1（在 GF(2) 上不可約）。將 a(x) = x + 1 乘以 b(x) = x²：

乘法群 GF(8)* 是 7 階循環群，元素 x 是本原元素，因為當 k = 1, 2, …, 7 時，x^k 遍歷了每一個非零元素。

為什麼這很重要

• 密碼學 — AES 使用 GF(2⁸) 中的算術，其中 f(x) = x⁸ + x⁴ + x³ + x + 1。橢圓曲線密碼學和離散對數問題存在於 GF(p) 和 GF(p^k) 中。
• 糾錯碼 — Reed-Solomon 和 BCH 碼（用於 CD、QR 碼、DVB-T、航海家號太空探測器）是基於 GF(2⁸) 或 GF(2^m) 上的多項式構建的。
• 組合設計 — 有限體用於構造哈達瑪矩陣 (Hadamard matrices)、射影平面和統計實驗中使用的拉丁方陣。
• 電腦代數 — 因式分解和模約化演算法 (Berlekamp, Cantor-Zassenhaus) 是在有限體上制定的。
• 數論教學 — Z_n、本原根和二次剩餘是通往模算術、RSA 和 Diffie-Hellman 的門戶。

常見問題解答

Z_n 何時是一個體？

模環 Z_n 當且僅當 n 為質數時是一個體。在這種情況下，每個非零元素都是單位，因為對於每個 0 < a < n，gcd(a, n) = 1。當 n 為合數時，Z_n 具有零因子，僅為一個環，而非整環。

什麼是 GF(p^k)？

GF(p^k) 也稱為階數為 p^k 的伽羅瓦體，是唯一的具有 p^k 個元素的有限體。其元素表示為 GF(p) 上次數小於 k 的多項式，算術運算是模一個 k 次不可約多項式 f(x) 進行的。對於每個質數 p 和正整數 k，在同構意義下恰好存在一個這樣的體。

什麼是不可約多項式，為什麼需要它？

GF(p) 上的不可約多項式是不能分解為係數在 GF(p) 中的較低次數多項式的多項式。模一個 k 次不可約多項式得到的商環是一個體。如果沒有不可約性，商環將包含零因子且不是體。

什麼是零因子？

環中的非零元素 a 如果存在非零元素 b 使得 a · b = 0，則 a 稱為零因子。在 Z_n 中，零因子恰好是與 n 的 gcd 大於 1 的元素 a。體沒有零因子，這就是為什麼 Z_n 恰好在 n 為質數時是一個體。

元素的乘法階是什麼？

單位 a 的乘法階是使得 a^k 在環中等於 1 的最小正整數 k。根據拉格朗日定理，此階數整除乘法群的大小：Z_n 為 φ(n)，GF(p^k) 為 p^k − 1。階數等於整個群大小的元素稱為本原根或生成元。

GF(p^k) 的本原元素有什麼作用？

本原元素是乘法群 GF(p^k)* 的生成元，該群是 p^k − 1 階的循環群。體中的每個非零元素都可以寫成本原元素的冪，這使得離散對數、BCH 碼和 Reed-Solomon 糾錯成為可能。

延伸閱讀

• 模算術 — 維基百科
• 有限體 — 維基百科
• 模 n 的本原根 — 維基百科
• 歐拉函數 — 維基百科
• 不可約多項式 — 維基百科