[latexpage]
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$
- 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:
[embedyt] https://www.youtube.com/watch?v=yufl3XIxlgw[/embedyt]