FINITE FIELD (LAPANGAN BERHINGGA)

FINITE FIELD (LAPANGAN BERHINGGA)

Muhamad Zaki Riyanto NIM: 02/156792/PA/08944 E-mail: [email protected] http://zaki.math.web.id Dosen Pembimbing: Drs. Al. Sutjiana, M.Sc.

Jika suatu lapangan (field) memuat elemen yang banyaknya berhingga, maka lapangan ini disebut dengan lapangan berhingga (finite field). Berikut ini dibahas beberapa konsep mengenai lapangan berhingga.

1.1. Lapangan Berhingga Definisi 1.1.1. Suatu lapangan yang memuat elemen sebanyak berhingga disebut dengan finite field (lapangan berhingga).

Teorema 1.1.2. Himpunan ℤ n merupakan lapangan berhingga jika dan hanya jika n adalah bilangan prima. Bukti: ⇒ Andaikan n bukan bilangan prima, maka n = a.b dengan 1 < a, b < n − 1 . Karena ℤ n merupakan lapangan, maka setiap elemen tak nolnya pasti mempunyai invers. Misalkan c adalah invers dari b, berarti

a.b.c ≡ a ( mod n ) .

Karena

n = a.b

maka

b.c ≡ 1( mod n )

a.b ≡ 0 ( mod n ) ,

dan

akibatnya

0 ≡ a ( mod n ) . Timbul kontradiksi dengan pengandaian di atas. Jadi n merupakan bilangan prima.

Copyright © 2008 http://zaki.math.web.id

1

⇐ Diketahui n adalah bilangan prima. Karena ℤ n merupakan gelanggang, maka akan dibuktikan bahwa setiap elemen tak nol mempunyai invers. Karena n adalah bilangan prima, maka gcd(n, a ) = 1 , untuk 0 < a < n . Akibatnya terdapat bilangan bulat x dan y sedemikian hingga x.n + y.a = 1 yang berarti y.a ≡ 1( mod n ) , diperoleh

y ≡ a −1 ( mod n ) . Jadi terbukti bahwa setiap elemen tak nolnya

mempunyai invers. Dengan kata lain, ℤ n adalah lapangan berhingga

⁭

Definisi 1.1.3. Diberikan suatu lapangan F. Karakteristik dari F adalah bilangan m

bulat positif terkecil m sedemikian hingga

∑1

F

= 1F + 1F + ... + 1F = 0 F dengan

i=1

1F ∈ F merupakan elemen identitas terdapat pergandaan dan 0 F ∈ F merupakan elemen identitas terhadap operasi pemjumlahan. Jika tidak ada m yang memenuhi, maka karakteristik dari F adalah 0.

Teorema 1.1.4. Jika karakteristik dari lapangan F tidak nol, yaitu m ≠ 0 , maka m merupakan bilangan prima.

Bukti: Andaikan m bukan bilangan prima dan m ≠ 0 , maka m = a.b dengan a > 1 dan b

b > 1 . Diketahui m adalah karakteristik dari F. Jika s, t ∈ F dengan s = ∑1F dan t =1

a

t = ∑1F , maka maka t =1

m  a  b  a.b t.s =  ∑ 1F  .  ∑1F  = ∑1F = ∑ 1F = 0 F . Diperoleh i =1  i =1   i =1  i =1

s, t ∈ F keduanya tak nol, tetapi t.s = 0 F . Karena t ≠ 0 F maka terdapat t −1 ∈ F sedemikian hingga t −1.t.s = t −1 0 F = 0 F , padahal t −1.t.s = 1F .s . Jadi diperoleh b

1F .s = s = 0 F . Kontradiksi dengan pengandaian bahwa s = ∑1F dengan b > 1 . t =1

Dengan demikian m adalah bilangan prima.


⁭

2

Teorema 1.1.5. Jika F merupakan lapangan berhingga dengan karakteristik p, maka F memuat p n elemen untuk suatu bilangan bulat positif n.

Bukti: p

Karena F mempunyai karakteristik p, maka berlaku

∑1

F

= 1F + 1F + ... + 1F = 0 F .

i=1

Diketahui F merupakan ruang vektor atas ℤ p . Karena F lapangan berhingga, maka dimensi F berhingga. Misalkan dimensi F adalah n, maka terdapat n vektor yang bebas linear dan membangun F. Misalkan

{ x1 , x2 ,..., xn }

basis dari F,

akibatnya setiap anggota dari F dapat disajikan secara tunggal sebagai kombinasi linear dari vektor-vektor basis, yaitu

F = {α1.x1 + α 2 .x2 + ... + α n .xn : α i ∈ ℤ p } . Jadi, banyaknya elemen dari F adalah F = {α1.x1 + α 2 .x2 + ... + α n .xn } = p n .

