乘法逆( ${GF}(2^4)$ )

Question

我想在4\times4中创建一个GF(2^4)乘法逆表。给出的本原多项式是P(x)= x^4+x+1

(注意:表中的值需要十六进制格式，因此今后我将在问题中同时使用多项式和十六进制符号)。

现在，我能够计算矩阵的第一行的乘法逆，即(0001,0102，03)。与03或(x+1)相反的是0E或(x^3+x^2+x)。

然而，当我试图计算10或x^4的逆时，它再次出现为0E或(x^3+x^2+x)。两个多项式是否有可能有完全相同的逆？如果没有，我就找不出我哪里出了问题。请帮帮忙。

Answer 1

Galois \operatorname{GF}(2^4) (也表示\mathbb{F_{2^4}})包含16 = 2 ^4元素。正式的定义是；

\mathbb{F_{2^4}}是多项式环\mathbb{F_{2}}[X]的商环\mathbb{F_{2}}[X]/(x^4 = x + 1)，由(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生成，即\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 )