密碼學中的伽羅瓦域
我不太了解伽羅瓦域，但我注意到它們在加密中被大量使用。我試圖讀懂它們，但很快就迷失在一堆亂七八糟的象形文字和外來術語中。我知道它們是表格的集合 $ GF(p^n) $ 為了 $ n\geq1 $ 在哪裡 $ p $ 是素數並且 $ n $ 是一個整數。據我所知，它們的定義如下：
$ GF(p^n) = [f(0) \bmod p, f(1) \bmod p, \dotsc, f(p^n-1) \bmod p, f(p^n) \bmod p] $
為了 $ f(x) = \sum_{i=0}^{n} \space x^ik_i $ ，即一個 $ n $ 具有常數的階多項式 $ K $ .
我已經看到提到這些欄位是雙射的，因此對於輸入集 $ A $ 有一個輸出集 $ B $ 包含相同的值 $ A $ ，但順序不同。
它是否正確？這是否有用於創建 s-box 的應用程序？
更新：
感謝到目前為止的答案。我現在明白了 $ GF(p^n) $ 是一個大小數組- $ n $ 向量，其每個元素都是作為某些多項式 mod 的結果計算的 $ p $ ，但我仍然不清楚它的其餘部分。我主要了解如何在這樣的欄位上進行矢量操作，但我仍然不知道如何使用這樣的有限欄位，更不用說在程式碼中實現它們了。我真的不明白什麼 $ GF(p^n) $ 看起來像在建築方面，我想這就是我真正想要的。如果它是一個向量數組，其中的每個元素都由某個多項式計算，那麼該多項式的輸入是如何決定的？是 $ GF $ 一個函式，你提供這樣一個值？輸入值是整數、向量等嗎？如果是這樣，輸入值的含義是什麼？集合中向量的索引如何影響其值的計算？
例如：
$ GF(p^n)[i] = \begin{bmatrix} v_0\v_1\v_2\…\v_{n-1} \end{bmatrix} $
在哪裡 $ i $ 是該欄位的一些索引，向量元素如何 $ V $ 計算？提供了哪些輸入？
這 $ GF $ 在 $ GF(p^n) $ 不是一個函式——它只是代表“伽羅瓦域（的 $ p^n $ 元素）”。
至於伽羅瓦域 是什麼，它是一組有限的事物（我們可以用數字來表示） $ 0 $ 到 $ p^n-1 $ )，在它們上定義了一些數學運算（特別是加法和乘法，以及它們的逆運算），讓我們可以用這些東西來計算它們，就好像它們是普通數一樣，但是計算結果總是保持在有限集中。
具體來說，我們需要在這個有限集的元素上定義的操作滿足域公理，其中包括您可能在高中代數課上學到的通常的結合性、交換性和分配性規則。特別是，我們還要求每個元素 $ a $ 有一個加法逆 $ -a $ 而如果 $ a \ne 0 $ ) 乘法逆 $ 1/a $ , 這樣 $ a + (-a) = 0 $ 和 $ a \times (1/a) = 1 $ . 因此，只要您堅持使用這些規則進行代數運算，伽羅瓦域看起來都與您熟悉的實數域完全一樣。
要學習如何在伽羅瓦域中進行算術運算（即用實際數字進行實際計算） ，從主要的伽羅瓦域開始可能是最簡單的（特別是如果您已經熟悉模算術） $ GF(p) $ . 這些領域中的算術只是對一些素數模數的整數的普通加法和乘法 $ p $ . 例如，在 $ GF(3) $ , 有三個數 ( $ 0 $ , $ 1 $ 和 $ 2 $ ) 具有以下加法和乘法規則（及其交換變體）：
$$ \begin{aligned} 0 + 0 &= 0 & 1 + 1 &= 2 & 0 \times 0 &= 0 & 1 \times 1 &= 1 \ 0 + 1 &= 1 & 1 + 2 &= 0 & 0 \times 1 &= 0 & 1 \times 2 &= 2 \ 0 + 2 &= 2 & 2 + 2 &= 1 & 0 \times 2 &= 0 & 2 \times 2 &= 1 \ \end{aligned} $$ 這裡唯一不尋常的規則是 $ 1 + 2 = 0 $ , $ 2 + 2 = 1 $ 和 $ 2 \times 2 = 1 $ ; 在這些情況下，在正常算術中，結果將等於或大於 $ 3 $ ，所以它通過減去“環繞” $ 3 $ . 從這些規則中，我們也可以確定逆。事實證明 $ -0 = 0 $ , $ -1 = 2 $ 和 $ -2 = 1 $ （自從 $ 1 + 2 = 0 $ ） 和 $ 1/1 = 1 $ 和 $ 1/2 = 2 $ （自從 $ 2 \times 2 = 1 $ )，因此它們確實存在並且屬於該領域。（作為練習，我將驗證逆元是否都是唯一的，並且這些規則確實也滿足所有其他域公理。）
為什麼我們需要 $ p $ 成為素數，然後呢？好吧，事實證明，如果一個數字 $ m $ 不是素數，那麼一些數字不會有乘法逆模 $ m $ ：例如，沒有整數 $ a $ 這樣 $ 2 \times a = 1 \pmod 4 $ . 因此，整數模 $ m $ 實際上不形成一個欄位（但只有一個ring），除非 $ m $ 是素數。
然而，如果 $ m $ 是素冪——即形式的數 $ m = p^n $ , 對於一些素數 $ p $ 和一些正整數 $ n $ ——然後我們仍然可以通過改變加法和乘法工作的規則來保存東西。這就是有關向量和多項式的所有內容的來源。但是，您應該記住的是，它們並不真正代表任何增加的複雜性，只是看待事物的替代方式。從根本上說，我們仍在處理一組 $ p^n $ 數字和對它們定義的一些算術運算——例如，如果我們用多項式辨識欄位中的每個數字，至少如果你還記得的話，我們需要使用的乘法規則很容易描述您可能在高中時也學過的多項式加法和乘法（和除法）的規則。
所以，讓我們從向量和加法開始。給定一個數字 $ a \in {0, \dotsc, p^n-1} $ ，我們可以用自然的方式表示它 $ n $ 根據- $ p $ 數字 $ a_0, \dotsc, a_{n-1} $ , 這樣
$$ a = a_0 + a_1 p + a_2 p^2 + \dotsb + a_{n-1} p^{n-1}. $$ 這正是您表示二進制數模的方式 $ 2^n $ 作為一串 $ n $ 位。我們也可以將字元串稱為向量，因為這基本上就是向量：一個有限長度的數字序列。
現在，當您通常將數字逐位相加時，您需要跟踪進位。另一方面，當您將兩個向量相加時，它更簡單：您只需分別將每個向量中的相應數字相加即可。現在，事實證明我們需要使用加法規則，以使域公理在具有 $ p^n $ 元素，正是這種“無進取加法”。例如，在 $ GF(4) $ （我們經常寫成 $ GF(2^2) $ 強調 $ 4 = 2^2 $ 確實是主要力量）加法規則如下所示：
$$ \begin{aligned} 0 + 0 &= 0 & 0 + 2 &= 2 & 1 + 1 &= 0 & 1 + 3 &= 2 & 2 + 3 &= 1 \ 0 + 1 &= 1 & 0 + 3 &= 3 & 1 + 2 &= 3 & 2 + 2 &= 0 & 3 + 3 &= 0 \ \end{aligned} $$ 如果你把它們寫成二進制，它們看起來更合乎邏輯：
$$ \begin{aligned} 00 + 00 &= 00 & 00 + 10 &= 10 & 01 + 01 &= 00 & 01 + 11 &= 10 & 10 + 11 &= 01 \ 00 + 01 &= 01 & 00 + 11 &= 11 & 01 + 10 &= 11 & 10 + 10 &= 00 & 11 + 11 &= 00 \ \end{aligned} $$ 在這裡你可以看到我們只是把數字加起來模 $ 2 $ 並忽略任何進位。您可能還會將此“加法”規則辨識為與按位XOR相同的操作。這不是獨有的 $ GF(4) $ ; 的元素 $ GF(2^n) $ 對於任何 $ n $ 可以表示為 $ n $ -bit 位串，以及它們作為按位異或的加法。
所以，現在我們知道如何在 $ GF(p^n) $ . 那麼乘法呢？好吧，這就是多項式的用武之地。你看，描述乘法規則的一種方法是想像數字 $ a_0, \dotsc, a_{n-1} $ 數量的 $ a $ 是多項式的係數
$$ a[x] = a_0 + a_1 x + a_2 x^2 + \dotsb + a_{n-1} x^{n-1} $$與未知 $ x $ . （這裡，變數 $ x $ 純粹是一個正式的佔位符；我們永遠不會給它賦值，所以你永遠不必擔心“什麼是 $ x $ ?”。它就在那裡，以便我們可以使用高中代數規則來處理多項式 $ x $ .) 然後，將兩個數字相乘 $ a $ 和 $ b $ , 我們只取它們各自的多項式 $ a[x] $ 和 $ b[x] $ ，使用高中代數規則將它們相乘（做所有內部算術模 $ p $ )，並取結果的係數。這一切都很簡單：記住多項式乘法也很簡單，就像普通的逐位乘法一樣，只是再次沒有進位。
可是等等！乘法有時不會給我訂單條件嗎 $ x^n $ 或更高？如果我將它們包含在數字字元串中，那不會導致數字大於 $ p^n-1 $ ?
嗯，是。這就是為什麼還有一個步驟：在乘法之後，我們需要以一個合適的多項式為模減少結果（具體來說，一個不可約的 一元多項式） $ n $ ）。也就是說，我們將乘法的結果除以這個減少多項式（我們可以再次使用高中多項式長除法），再次記住對係數進行模數運算 $ p $ ，並保留剩餘部分（這將是有序的 $ x^{n-1} $ 或更少）。當然，在實踐中，在乘法過程中進行歸約通常更有效*，*這樣您就不需要儲存冗長的中間結果。
好的，那麼減少多項式從何而來？好吧，事實證明我們在選擇它時有一定的自由度，因為通常有幾個多項式可以工作。它們中的每一個都會給出不同的乘法規則，儘管所有域都是這樣構造的（更一般地說，所有有限域都有 $ p^n $ 元素）是同構的，在這個意義上，對於任何兩個伽羅瓦域 $ A $ 和 $ B $ 的 $ p^n $ 元素，有一個可逆的函式 $ f: A \to B $ 將一個欄位映射到另一個欄位，以便 $ f(a + b) = f(a) + f(b) $ 和 $ f(a \times_A b) = f(a) \times_B f(b) $ ， 在哪裡 $ \times_A $ 和 $ \times_B $ 表示兩個欄位的乘法運算符。因此，當我們只關心域的一般代數性質而不關心數字的具體表示時，通常會說“伽羅瓦”序域 $ p^n $ ，即使它可能有多種表示形式。
如果你被要求在一個特定的伽羅瓦域中計算某些東西，通常會為你提供約簡多項式。例如，如果您正在編寫 AES 實現，它使用 $ GF(2^8) $ 用約簡多項式 $ x^8 + x^4 + x^3 + x + 1 $ （哪裡，因為 $ p=2 $ , 所有係數要麼 $ 0 $ 或者 $ 1 $ ).
如果您要選擇自己的表示，從而選擇您自己的約簡多項式，您通常應該嘗試選擇一些使計算容易的東西，但要遵守上述不可約約束。這通常意味著選擇盡可能少的非零係數，並且所有這些係數都出現在低階項上（除了 $ x^n $ 項，其係數必須為 $ 1 $ 多項式是單數且有序的 $ n $ ， 當然）。
我可以更詳細地介紹如何在二進制伽羅瓦域中實現乘法 $ GF(2^n) $ ，因為我上面寫的內容仍然處於相當抽象的水平，而且因為——尤其是對於有程式背景的人來說——理論通常比實際程式碼更複雜（或者至少看起來是這樣）。但是，老實說，我自己更熟悉事物的理論方面，無論如何，這個答案已經足夠長了。不過，維基百科確實有一篇關於有限域算術的不錯的文章，你可以從它開始。
哦，那不有序的伽羅瓦域呢 $ p^n $ 對於一些素數 $ p $ 和正整數 $ n $ ? 好吧，事實證明不存在——如果元素的數量有兩個不同的質因數，你就不能滿足域公理。所以，唉，沒有這樣的事情 $ GF(6) $ 或者 $ GF(10) $ .