⁭

Teorema di atas mengatakan bahwa setiap lapangan berhingga mempunyai elemen sebanyak bilangan prima atau pangkat dari bilangan prima. Selanjutnya akan ditunjukkan bahwa untuk sebarang bilangan p dan bilangan bulat positif n terdapat lapangan berhingga dengan elemen sebanyak p n . Untuk n = 1 , maka himpunan bilangan bulat modulo p membentuk suatu lapangan berhingga dengan p elemen. Untuk n ≥ 2 , dapat ditunjukkan bahwa terdapat suatu lapangan berhingga yaitu dengan memandang ℤ p [ x ] sebagai himpunan semua polinomial dalam x atas lapangan ℤ p , dan setiap polinomial mempunyai

derajad

yang

berhingga.

Sebagai

contoh,

untuk

p =2,

ℤ 2 [ x ] = {0,1, x,1 + x, x 2 ,1 + x 2 , x + x 2 ,1 + x + x 2 ,...} merupakan himpunan semua polinomial dalam x dengan derajad berhingga dan koefisiennya merupakan elemen ℤ 2 . Himpunan polinomial dalam ℤ p [ x ] membentuk suatu lapangan berhingga terhadap operasi penjumlahan dan pergandaan.


3

Dari ℤ p [ x ] ditentukan suatu polinomial irreducible (tak tereduksi) f ( x) dengan derajad n. Polinomial tak tereduksi adalah suatu polinomial yang tidak dapat dinyatakan sebagai hasil pergandaan dari dua buah polinomial dengan derajad yang lebih kecil dari derajad f ( x) dalam ℤ p [ x ] . Dengan polinomial tersebut dapat dibangun suatu lapangan dengan p n elemen. Diberikan lapangan F [ x ] dan f ( x) , g ( x) , h( x) ∈ F [ x ] .

Definisi 1.1.6. Polinomial h( x) dikatakan kongruen dengan g ( x) modulo f ( x) jika dan hanya jika terdapat suatu polinomial l ( x) ∈ F [ x ] sedemikian hingga h( x) − g ( x) = l ( x) f ( x) . Ditulis h( x) ≡ g ( x) ( mod f ( x) ) .

Dari Definisi 1.1.6 di atas, dapat dilihat bahwa h( x) dan g ( x) disebut kongruen jika f ( x) membagi selisihnya. Artinya h( x) dan g ( x) mempunyai sisa yang sama apabila dibagi dengan f ( x) . Dapat ditunjukkan bahwa kongruensi ini merupakan suatu relasi ekuivalensi pada F [ x ] , akibatnya terdapat partisi – partisi yaitu himpunan yang didefinisikan ke dalam subset – subset saling asing yaitu klas – klas ekuivalensi.

Definisi 1.1.7. Untuk suatu polinomial f ( x) ∈ F [ x ] , klas ekuivalensi yang memuat g ( x) ∈ F [ x ] adalah

[ g ( x)] = {h( x) ∈ F [ x ] : h( x) ≡ g ( x) ( mod f ( x) )} , yaitu himpunan semua polinomial yang apabila dibagi dengan

f ( x)

menghasilkan sisa yang sama dengan g ( x) .

Operasi penjumlahan dan pergandaan dalam klas – klas ekuivalensi tersebut didefinisikan sebagai berikut. Untuk g ( x) , h( x) ∈ ℤ p [ x ] ,


4

[ g ( x ) ] + [ f ( x ) ] = [ g ( x) + f ( x ) ] dan

[ g ( x)].[ f ( x)] = [ g ( x). f ( x)] . Diberikan ℤ p [ x ] / f ( x) yaitu himpunan semua klas – klas ekuivalensi dalam ℤ p [ x ] yang kongruen modulo f ( x) , dengan f ( x) adalah polinomial tak tereduksi. Menggunakan definisi operasi penjumlahan dan pergandaan klas – klas ekuivelensi di atas, maka ℤ p [ x ] / f ( x) membentuk suatu lapangan berhingga. Untuk menunjukkan bahwa setiap elemen tak nolnya mempunyai invers, diambil

[ g ( x) ] ∈ ℤ p [ x ] / f ( x) terhadap

operasi

dengan [ g ( x) ≠ 0] . Karena [1] merupakan elemen identitas

pergandaan,

[ h( x ) ] ∈ ℤ p [ x ] / f ( x )

maka

sedemikian

akan

ditujukkan

hingga

bahwa

[ g ( x)].[ h( x)] = [1]

terdapat atau

