Pembahasan Soal 2 Lapangan Galois

Soal Diberikan dua polinomial $p(x)$ dan $q(x)$ di $GF_2[x]$ yang memenuhi deg $(p(x)) < 3$ , deg $(q(x)) < 2$ , dan

$\begin{align*} p(x)(1 + x + x^3) + q(x)(1 + x + x^2 + x^4) = 1. \end{align*}$

Selidiki apakah $p(x)^2 + q(x)$ irredusibel di $GF_2[x]$ .

Pembahasan

Diberikan dua polinomial $p(x)$ dan $q(x)$ di $GF_2[x]$ yang memenuhi deg $(p(x)) < 3$ , deg $(q(x)) < 2$ , dan

$\begin{align*} p(x)(1 + x + x^3) + q(x)(1 + x + x^2 + x^4) = 1. \end{align*}$

Misalkan $p(x) = ax^2 + bx + c$ dan $q(x) = mx + n$ ; $a, b, c, m, n \in GF_2$ .

Substitusikan $p(x) = ax^2 + bx + c$ dan $q(x) = mx + n$ ke persamaan $p(x)(1 + x + x^3) + q(x)(1 + x + x^2 + x^4) = 1$ , diperoleh

$\begin{align*} (ax^2 + bx + c)&(1 + x + x^3) + (mx + n)(1 + x + x^2 + x^4) = 1\\ &\iff ax^2 + bx + c + ax^3 + bx^2 + cx + ax^5 + bx^4 + cx^3 + mx + n + mx^2 + nx + mx^3 + nx^2 + mx^5 + nx^4 = 1\\ &\iff (a + m)x^5 + (b + n)x^4 + (a + c + m)x^3 + (a + b + m + n)x^2 + (b + c + m + n)x + (c + n) = 1. \end{align*}$

Didapatkan sistem persamaan linear di $GF_2$ sebagai berikut.
$a + m = 0, \quad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \ldots (1)$
$b + n = 0, \; \quad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \ldots (2)$
$a + c + m = 0, \; \quad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \ldots (3)$
$a + b + m + n = 0, \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \ldots (4)$
$b + c + m + n = 0, \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \ldots (5)$
$c + n = 1. \; \quad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \ldots (6)$
Dari $(3) + (1)$ , diperoleh $c = 0. \qquad \qquad \qquad \qquad \qquad \qquad \qquad \ldots (7)$
Dari $(6) + (7)$ , diperoleh $n = 1. \qquad \qquad \qquad \qquad \qquad \qquad \qquad \ldots (8)$
Dari $(2) + (8)$ , diperoleh $b = 1. \qquad \qquad \qquad \qquad \qquad \qquad \qquad \ldots (9)$
Dari $(5) + (7) + (8) + (9)$ , diperoleh $m = 0. \; \qquad \qquad \qquad \qquad \qquad \ldots (10)$
Dari $(1) + (10)$ , diperoleh $a = 0.$
Akibatnya, $p(x) = x$ dan $q(x) = 1$ , sehingga $p(x)^2 + q(x) = x^2 + 1$ .
Perhatikan bahwa, jika $x = 1$ , maka $p(1)^2 + q(1) = 1^2 + 1 = 0$ .
Dengan demikian, $p(x)^2 + q(x) \boxed{\text{redusibel}}$ di $GF_2[x]$ .

Versi 2
Diberikan dua polinomial $p(x)$ dan $q(x)$ di $GF_2[x]$ yang memenuhi deg $(p(x)) < 3$ , deg $(q(x)) < 2$ , dan

$\begin{align*} p(x)(1 + x + x^3) + q(x)(1 + x + x^2 + x^4) = 1. \end{align*}$

Untuk memenuhi deg $(p(x)) < 3$ dan deg $(q(x)) < 2$ , dimisalkan

$\begin{align*} &p(x)= ax^2+bx+c; &q(x)= mx+n. \end{align*}$

Selanjutnya, dilakukan subtitusi sebagai berikut.

$\begin{align*} p(x)(1 + x + x^3) + q(x)(1 + x + x^2 + x^4) &= 1 \\ (ax^2+bx+c)(1+x+x^3)+(mx+n)(1+x+x^2+x^4) &=1 \\ (ax^2+ax^3+ax^5+bx+bx^2+bx^4+c+cx+cx^3) \\+ (mx+mx^2+mx^3+mx^5+n+nx+nx^2+nx^4)&=1\\ ax^5+bx^4+ax^3+cx^3+ax^2+bx^2+bx+cx+c\\+mx^5+nx^4+mx^3+mx^2+nx^2+mx+nx+n&=1 \\ (a+m)x^5+(b+n)x^4+(a+c+m)x^3 \\+(a+b+m+n)x^2+(b+c+m+n)x+(c+n)&=1 \end{align*}$

Kemudian, diperoleh sistem persamaan linear di $GF_2$ sebagai berikut.

(1) $\begin{align*} a+m&=0 \\ b+n&=0 \\ a+c+m&=0 \\ a+b+m+n&=0 \\ b+c+m+n&=0 \\ c+n&=1 \end{align*}$

Berdasarkan $(1)$ : $m=a$ . \\
Berdasarkan $(2)$ : $n=b$ . \\
Subtitusi $m=a$ ke $(3)$ dan diperoleh:

$\begin{align*} a+c+a&=0\\2a+c&=0\\c&=0 \end{align*}$

Subtitusi $n=b$ ke $(6)$ dan diperoleh:

$\begin{align*} c+n&=1 \\ c&=1+n. \end{align*}$

Karena $c=0$ maka $n=1$ dan karena $n=b$ maka $n=b=1$ . \\
Kemudian dari $(4)$ diperoleh

$\begin{align*} a+1+0+1&=0 \\a&=0 \end{align*}$

Kemudian dilakukan verifikasi ke $(4)$ dengan

$\begin{equation*} a = 0;\quad b = 1;\quad c = 0;\quad m = 0;\quad n = 1 \end{equation*}$

$\begin{equation*} 0 + 1 + 0 + 1 = 0 \end{equation*}$

Diperoleh solusi untuk $p(x)$ dan $q(x)$ sebagai berikut.

$\begin{align*} p(x)&=ax^2+bx+c\\ &=(0)x^2+(1)x+0\\ &=x \\ q(x)&=mx+n \\ &=(0)x+1 \\ &=1 \end{align*}$

Selanjutnya akan diselidiki apakah $p(x)^2+q(x)$ irreducible di $GF_2[x]$ .

$\begin{align*} p(x)^2+q(x)=x^2+1 \end{align*}$

Apabila $p(x)^2+q(x)$ irreducible di $GF_2[x]$ , maka $p(x)^2+q(x)$ tidak memiliki akar di $GF_2$ . Dilakukan pengujian sebagai berikut.
Jika $x=0$ : $0^2+1=1$
Jika $x=1$ : $1^2+1=1+1=0$ .
Diperoleh bahwa $x=1$ adalah akar dari $x^2+1$ . Artinya:

$\begin{align*} x^2+1=(x+1)(x+1)=(x+1)^2 \end{align*}$

Dengan demikian, diperoleh kesimpulan bahwa $p(x)^2 + q(x) \boxed{\text{reducible}}$ di $GF_2[x]$ .

Video Penjelasan:

Leave A Comment Batalkan balasan

Artikel Terbaru

Komentar