Pembahasan Soal 5 Lapangan Galois

Soal Let GF_{2^4}, proof that f(x) = x^4 + x + 1 is the minimum function.

Pembahasan

Lapangan GF_{2^4} adalah lapangan hingga yang memiliki 2^4 = 16 elemen. Lapangan ini merupakan ekstensi dari lapangan dasar GF(2), yang terdiri dari dua elemen: \{0, 1\}.

Untuk membangun GF(2^4), kita memerlukan sebuah polinomial tak tereduksi (irreducible polynomial) derajat 4 atas GF(2). Jika f(x) adalah polinomial seperti itu, maka:

    \[GF(2^4) \cong GF(2)[x]/(f(x))\]

dengan f(x) = x^4 + x + 1

  1. Akan ditunjukkan bahwa f(x) tak tereduksi. Ambil sebarang \{0, 1\} \in GF(2)

f(0) = 0^4 + 0 + 1 = 1 \quad \Rightarrow \text{bukan akar}

f(1) = 1^4 + 1 + 1 = 1 + 1 + 1 = 1 \quad \Rightarrow \text{bukan akar}

Karena f(x) tidak memiliki akar di GF(2), maka tidak dapat difaktorkan menjadi faktor linear.

Misal f(x) = (x^2 + ax + b)(x^2 + cx + d) dengan a, b, c, d \in GF(2).

    \begin{align*} f(x) &= (x^2 + ax + b)(x^2 + cx + d)\\ &= x^4+cx^3+dx^2+ax^3+acx^2+adx+bx^2+bcx+bd\\ &=x^4+(c+a)x^3+(ac+d+b)x^2+(bc+ad)x+bd \end{align*}

Diperoleh

    \begin{align*} c+a&=0\\ ac+d+b&=0\\ bc+ad&=1\\ bd&=1 \end{align*}

Akibatnya, b=d=1, ac=0, dan a=c. Jadi, a=c=0. Namun bc+ad=0\ne1, sehingga terjadi kontradiksi. Dengan demikian, f(x) polinomial irreducible.

2. Akan ditunjukkan f(x) adalah fungsi minimal.

Diperhatikan bahwa untuk lapangan Galois GF_{2^4} dengan polinomial modulus f(x) = x^4 + x + 1, berlaku:

    \begin{align*} [x]^0 &= 1\\ [x]^1 &= [x]\\ [x]^2 &= [x^2]\\ [x]^3 &= [x^3]\\ [x]^4 &= [x + 1]\\ [x]^5 &= [x^2 + x]\\ [x]^6 &= [x^3 + x^2]\\ [x]^7 &= [x^4 + x^3] = [x^3 + x + 1]\\ [x]^8 &= [x^4 + x^2 + x] = [x^2 + 1]\\ [x]^9 &= [x^3 + x]\\ [x]^{10} &= [x^4 + x^2] = [x^2 + x + 1]\\ [x]^{11} &= [x^3 + x^2 + x]\\ [x]^{12} &= [x^4 + x^3 + x^2] = [x^3 + x^2 + x + 1]\\ [x]^{13} &= [x^4 + x^3 + x^2 + x] = [x^3 + x^2 + 1]\\ [x]^{14} &= [x^4 + x^3 + x] = [x^3 + 1] \end{align*}

Karena x merupakan akar f(x) yang memenuhi [x]^0 sampai [x]^{14} semua berbeda, berarti f(x) fungsi minimum.

 

Video Penjelasan:

Leave A Comment

Alamat email Anda tidak akan dipublikasikan.

*