g ( x).h( x) ≡ 1( mod f ( x) ) . Karena f ( x) merupakan polinomial tak tereduksi dan f ( x) tidak membagi g ( x) , maka gcd ( g ( x), f ( x) ) = 1 . Akibatnya terdapat polinomial s ( x) dan t ( x) sedemikian hingga s ( x).g ( x) + t ( x). f ( x) = 1 atau

s ( x).g ( x) ≡ 1( mod f ( x) ) . Jadi diperoleh bahwa

[ g ( x) ]

−1

[ s( x)].[ g ( x)] = [1] ,

sehingga

= [ s ( x) ] . Untuk menunjukkan ℤ p [ x ] / f ( x) berhingga, diasumsikan

ℤ p [ x ] / f ( x) mempunyai elemen sebanyak p n , dengan mengambil sebarang klas ekuivalensi dalam ℤ p [ x ] / f ( x) , misal

[ g ( x)] .

Selanjutnya, menggunakan

algoritma pembagian dalam polinomial diperoleh g ( x) = q ( x). f ( x) + r ( x) dengan r ( x) = 0 atau derajad r ( x) lebih kecil dari derajad

f ( x) , untuk suatu

q( x), r ( x) ∈ ℤ p [ x ] / f ( x) . Jadi [ g ( x)] = [ r ( x)] , dengan r ( x) merupakan sisa jika g ( x) dibagi dengan f ( x) . Karena r ( x) = 0 atau derajad r ( x) lebih kecil dari derajad f ( x) maka tidak ada dua polinomial sisa yang berbeda dan berada pada klas yang sama. Karena


5

n −1

r ( x) = ∑ ai .x i , dengan ai ∈ ℤ p i=0

maka terdapat sebanyak p pilihan untuk setiap ai , dengan 0 ≤ i ≤ n − 1 , yang berarti terdapat sebanyak p n klas-klas sisa yang berbeda. Hal ini menunjukkan bahwa ℤ p [ x ] / f ( x) memuat sebanyak p n elemen, dengan p adalah bilangan prima.

Contoh 1.1.8. Akan dikonstruksi suatu lapangan dengan empat elemen menggunakan polinomial tak tereduksi f ( x) = x 2 + x + 1∈ ℤ 2 [ x ] .

ℤ 2 [ x ] / f ( x) = {[ g ( x)] : g ( x) ∈ ℤ 2 [ x ]}

= {h( x) : g ( x) ≡ h( x) ( mod f ( x) )} = {h( x) = l ( x). f ( x) + g ( x) : l ( x) ∈ ℤ 2 [ x ]} Polinomial

f ( x)

membentuk lapangan

ℤ 2 [ x ] / f ( x) = {[ 0] , [1] , [ x ] , [1 + x ]} .

Elemen–elemen dari ℤ 2 [ x ] / f ( x) merupakan himpunan dalam ℤ 2 [ x ] yang berderajad kurang dari dua. Operasi penjumlahannya sama dengan operasi penjumlahan

polinomial

[1 + x ] + [ x ] = [1 + 2 x ] = [1] ,

biasa

pada

ℤ 2 [ x] .

Sebagai

contohnya,

karena 2 ≡ 0 ( mod 2 ) , diperoleh bahwa lapangan

tersebut mempunyai karakteristik 2. Sedangkan untuk operasi pergandaannya sama dengan operasi pergandaan polinomial biasa pada ℤ 2 [ x ] kemudian mereduksikan hasilnya dengan menghitung sisanya setelah dibagi dengan f ( x) . Untuk mereduksinya dapat dikerjakan menggunakan pembagian biasa atau menggunakan hubungan x 2 ≡ x + 1 yang digunakan untuk mereduksi hasil pergandaan

yang

berderajad

2.

Sebagai

contohnya,

[1 + x ].[1 + x ] = 1 + 2 x + x 2  = [1 + (1 + x)] = [ x ] .


6

Lapangan berhingga F yang memuat q elemen sering dinotasikan dengan

GF ( q ) yang disebut Galois field (lapangan Galois). Perhatikan bahwa q mempunyai bentuk p n , yaitu q merupakan suatu bilangan prima p atau hasil pemangkatan dari p. Notasi GF ( p n ) adalah suatu lapangan dengan karakteristik p.

Lapangan

ℤp

dapat

dinotasikan

[ g ( x)] ∈ ℤ p [ x ] / f ( x) cukup ditulis dengan

dengan

GF ( p ) .

Selanjutnya,

g ( x) saja.

1.2. Polinomial Tak Tereduksi Definisi 1.2.1. Monic polynomial (polinomial monik) adalah suatu polinomial yang koefisien tak nol pada pangkat tertinggi dari x adalah 1.

