乘法逆高飛_(24)GF(24){GF}(2^4)

我想創建一個 $ 4\times4 $ 乘法逆表 $ GF(2^4) $ . 給出的原始多項式是 $ P(x)= x^4+x+1 $

（注意：表中的值需要採用十六進制格式，因此我將在以後的問題中使用多項式和十六進製表示法）。

現在，我能夠計算矩陣第一行的乘法逆，即 (00,01,02,03)。03或的倒數 $ (x+1) $ 出來是0E或 $ (x^3+x^2+x) $ .

但是，當我嘗試計算10or的倒數時 $ x^4 $ ，它又是0E或 $ (x^3+x^2+x) $ . 是否有可能兩個多項式具有完全相同的逆？如果沒有，我無法弄清楚我哪裡出錯了。請幫忙。

伽羅瓦場 $ \operatorname{GF}(2^4) $ （也代表 $ \mathbb{F_{2^4}} $ ) 包含 $ 16 = 2 ^4 $ 元素。正式的定義是；

$ \mathbb{F_{2^4}} $ 是商圈 $ \mathbb{F_{2}}[X]/(x^4 = x + 1) $ 多項式環的 $ \mathbb{F_{2}}[X] $ 由產生的理想 $ (x^4 = x + 1) $ 是有序域 $ 2^4 $ .

我們可以列出元素 $ \operatorname{GF}(2^4) $ 關於具有定義本原多項式的多項式表示，即$$ a_3 x^3+a_2 x^2+a_1 x+a_0 $$在哪裡 $ a_i \in \operatorname{GF}(2) $ 為了 $ i=0,1,2,3 $ .

$ \operatorname{GF}(2^4) $ 是一個欄位，因此每個元素都有一個唯一的乘法逆元，除了零。

$ x^4 $ ，正如我們所看到的， 不是域的元素，但是，我們可以藉助定義多項式的方程來減少它 $ x^4 = x + 1 $ . 因此它具有與 $ x+1 $ 在場，所以逆是相同的。

此外，乘法逆表有 $ 2\times 16 $ 大小，所以只有一行（或一列）要計算。

$$ \begin{array}{|c|c|}\hline p(x) \in GF(2^4) & inverse \ \hline 1 & 1 \\hline x & x^3 + 1 \\hline x + 1 & x^3 + x^2 + x \\hline x^2 & x^3 + x^2 + 1 \\hline x^2 + 1 & x^3 + x + 1 \\hline x^2 + x & x^2 + x + 1 \\hline x^2 + x + 1 & x^2 + x \\hline x^3 & x^3 + x^2 + x + 1 \\hline x^3 + 1 & x \\hline x^3 + x & x^3 + x^2 \\hline x^3 + x + 1 & x^2 + 1 \\hline x^3 + x^2 & x^3 + x \\hline x^3 + x^2 + 1 & x^2 \\hline x^3 + x^2 + x & x + 1 \\hline x^3 + x^2 + x + 1 & x^3 \\hline \end{array} $$

欄位的非零元素，通常在右上角加一個星號表示 $ \mathbb{F}^{2^4} = \mathbb{F}{2^4}- {0} $ 形成一個乘法循環群。 $ \mathbb{F}^{2^4} $ 可以由 $ x $ ， IE $ \mathbb{F}^*{2^4} = \langle x \rangle $ . 發電機的功率；

$$ \begin{array}{|c|c|}\hline i & x^i \ \hline x^ 1 & x \ \hline x^{ 2 } & x^2 \ \hline x^{ 3 } & x^3 \ \hline x^{ 4 } & x + 1 \ \hline x^{ 5 } & x^2 + x \ \hline x^{ 6 } & x^3 + x^2 \ \hline x^{ 7 } & x^3 + x + 1 \ \hline x^{ 8 } & x^2 + 1 \ \hline x^{ 9 } & x^3 + x \ \hline x^{ 10 } & x^2 + x + 1 \ \hline x^{ 11 } & x^3 + x^2 + x \ \hline x^{ 12 } & x^3 + x^2 + x + 1 \ \hline x^{ 13 } & x^3 + x^2 + 1 \ \hline x^{ 14 } & x^3 + 1 \ \hline x^{ 15 } & 1 \ \hline x^{ 16 } & x \ \hline \end{array} $$ $ p(x) = 0 $ 不包括在內，因為它沒有乘法逆元。

---

以下是此答案中使用的 SageMath 程式碼。

#Base field
R.<y> = PolynomialRing(GF(2), 'y')

#Defining polynomial
G = y^4+y+1

#The field extension
S.<x> = QuotientRing(R, R.ideal(G))
S.is_field()

for p in S:
   if ( p != 0 ):
       print( p, " - ", 1/p )

引用自：https://crypto.stackexchange.com/questions/83549