Çarpımsal ters ${GF}(2^4)$

Question

Ben yaratmak istiyorum $4\times4$ çarpımsal ters tablo $GF(2^4)$. Verilen ilkel polinom$P(x)= x^4+x+1$

(NOT: tablodaki değerlerin onaltılık formatta olması gerekir, bu nedenle bundan sonra soruda hem polinom hem de onaltılık gösterimler kullanacağım).

Şimdi, matrisin ilk satırı için çarpımsal tersini hesaplayabildim, yani (00,01,02,03). 03Veya tersi$(x+1)$çıkar olmaya 0Eveya$(x^3+x^2+x)$.

Ancak, 10veya tersini hesaplamaya çalıştığımda$x^4$, tekrar ortaya çıkıyor 0Eveya$(x^3+x^2+x)$. İki polinomun tam olarak aynı tersi olması mümkün mü? Değilse, nerede yanlış yaptığımı anlayamıyorum. Lütfen yardım et.

Answer 1

Galois Sahası $\operatorname{GF}(2^4)$ (ayrıca temsil edildi $\mathbb{F_{2^4}}$) içerir $16 = 2 ^4$elementler. Resmi tanım;

$\mathbb{F_{2^4}}$ bölüm halkasıdır $\mathbb{F_{2}}[X]/(x^4 = x + 1)$ polinom halkasının $\mathbb{F_{2}}[X]$ tarafından oluşturulan ideal tarafından $(x^4 = x + 1)$ bir düzen alanıdır $2^4$.

Unsurlarını listeleyebiliriz $\operatorname{GF}(2^4)$ tanımlayıcı ilkel polinom ile polinom gösterimi üzerinde, yani $$a_3 x^3+a_2 x^2+a_1 x+a_0$$ nerede $a_i \in \operatorname{GF}(2)$ için $i=0,1,2,3$.

$\operatorname{GF}(2^4)$ bir Alandır, bu nedenle sıfır dışında her elemanın benzersiz bir çarpımsal tersi vardır.

$x^4$Gördüğümüz gibi, alanın bir unsuru değildir, ancak onu tanımlayan polinom denkleminin yardımıyla azaltabiliriz $x^4 = x + 1$. Bu nedenle aynı temsiliyete sahiptir$x+1$ alanda, yani tersi aynıdır.

Ayrıca, çarpım ters tablosunda $2\times 16$ boyut, dolayısıyla hesaplanacak yalnızca bir satır (veya sütun) vardır.

\ başlar {dizi} {| 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 {dizi}

Alanın sıfır olmayan öğeleri, genellikle sağ üst köşeye bir yıldız eklenerek gösterilir $\mathbb{F}^*_{2^4} = \mathbb{F}_{2^4}- \{0\}$ çarpımsal bir döngüsel grup oluşturur. $\mathbb{F}^*_{2^4}$ tarafından oluşturulabilir $x$yani $\mathbb{F}^*_{2^4} = \langle x \rangle$. Jeneratörün güçleri;

\ başlangıç ​​{dizi} {| 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 {dizi} $p(x) = 0$ çarpımsal tersi olmadığı için dahil edilmez.

---

Bu cevapta kullanılan SageMath kodu aşağıdadır.

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