Dalam mengkonstruksi suatu lapangan berhingga dengan

p n elemen,

digunakan suatu polinomial tak tereduksi dengan derajad n dalam GF ( p) [ x ] . Untuk menunjukkan bahwa selalu dapat ditemukan suatu polinomial tak terduksi untuk setiap bilangan bulat positif n, akan dibahas untuk n = 2 , yaitu terdapat polinomial monik tak tereduksi dalam GF ( p) [ x ] . Dalam GF ( p) [ x ] terdapat sebanyak p 2 polinomial monik dengan derajad 2. Jika salah satunya tereduksi berarti merupakan pergandaan dari dua buah polinomial monik berderajat satu. Terdapat sebanyak p polinomial monik berderajad 1. Jadi terdapat sebanyak  p   + p polinomial monik tak tereduksi. Sehingga jumlah polinomial monik tak 2 tereduksi berderajad 2 adalah  p  p I2 = p2 −   − p =   > 0 , p ≥ 2 . 2 2 Hal tersebut menunjukkan keberadaan polinomial tak tereduksi yang berderajad 2 dalam GF ( p) [ x ] . Dengan cara yang sama dapat dihitung banyaknya polinomial tak tereduksi berderajad 3. Jadi secara umum dapat disimpulkan bahwa selalu


7

dapat ditemukan suatu polinomial tak tereduksi untuk setiap bilangan bulat positif n.

1.3. Sifat-sifat Lapangan Berhingga Definisi 1.3.1. Diberikan lapangan berhingga F dan didefinisikan F * yaitu himpunan elemen-elemen dari F yang tidak nol, F * = F \{0} . Elemen α ∈ F disebut generator (pembangun) dari F * , atau disebut primitive element (elemen primitif) dari F jika

{α

i

: i ≥ 0} = F * .

Yaitu jika α membangun semua elemen tak nol dalam lapangan F.

Contoh 1.3.2. Akan dibentuk suatu lapangan dengan sembilan elemen dengan mengambil polinomial tak tereduksi

f ( x) = 1 + x 2 ∈ ℤ 3 [ x ] . Lapangan tersebut adalah

F = {0,1, 2, x, 2 x,1 + x,1 + 2 x, 2 + x, 2 + 2 x} . Jika diambil α = x , maka ternyata α tidak membangun seua elemen tak nol dalam F. Jadi α = x bukan elemen primitif. Tetapi jika diambil α = 1 + x , dapat ditunjukkan bahwa α = 1 + x membangun semua elemen tak nol dalam lapangan F. Dengan menggunakan reduksi x 2 ≡ −1( mod f ( x) ) ≡ 2 ( mod 3) diperoleh

(1 + x )

(1 + x )

4

=2

(1 + x ) = (1 + x )

(1 + x )

5

= 2 + 2x

(1 + x )

2

= 2x

(1 + x )

6

=x

(1 + x )

3

= 1+ 2x

(1 + x )

7

= 2+ x .

0

=1

1

Jadi α = 1 + x merupakan pembangun dari F = GF (9) * .

Lemma 1.3.3. Untuk setiap elemen tak nol α ∈ GF (q ) , α q −1 = 1 . Selanjutnya, suatu elemen α ∈ GF (q m ) di dalam GF (q ) jika dan hanya jika α q = α .


8

Bukti: Misalkan a1 , a2 ,..., aq −1 elemen tak nol dalam GF (q ) yang berbeda. Untuk suatu

α ∈ GF (q ) , α a1 , α a2 ,..., α aq −1 juga berbeda, karena jika tidak maka untuk suatu i ≠ j berakibat α ai = α a j , sehingga jika digandakan dengan a −1 diperoleh ai = a j . Jadi {α a1 , α a2 ,..., α aq −1} = {a1 , a2 ,..., aq −1} . Hal tersebut mengakibatkan

(α a1 )(α a2 ) ... (α aq −1 )

= a1a2 ...aq −1

α q −1 ( a1a2 ...aq −1 ) = a1a2 ...aq −1 α q −1 = 1. Jadi, jika α ∈ GF (q ) , maka α q = α yang berarti setiap elemen GF (q ) adalah akar dari polinomial x q − x . Untuk membuktikan pernyataan kedua, tinggal menunjukkan bahwa jika α q = α maka α ∈ GF (q ) . Diketahui bahwa polinomial derajad n atas GF (q ) mempunyai akar paling banyak q akar pada polinomial derajad q atas GF (q ) yang berarti q elemen dalam GF (q ) merupakan akar – akar dari polinomial x q − x . Jadi polinomial tersebut tidak mempunyai akar lain dan hal tersebut membuktikan jika α q = α , maka α ∈ GF (q ) .

