伽羅瓦域中的乘法/除法 (2^8)
我正在嘗試實現乘法和除法 $ GF(2^8) $ 使用對數表和指數表。我使用 3 的指數作為生成器，使用來自此處的說明。
但是，對於其中一些微不足道的乘法，我無法獲得預期的答案。
為了 $ 2 · 4 $ 這有效：
$$ \begin{align*} \log_3(2) &= 25 \ \log_3(4) &= 50 \ 25 + 50 &= 75 \ \exp_3(75) &= 8 \Rightarrow \text{ expected answer} \end{align*} $$ 然而對於 $ 7 · 11 $ 這打破了：
$$ \begin{align*} \log_3(7) &= 198 \ \log_3(11) &= 104 \ 198 + 104 &= 302. \ \text{Mod it by 255, gives us 47.}\ \exp_3(47) &= 49 \end{align*} $$ 而不是預期的 77。 據我了解，我們使用模數 255，因為 3 生成器以 255 次方“環繞”（因此模式在此之後重複），因此我們只需要 0~254。就算我錯了， $ 302 \bmod 256 $ 仍然沒有給我們 $ 70 $ ， 在哪裡 $ \exp_3(70) = 77 $ （預期的答案）
我對乘法和除法的觀察是，它可以正常工作，直到加法/減法的結果超出 0~255 的範圍。
在 GF(2 8 ) 中，7 × 11 = 49。離散對數技巧工作得很好。
您的錯誤在於假設伽羅瓦域乘法與普通整數乘法的工作方式相同。在素數域中，這實際上或多或少是這種情況，只是您需要以域的順序為模來減少結果，但在非素數域中，乘法規則是不同的。
例如，讓我們做 7 × 11。注意到 7 = 111 2和 11 = 1011 2，我們可以用二進制計算 7 × 11：
111 × 1011 = ------ 111 + 1110 + 111000 = --------到目前為止，一切都與普通整數乘法相同。但是在整數中，我們會在進行加法時傳播進位，因此最終得到
1112 + 11102 + 1110002 = 101012 + 1110002 = 10011012 = 77,
在 GF(2 n ) 中，加法是按位進行的，沒有進位（即 GF(2 n ) 加法與按位 XOR 相同），因此我們得到
1112 + 11102 + 1110002 = 10012 + 1110002 = 1100012 = 49.
（當然，如果結果超過了組階，我們還必須對歸約多項式進行模歸約，但在這種情況下，n ≥ 7 不會發生這種情況。）