Multiplikative Inverse in ${GF}(2^4)$

Question

Ich möchte eine erstellen $4\times4$ multiplikative inverse Tabelle in $GF(2^4)$. Das angegebene primitive Polynom ist$P(x)= x^4+x+1$

(HINWEIS: Die Werte in der Tabelle müssen im Hexadezimalformat vorliegen, daher werde ich in der Frage von nun an sowohl Polynom- als auch Hexadezimalnotationen verwenden.)

Jetzt konnte ich die multiplikative Inverse für die erste Zeile der Matrix berechnen, dh (00,01,02,03). Die Umkehrung von 03oder$(x+1)$kommt heraus, um zu sein 0Eoder$(x^3+x^2+x)$.

Wenn ich jedoch versuche, die Umkehrung von 10oder zu berechnen$x^4$kommt es wieder raus 0Eoder$(x^3+x^2+x)$. Ist es möglich, dass zwei Polynome genau die gleiche Umkehrung haben? Wenn nicht, kann ich nicht herausfinden, wo ich falsch liege. Bitte helfen Sie.

Answer 1

Das Galois-Feld $\operatorname{GF}(2^4)$ (auch vertreten $\mathbb{F_{2^4}}$) enthält $16 = 2 ^4$Elemente. Die formale Definition ist;

$\mathbb{F_{2^4}}$ ist der Quotientenring $\mathbb{F_{2}}[X]/(x^4 = x + 1)$ des Polynomrings $\mathbb{F_{2}}[X]$ durch das Ideal erzeugt durch $(x^4 = x + 1)$ ist ein Ordnungsfeld $2^4$.

Wir können die Elemente von auflisten $\operatorname{GF}(2^4)$ auf die Polynomdarstellung mit dem definierenden primitiven Polynom, nämlich $$a_3 x^3+a_2 x^2+a_1 x+a_0$$ wo $a_i \in \operatorname{GF}(2)$ zum $i=0,1,2,3$.

$\operatorname{GF}(2^4)$ ist ein Feld, daher hat jedes Element eine eindeutige multiplikative Inverse mit Ausnahme der Null.

$x^4$Wie wir sehen können, ist dies kein Element des Feldes, wir können es jedoch mit Hilfe der definierenden Polynomgleichung reduzieren $x^4 = x + 1$. Daher hat es die gleiche Darstellung mit$x+1$ auf dem Feld ist also die Umkehrung dieselbe.

Auch die Multiplikation inverse Tabelle hat $2\times 16$ Größe, so dass nur eine Zeile (oder Spalte) berechnet werden muss.

\ 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}

Die Nicht-Null-Elemente des Feldes, die normalerweise durch Hinzufügen eines Sterns oben rechts dargestellt werden $\mathbb{F}^*_{2^4} = \mathbb{F}_{2^4}- \{0\}$ bilden eine multiplikative zyklische Gruppe. $\mathbb{F}^*_{2^4}$ kann generiert werden von $x$dh $\mathbb{F}^*_{2^4} = \langle x \rangle$. Die Leistungen des Generators;

\ 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$ ist nicht enthalten, da es keine multiplikative Inverse hat.

---

Unten finden Sie den in dieser Antwort verwendeten SageMath-Code.

#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 )