⁭

Definisi 1.3.4. Order dari suatu elemen tak nol α ∈ GF (q ) adalah bilangan bulat positif terkecil t sedemikian hingga α t = 1 , ditulis ord(α ) = t .

Lemma 1.3.5. Untuk setiap elemen tak nol α ∈ GF (q ) , ord(α ) membagi q − 1 . Bukti: Misalkan

ord(α ) = t ,

untuk

suatu

α ∈ GF (q ) . Menggunakan algoritma

pembagian pada bilangan bulat maka q − 1 = l.t + r , dengan 0 ≤ r < t . Sehingga diperoleh

α q −1 = α l .t + r = α l .tα r = (α t )l α r .


9

Menurut teorema sebelumnya, α q −1 = 1 , dan diketahui α t = 1 . Jadi diperoleh

α r = 1 . Karena ord(α ) = t dan 0 ≤ r < t , maka r = 0 yang berarti bahwa t membagi q – 1.

Teorema 1.3.6.

⁭ Setiap lapangan berhingga F = GF (q ) mempunyai elemen

primitif.

Bukti: Misalkan α elemen F = GF (q ) yang mempunyai order tertinggi yaitu t. Jika t = q − 1 , maka α elemen primitif dari F. Andaikan t < q − 1 dan order dari tiap elemen tak nol GF (q ) yang lain membagi t, maka setiap elemen tak nolnya memenuhi persamaan y t − 1 = 0 . Persamaan tersebut mempunyai paling banyak t akar dalam GF (q ) , yang berarti kontradiksi dengan t < q − 1 . Berarti terdapat elemen GF (q ) , sebut β sedemikian hingga ord ( β ) tidak membagi t. Misalkan

gcd ( t , ord ( β ) ) = d , maka ord ( β ) = db untuk suatu b > 1 dan gcd ( b, t ) = 1 . Jadi

β d = γ adalah elemen dengan order b. Berarti elemen αγ mempunyai order bt > t . Kontradiksi dengan asumsi bahwa t adalah order terbesar dari sebarang elemen. Misalkan ord (αγ ) = s , berarti

(αγ )

s

(αγ )

= 1 . Karena

bt

= 1 maka

menurut Lemma 1.3.5, s membagi bt. Selanjutnya, akan ditunjukkan bahwa bt membagi s. Dapat dilihat bahwa (αγ ) = α sb = 1 dan (αγ ) = γ st = 1 , juga t sb

st

membagi sb, dan b membagi st, karena ord(α ) = t dan ord(γ ) = b . Karena gcd(b, t ) = 1 maka t membagi s, dan b membagi s. Sehingga diperoleh bahwa bt membagi s. Jadi s = bt , sehingga dapat disimpulkan bahwa t = q − 1 .

⁭

Dari Definisi 1.3.4 diperoleh bahwa elemen primitif α dari suatu lapangan GF (q ) mempunyai order q − 1 . Akibatnya α q −1 = α 0 = 1 , dan dapat dilihat bahwa pangkatnya dihitung menggunakan modulo q − 1 .


10

Lemma 1.3.7. Jika lapangan F mempunyai karakteristik p dan α , β ∈ F , maka

(α + β )

p

=α p +β p .

Bukti: Menggunakan teorema binomial diketahui bahwa p

 p

(α + β ) = ∑   α p −i β i i p

  .  p  p p −1  p  p −i i  p  p =  α + ∑  α β +   β i =1  i  0  p i=0

 p Karena   merupakan bilangan bulat, dan untuk 1 ≤ i ≤ p − 1 maka i  p p! P ( P − 1)...( P − i + 1) = = p.  = i (i − 1)...2.1  i  ( p − 1)!i !  p Jadi   ≡ 0 ( mod p ) untuk 1 ≤ i ≤ p − 1 dengan p adalah bilangan prima. i Sehingga pada persamaan binomial di atas, bentuk

p −1

 p

i =1

 

∑  i α

p −i

β i = 0 . Jadi,

diperoleh (α + β ) = α p + β p . p

⁭

1.4. Polinomial Minimal Definisi 1.4.1.

Diberikan lapangan F dengan karakteristik p, dan misalkan

α ∈ F * adalah elemen tak nol dari F. Polinomial minimal dari α terhadap GF ( p ) adalah suatu polinomial monik m( x) dengan derajad terkecil dalam

GF ( p) [ x ] sedemikian hingga m(α ) = 0 .

Teorema 1.4.2.

Polinomial minimal dari elemen α adalah tunggal.

Bukti: Andaikan F = GF (q ) dan F mempunyai karakteristik p. Dari Lemma 1.3.3 diketahui bahwa α memenuhi persamaan polinomial x q −1 − 1 dalam GF ( p) [ x ]


11

dengan α merupakan akarnya, maka salah satunya pasti ada yang memiliki derajad terkecil. Hal tersebut menunjukkan keberadaan polinomial minimal dari

α . Andaikan terdapat dua polinomial minimal dari α , yaitu m1 ( x) dan m2 ( x) dengan derajad terkecil dan mempunyai akar α . Menggunakan algoritma pembagian untuk polinomial diperoleh m1 ( x) = l ( x).m2 ( x) + r ( x) dengan derajad r ( x) < derajad m2 ( x) atau r ( x) = 0 . Karena m1 (α ) = 0 dan m2 (α ) = 0 maka diperoleh r (α ) = 0 . Karena m2 ( x) mempunyai derajad paling kecil maka r ( x) = 0 . Jadi, m2 ( x) membagi m1 ( x) . Dengan cara yang sama diperoleh bahwa m1 ( x)

membagi

m2 ( x) .

Karena

keduanya

polinomial

monik,

m1 ( x) = m2 ( x) .

maka

⁭

Karena dalam hal ini yang digunakan adalah polinomial minimal dari α , maka polinomial minimal untuk α dinotasikan dengan mα ( x) .

Teorema 1.4.3.

Polinomial minimal dari α ∈ F * yaitu mα ( x) merupakan

polinomial tak tereduksi.

Bukti: Andaikan

mα ( x)

tereduksi, maka

mα ( x) = h( x).l ( x)

untuk suatu

h( x) ,

l ( x) ∈ GF ( p) [ x ] dengan derajad h( x) ≥ 1 dan derajad l ( x) ≥ 1 . Diperoleh mα ( x) = h(α ).l (α ) = 0 yang berakibat paling tidak salah satu dari h(α ) atau l (α ) sama dengan nol. Jadi

α merupakan akar salah satu dari h( x) atau l ( x) . Hal tersebut kontradiksi dengan syarat bahwa mα ( x) adalah polinomial minimal. Jadi mα ( x) tak tereduksi.

Definisi 1.4.4.

⁭ Untuk suatu α ∈ F dan t adalah bilangan bulat terkecil

sedemikian hingga α p = α . Himpunan konjugat dari α atas GF(p) adalah t


12

{

C (α ) = α , α p , α p , α p ,..., α p 2

3

t −1

}.

Jadi, C (α ) = C (α p ) untuk suatu i dan suatu lapangan F dengan karakteristik p. i

Lemma 1.4.5.

Jika diberikan lapangan berhingga F dengan karakteristik p,

α ∈ F * dan C (α ) himpunan konjugat dari α atas GF(p), maka

∏ (x − β )

m( x ) =

β ∈C (α )

adalah polinomial dengan koefisien dalam GF(p).

Bukti: t

Misalkan m( x) = ∑ mi x i , koefisien mi di dalam F. Akan ditunjukkan bahwa mi i=0

tersebut dalam lapangan ground GF(p). m( x ) p =

∏α ( x − β ) β

p

∈C ( )

=

∏α ( x β ∈C ( )

p

−βp)=

∏α ( x β

− β ) = m( x p ) = ∑ mi x ip t

p

∈C ( )

i =0

dengan persamaan pertama diperoleh dari Lemma 1.3.7, dan persamaan ketiga karena {β : β ∈ C (α )} = {β p : β ∈ C (α )} . Di lain pihak m( x) p = ∑ ( mi x i ) =∑ mi p x ip . t

t

p

i =0

i =0

Jadi mi = mi p , menggunakan Lemma 1.3.3, diperoleh mi ∈ GF ( p ) , untuk 0≤i≤t.

⁭

Teorema 1.4.6. Untuk suatu α ∈ F * , maka polinomial minimal dari α adalah

mα ( x) =

∏ (x − β ) .

β ∈C (α )

Bukti: Akan ditunjukkan bahwa mα (α ) = 0 dan mα (α p ) = 0 .

mα ( x) = mα (α ) =

∏ (x − β ) ,

β ∈C (α )

∏α (α − β ) = (α − α ) (α − α ) (α − α β p

∈C ( )


p2

) ...(α − α ) = 0 . p t −1

13

Jadi α merupakan akar dari mα ( x) . t

Misalkan m( x) = ∑ mi x i , dengan mi ∈ GF ( p ) . Menurut Definisi berarti α i=0

merupakan akar, karena t

t

mα (α p ) = ∑ miα p = ∑ miα pi ( mi p = mi karena mi ∈ GF ( p ) ) i

i =0

i =0

p

 t  =  ∑ miα i  (menggunakan Lemma 1.3.7)  i=0  = [ mα (α )] = 0 p = 0 . p

Akibatnya semua elemen dalam C (α ) merupakan akar dari mα ( x) .

⁭

1.5. Contoh Lapangan Berhingga Contoh 1.5.1. Akan dibangun lapangan berhingga F = GF (23 ) . Pertama, dipilih polinomial tak tereduksi berorder 3 atas ℤ 2 , yaitu f ( x) = x3 + x + 1 . Elemen – elemen dari

{

}

F = [ 0] , [1] , [ x ] , [1 + x ] ,  x 2  , 1 + x 2  ,  x + x 2  , 1 + x + x 2  . Selanjutnya, untuk menyederhanakan tanda dalam kurung yang menunjukkan kelas ekuivalensi dapat dihilangkan. Pergandaan dari elemen – elemen F adalah pergandaan modulo f ( x) ,

yaitu

x3 + x + 1 ≡ 0 ( mod f ( x) ) ,

maka

diperoleh

x3 ≡ − x − 1 ≡ x + 1( mod f ( x) ) , sebab 1 ≡ −1 dalam ℤ 2 . Untuk suatu elemen lapangan a0 + a1 x + a2 x 2 dapat disajikan dalam bentuk 3-tuple (a0 a1a2 ) dengan mengurutkan dari pangkat terkecil ke pangkat yang besar. Dengan penyajian tersebut maka elemen dari lapangan F adalah 0 = (000)

1 + x = (110)

1 = (100)

1 + x 2 = (101)

x = (010)

x + x 2 = (011)

x 2 = (001)

1 + x + x 2 = (111)


14

Jika diambil α = x , maka dapat dengan mudah ditunjukkan bahwa α membangun F. Dan khusus untuk lapangan ini maka dapat ditunjukkan bahwa setiap elemen yang bukan 1 merupakan pembangun. Misal diambil β = (101) dan akan dihitung mβ ( x) . Menggunakan Teorema 1.4.6, mβ ( x) =

∏β ( y − δ ) = ( y − β ) ( y − β )( y − β ) , sebab β δ 2

4

8

=β.

∈C ( )

Sehingga diperoleh

( y − β ) ( y − β 2 )( y − β 4 ) = y 3 + ( β + β 2 + β 4 ) y 2 + ( ββ + ββ 4 + β 2 β 4 ) y + ββ 2 β 4 . Untuk mempermudah perhitungan, elemen – elemen tak nol dari F dibuat penyajiannya dalam bentuk pangkat dari pembangunnya, yaitu α = x .

α 0 = (100)

α 4 = (011)

α 1 = (010)

α 5 = (111)

α 2 = (001)

α 6 = (101)

α 3 = (110)

α7 =α0 =1

Karena β = α 6 maka β 2 = α 12 = α 5 dan β 4 = α 24 = α 3 . Perlu diingat bahwa pangkatnya dikerjakan dengan modulo 8 – 1 = 7, yaitu order dari grup siklik yang dibangun oleh α . Jadi diperoleh

β + β 2 + β 4 = α 6 + α 5 + α 3 = (101) + (111) + (110) = 1 ββ 2 + ββ 4 + β 2 β 4 = β 3 + β 5 + β 6 = α 18 + α 30 + α 36 = α 4 + α 2 + α = 0 ββ 2 β 4 = β 7 = α 42 = 1 . Sehingga diperoleh mβ ( y ) = y 3 + y 2 + 1 . Polinomial minimal tersebut juga merupakan polinomial minimal untuk β 2 dan β 4 . Polinomial minimal untuk α dapat dihitung sebagai berikut. mα ( x) =

∏α ( y − δ ) = ( y − α ) ( y − α )( y − α ) . δ 2

4

∈C ( )

Seperti untuk β , kemudian dihitung

( y − α ) ( y − α 2 )( y − α 4 )

=

y 3 + (α + α 2 + α 4 ) y 2 + (αα 2 + αα 4 + α 2α 4 ) y + αα 2α 4 Copyright © 2008 http://zaki.math.web.id

15

α + α 2 + α 4 = (010) + (001) + (011) = 0 αα 2 + αα 4 + α 2α 4 = α 3 + α 5 + α 6 = (110) + (111) + (101) = 1 αα 2α 4 = α 7 = 1 . Jadi polinomial minimal untuk α akan sama dengan polinomial minimal untuk

α 2 dan α 4 , yaitu mα ( y ) = y 3 + y + 1 . Contoh 1.5.2. Akan dibangun suatu lapangan berhingga polinomial

f ( x) = x 4 + x + 1∈ ℤ 2 [ x ] .

Dalam

F = GF (2 4 ) hal

ini

menggunakan

α=x

merupakan

pembangun lapangan F.

α 0 = (1000)

α 8 = (1010)

α 1 = (0100)

α 9 = (0101)

α 2 = (0010)

α 10 = (1110)

α 3 = (0001)

α 11 = (0111)

α 4 = (1100)

α 12 = (1111)

α 5 = (0110)

α 13 = (1011)

α 6 = (0011)

α 14 = (1001)

α 7 = (1101)

α 15 = α 0 = 1

Polinomial minimal untuk β ∈ F adalah mβ ( y ) =

∏ ( y −δ )

δ ∈C ( β )

= ( y − β ) ( y − β 2 )( y − β 4 )( y − β 8 ) , karena β 16 = β

= y 4 + ( β + β 2 + β 4 + β 8 ) y 3 + ( ββ 2 + ββ 4 + ββ 8 + β 2 β 4 + β 2 β 8 + β 4 β 8 ) y 2 + ( ββ 2 β 4 + ββ 2 β 8 + ββ 4 β 8 + β 2 β 4 β 8 ) y + ββ 2 β 4 β 8

= y 4 + ( β + β 2 + β 4 + β 8 ) y 3 + ( β 3 + β 5 + β 9 + β 6 + β 10 + β 12 ) y 2 + ( β 7 + β 11 + β 13 + β 14 ) y + β 15 .


16

Jadi,

β =α ,

untuk

C (α ) = {α , α 2 , α 4 , α 8 } ,

karena

maka

m1 ( y ) = m2 ( y ) = m3 ( y ) = m4 ( y ) .

β + β 2 + β 4 + β 8 = α +α 2 +α 4 +α8 = (1000) + (0010) + (1100) + (1010) = 0

β 3 + β 5 + β 9 + β 6 + β 10 + β 12 = α 3 + α 5 + α 9 + α 6 + α 10 + α 12 = (0001) + (0110) + (0101) + (0011) + (1110) + (1111) = 0

β 7 + β 11 + β 13 + β 14 = α 7 + α 11 + α 13 + α 14 = (1101) + (0111) + (1011) + (1001) = 1

β 15 = α 15 = α 0 = 1 . Jadi diperoleh m1 ( y ) = y 4 + y + 1 = m2 ( y ) = m4 ( y ) = m8 ( y ) . Untuk β = α 3 , maka C (α 3 ) = {α 3 , α 6 , α 12 , α 24 } = {α 3 , α 6 , α 12 , α 9 } . Jadi diperoleh

m3 ( y ) = m6 ( y ) = m9 ( y ) = m12 ( y ) , dan

β + β 2 + β 4 + β 8 = α 3 + α 6 + α 12 + α 9 = (0001) + (0011) + (1111) + (0101) = 1

β 3 + β 5 + β 9 + β 6 + β 10 + β 12 = α 9 + α 15 + α 12 + α 3 + α 0 + α 12 = (0101) + (1000) + (1111) + (0001) + (1000) + (1111) = 1

β 7 + β 11 + β 13 + β 14 = α 6 + α 3 + α 9 + α 12 = (0011) + (0001) + (0101) + (1111) = 1

β 15 = α 0 = 1 . Jadi

diperoleh

m3 ( y ) = y 4 + y 3 + y 2 + y + 1 = m6 ( y ) = m9 ( y ) = m12 ( y ) .

Untuk

β = α 5 maka C (α 5 ) = {α 5 , α 10 } sehingga m5 ( y ) = m10 ( y ) , yaitu m5 ( y ) =

∏β ( y − δ ) = ( y − α )( y − α ) = y + (α δ 5

∈C ( )


10

2

5

+ α 10 ) y + α 5α 10

17

dengan α 5 + α 10 = (0110) + (1110) = 1 dan α 15 = α 0 = 1 . Sehingga diperoleh

m5 ( y ) = y 2 + y + 1 = m10 ( y ) . Untuk β = α 7 , C (α 7 ) = {α 7 , α 14 , α 13 , α 11} sehingga dengan cara yang sama diperoleh m7 ( y ) = y 4 + y 3 + 1 = m14 ( y ) = m13 ( y ) = m11 ( y ) . Selanjutnya, diperoleh m0 ( y ) = y + 1 .

DAFTAR PUSTAKA Fraleigh, John B., 2000, A First Course in Abstract Algebra, Sixth Edition, Addison-Wesley Publishing Company, Inc., USA. Vanstone, Scott A. and van Oorschot, Paul C., 1989, An Introduction to Error Correcting Codes with Applications, Kluwer Academic Publishers, Massachusetts, USA.


18

FINITE FIELD (LAPANGAN BERHINGGA)

Recommend Documents