BAB III PEMBAHASAN TEOREMA DAN LEMMA YANG DIBUTUHKAN DALAM KONSTRUKSI ARITMETIK GF(5m)
Teori finite field mulai diperkenalkan pada abad ke tujuh dan abad ke delapan, dengan tokoh matematikanya Pierre de Fermat (1601-1665) dan Leonhard Euler (1707-1783) dengan kontribusinya pada khusus teori struktur finite field. Teori secara umum tentang finite field mulai dikerjakan oleh Carl Friedrich Gauss (1777-1855) dan Evariste Galois (1811-1832), teori ini banyak dikembangkan dalam dunia aplikasi matematika, komputer, dan teori komunikasi. (5), langkah pertama yang
Dalam melakukan konstruksi finite field
dilakukan adalah dengan memilih polinomial irredusibel berderajat 5 atas Z ,
misalkan
( ) ϵ Z[x]. Kenapa kita memilih polinomial irredusibel f(x) ? karena
dengan memilih polinomial irredusibel
f(x), menurut Teorema 2.35 [ ]/〈 ( )〉 ≃
〈 ( 〉)merupakan field. Menurut Teorema 2.39 menurut
{
+
Teorema
2.44 |
+ ⋯+
,
[ ]/〈 ( )〉
,…,
dapat
}.
[ ]/
( ,)sehingga
ditulis
Langkah
sebagai
selanjutnya
mengetes apakah polinomial irredusibel f(x) tersebut mempunyai akar atau tidak. Hasilnya dipergunakan untuk mengkonstruksi perluasan field F. Teorema berikut menjelaskan bahwa
[ ]/〈 ( )〉 ≃
). (5
( )≃
Teorema 3.1. Misal p x yaitu polinomial irredusibel berderajat n atas Z p . ( )=
Bukti:
+
+ ⋯+
,
,…,
merupakan field.
Diketahui p x yaitu polinomial irredusibel berderajat m atas Z p . Misalkan :
[ ]→
)( yaitu fungsi yang didefinisikan
( )
= ( )
Fungsi f dibawah operasi dan merupakan homomorfisma karena ( ( ) + ( )) = ( ( ) + ( )) =( =
( )
( ( )) +
( )
( )) +( ( )
( ( ))
( ))
(. )
15
( ( ). ( )) = ( ( ). ( )) =(
=
( )
( ( )).
( )
Fungsi f surjektif karena ambil (
sedemikian hingga Kernel dari f yaitu ( ) =
( )
( )) =
={ ( )
( ( ))
( ))
( )
( ) terdapat
( )
( )
[ ]
=0
( ) = 0}
[ | }( )
= 〈 ( 〉)
( )).( ( )
( )
( )
[ ]
( )
Karena fungsi f homomorfisma dan surjektif maka f epimorfisma. Selanjutnya dengan memandang Teorema Dasar ( ). Menurut Teorema 2.35 F x
[ ]/〈 ( )〉 ≅
homomorfisma maka p x
( ) juga
field maka terbukti
field.
Akibat dari teorema di atas, maka
(5) sebagai berikut .
sehingga diperoleh representasi 1.
field
2.
field
3.
(5) = {
+
|
+ ⋯+
,
( )≃
field GF(5m) ,…,
(5) = {[
, ,…,
berdimensi m
}.
dapat dipandang sebagai vektor dengan koordinatnya
},
,
sehingga ,…,
]|
Misal diberikan field hingga himpunan
) (5
}
,…,
(5) dapat dipandang sebagai ruang vektor atas
dengan basis standar {1, { ,
[ ]/〈 ( )〉 ≃
unsur-unsur
kita ,
,…,
dapat
menulis
}.
(5) dan didefinisikan
(5)∗ yaitu
(5) yang bukan nol dan dinotasikan dengan
(5)\{0}. Dua teorema berikut menjelaskan bahwa
(5)∗ merupakan
grup siklik multiplikatif dan mempunyai generator c yang merupakan unsur primitif dari Teorema 3.2.
(5).
Bukti: Dari Definisi field Karena
( )∗ merupakan grup siklik multiplikatif ber order ( )∗ merupakan grup multiplikatif. Misal
( )∗ ber order
− 1 maka c i mempunyai paling banyak
nilai yang berbeda. r Z dengan 1 ≤
≤
− 1 sedemikian sehingga
− 1.
()∗
−1
16
c r i ci
c r ci c i ci c i
c r ci c i 1
(Sifat Assosiatif)
cr 1.
Dapat disimpulkan r Z minimum sehingga O c r . Pilih c sehingga r sebesar mungkin. Akan ditunjukkan order l dari sembarang yaitu membagi r. Untuk sembarang prima , misal r a r ' dan
()∗
l b l ' dimana r ' dan l ' tidak dapat dibagi oleh . Maka c
a
mempunyai
a
order r ' , l ' mempunyai order b , dan c l ' mempunyai order b r ' . Dari sini diperoleh b a atau r tidak maksimal. Dapat disimpulkan setiap pangkat prima pembagi dari l juga pembagi dari r dan l r . ()∗
Maka setiap dibagi oleh
x . F *
≤
−1
x x
maka p n 1
memenuhi persamaan x r 1 0 . Artinya x r 1 dapat Karena ∃
−1
diperoleh
1 dan.
F *
Teorema 3.3. Sembarang
( )∗ =
=
, ,
− 1.
,…,
)(∗ ,
≥
,
=1
Sehingga
( ) memuat suatu unsur
primitif.
− 1 tetapi
diperoleh
primitif atau akar
Bukti: ( ) field berhingga berorder
Misal siklik primitif.
( )∗ . Dari Definisi 2.43 maka c merupakan unsur primitif atau akar
Karena
akibatnya
. Ambil c sebagai generator grup
(5 )∗
(5)∗ merupakan
sehingga
(5) = 0, 1,
grup
siklik
(5)∗ = 〈 〉 = 1,
, ,...,
polinomial, dan representasi integer dalam ( )= +
+2
, ,...,
.
Sebagai
. Tabel berikut ini menunjukkan
adanya hubungan antara representasi elemen polinomial primitif
multiplikatif, maka terdapat
primitif, representasi basis (5) yang dibangun oleh
17
Tabel 1. finite field No. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
Elemen primitif 0
=1
( )
Representasi Basis
Integer
0
0
1
1 5
3+4
23
2+3
17
2+4
22
4+4
24
2
2
2
10
4+3
19
1+3
16
4+
9
3+3
18
4
4
4
20
3+
8
2+
7
3+2
13
1+
6
3
3
3
15
1+2
11
2+2
12
4+2
14
1+4
21
18
3.1. Polinomial Minimum Kenapa kita perlu membahas polinomial minimum ? Karena polinomial minimum menjamin bahwa polinomial tersebut adalah irredusibel dan jika berunsur primitif merupakan polinomial primitif. polinomial primitif inilah yang (5).
akan kita gunakan dalam mengkonstruksi algoritme aritmetik
Definisi 3.4. polinomial minimum M x dari c atas Z p merupakan polinomial monik berderajat terendah dengan koefisien dari Z p sehingga M c 0 . Teorema 3.5. Misalkan m(x) adalah polinomial minimum dengan unsur α dalam finite field GF(pm). Maka (i)
m(x) irredusibel
(ii)
jika α akar dari polinomial f(x) dengan koefisien didalam GF (p), maka m(x) membagi f(x) −
(iii)
m(x) membagi
(iv)
derajat
(v)
Polinomial minimum berunsur primitif dari
( )≤
( ) yang berderajat m
merupakan polinomial primitif. Bukti : (i)
Jika m(x) redusibel, maka
( )=
( ) ( Sebagai ). akibatnya
( ) = .0 Karena tidak memuat pembagi nol, maka
( ) = 0atau
( ) = 0.Hal ini kontradiksi dengan Definisi 3.4. Sehingga dapat ( p) olinomial irredusibel.
disimpulkan bahwa
(ii) Dengan menggunakan algoritma pembagian, dimana derajat dari ( )=
( )lebih rendah daripada derajat
( ) = 0, ( ). = Dan 0 karena derajat dari
daripada derajat
( ,)maka
( ) ≈ .0
(iii) Dari pembuktian sifat (ii) terbukti m(x) membagi () dan
(iv) Karena Ada +
( )=
∑ (. Maka )
= 0 dan terdapat
,…,
( )lebih rendah
−
( )≤
(.)
} yang tak bebas linear.
= {1, 2, … , sehingga }
merupakan polinomial berderajat ≤
mempunyai akar c sehingga derajat
( ) +, ( )
( .) Karena
( ) ruang vektor berdimensi m atas
+ 1sembarang anggota yaitu {1, + ⋯+
( )
yang
19
() unsur primitif. Menurut sifat 1, polinomial minimum
(v) Misal
( )berderajat d merupakan polinomial irredusibel. Dengan Teorema ( )untuk membangun field F ber order
3.1, gunakan
memuat c dan semua unsur dari
( ), maka
( ) ≤ , mengakibatkan
menurut sifat 4, derajat
=
. Karena F
≥ . Selanjutnya
Dua teorema berikut menegaskan tentang eksistensi dan ketunggalan dari (5).
finite field
Teorema 3.6. Semua field hingga ber order
adalah isomorfik.
Bukti: Misal F dan G field ber order dan
. Misal
( )polinomial minimum dari F
( )polinomial minimum lain dari G . Menurut Teorema 3.3, F
dan G merupakan unsur primitif atau akar primitif dari F dan dari G, dan dengan Teorema 3.5.5 merupakan polinomial primitif. Dengan Teorema 3.5.3,. ( |)
−
. Dan dari Teorema 3.5.4, derajat
( ) ≤ sehingga dengan
Teorema 3.1, field F dan G dapat dianggap memuat semua polinomial dalam dan berderajat n 1 , yaitu memuat polinomial modulo
( .)Maka dapat
dikatakan pemetaan merupakan isomorfima pemetaan F G .
≥ 1, maka ada
Teorema 3.7. Untuk sembarang p prima dan bilangan bulat tunggal field ber order
yang dinotasikan dengan
Bukti: Misal Untuk Untuk
( ). perluasan field hingga dari
= 1, GF p Z p .
( ).
( .. )
> 1bentuk F1 GF p .
Akan dibuktikan
( ) field yang memuat semua akar dari .
Misal f1 x faktor irredusibel berderajat 2 dari
−
−
atas F1 . Menurut
−
atas F2 . Menurut
Teorema 3.1 dengan menggunakan p x f1 x dapat diperoleh field baru F2 . Misal f 2 x faktor irredusibel berderajat 2 dari
Teorema 3.1 dengan menggunakan p x f 2 x dapat diperoleh field baru F3 . ….sampai diperoleh field Fr yang unik, memuat semua akar dari
− .
20
( )=
Sehingga diperoleh:
−
= ( ) ( )… ( ) ( ).
Berikut ini merupakan Teorema dan Lemma sub field dari
Lemma 3.8. Jika n, r, s bilangan bulat dengan n 1, r 1, s 1 , maka n s 1 n r 1 jika dan hanya jika s r . Bukti: Misal r Qs R dimana 0 R s . Qs n r 1 nQs R 1 1 nr 1 R n . n ns 1 ns 1 ns 1 ns 1
Maka n Qs 1 selalu dapat dibagi dengan n s 1 . Teorema 3.9. i)
GF p r
memuat sub field (isomorfik dengan ) GF p s jika dan hanya jika
s r. ii) Jika c GF p r , maka c GF p s jika dan hanya jika c p c . Untuk s
sembarang field jika c 2 c , maka c yaitu 0 atau 1. Bukti: i)
) Misal c GF p s
merupakan unsur primitif maka c p
s
1
1 sehingga
O c p s 1 Karena GF p s sub field GF p r maka c GF p r sehingga c p
r
1
1 . Berdasarkan sifat dasar ketiga dalam Ringkasan 2.3, maka
p s 1 p r 1 dan selanjutnya dengan Lemma 3.11 mengakibatkan s r .
) Misal c GF p s merupakan unsur primitif maka c p
s
1
1 sehingga
O c p s 1 . Dengan Lemma 3.11, karena s r diperoleh p s 1 p r 1 . Karena p s 1 p r 1 dan GF p s sub field GF p r akibatnya c p sehingga c GF p r .
s
1
1
21
ii) ) Diketahui c GF p r , maka c GF p s . Dari Teorema Fermat setiap unsur c GF p s memenuhi c p c . s
) Misalkan c GF p r dan diketahui c p c . Dari i) karena GF p s sub s
field GF p r maka c GF p s . =
↔
−
=0↔ (
− 1) = 0. Karena merupakan Daerah Integral dan
tidak memuat pembagi nol diperoleh c 0 atau.
−1=0↔
=1
Dari teorema di atas, kita bisa mengetahui bahwa sub field dari adalah
(5 ),
(5 ),
(5 ),
dapat digambarkan sebagai berikut :
(5 ),
(5 ), dan
(5) . Secara
(5 )
jelas
(5 ) (5 ) (5 )
(5 )
(5)
(5 )
Gambar 2. Subfield dari
(5 )
Untuk mencari polinomial monik dan irredusibel dalam teorema berikut ini. Teorema 3.10.
−
(5) digunakan
=perkalian semua polinomial monik, irredusibel atas
Z p yang derajatnya membagi m.
Bukti: ) Misal M x polinomial irredusibel atas Z p berderajat d, dimana
| .
Untuk kasus M x x trivial. Asumsi M x x . Gunakan M x untuk membuat field, maka M x merupakan polinomial minimum. Misalkan −
dan dari Teorema3.5.3:
( |)
( )=
− . Dengan memandang Lemma
22
3.8,
|
karena
− 1|
maka
− 1. Oleh karena itu
1
) Misal M x pembagi dari
( |)
Akan ditunjukkan | . Asumsi.
−1
dan
−
− .
−
↔
−
− , polinomial irredusibel, dan berderajat d. ( )≠
( )−1 − 1. Gunakan M x
→
field GF p d ber order p d . Misal c GF p d akar dari
untuk membuat
M x dan GF p d merupakan unsur primitif dapat dinyatakan
a0 a1c a2 c 2 ... ad 1c d 1 M x
Karena c akar dari .
maka
=
.
↔
(*)
(menurut Teorema 2.44)
( )=0↔
maka
−
= 1. Dari (*) dan Teorema 2.16:
−
diperoleh
=0↔
=
↔
=0↔
a b
=
Berdasarkan sifat dasar ketiga dalam Ringkasan 2.5 maka
p
=
↔
ap bp
↔
= 1.
pd 1 pn 1 .
Selanjutnya dengan Lemma 3.8 diperoleh d n . Dari teorema di atas kita dapat mencari polinomial irredusibel dan polinomial (5) sebagai berikut :
monik dalam Untuk
=1
( )=
−
Untuk
=
= (
=2
( )=
= (
(
=
= (
−
=
+ 1)(
+ 2)(
+ 3)(
+4
+ 2)( +4
+ 4)
+ 3)(
+2
(
+ 3)(
+ 1)(
(
+ 2)(
+4
= ( (
+ 2)(
+2
Dan seterusnya
=
+ 3)(
( + 4) = (
+ 3)( =
+ 4)(
+ 1)(
+ 1)(
+ 4)
+ 4)
( + 4)
+ 1)(
+ 4)
+ 4)( +
+ 1)(
+ 1)(
+ 4)
+ 2)(
+ 1)(
+3
+3
+ 4)(
+ 4)(
+ 2)( + 4
+
+ 2)
+ 4)( + 3)
+ 1)
+ 2)
23
Untuk memeriksa bahwa polinomial yang diperoleh merupakan polinomial irredusibel dan polinomial primitif digunakan dua teorema berikut ini. Teorema 3.11. Jika p adalah prima dan m adalah intejer positif, maka berlaku : 1) Produk dari semua polinomial irredusibel monik dalam Ζp[x] yang derajatnya −
membagi m atau faktor dari m sama dengan
.
2) Misalkan f(x) adalah polinomial berderajat m dalam Ζp[x], maka f(x) ( ),
irredusibel atas Ζp[x] jika dan hanya jika setiap 1 ≤
≤
Bukti :
−
= 1, untuk
| . Untuk
1) Misalkan f(x) polinomial irredusibel atas Ζp berderajat m, dimana kasus f(x) = x trivial. Asumsi ( ) ≠
.Gunakan f(x) untuk membuat field
GF(pm), maka f(x) merupakan polinomial minimum. Misalkan ( ) = ( )
dan dari Teorema 3.5.4 maka
Lemma 3.8 dan karena
| maka
− 1. Dengan memandang
− 1|
− 1 dan
− 1. Dengan demikian ( )
−1
−
| . Asumsi
ditunjukkan bahwa
( )≠
→
( )
− 1. Gunakan f(x)
() adalah akar
() merupakan unsur primitif maka menurut Teorema
dari f(x) dan
2.43 dapat dinyatakan sebagai
adalah akar dari f(x), maka .
↔
=
= 1.
Dari (*) dan Teorema 2.17 maka ( −
=0↔
=
+
+⋯+
( )=0↔
↔
+
.
)=
=
+
(*). Karena α
−
=0↔
.
Selanjutnya berdasarkan Lemma 3.8 maka diperoleh
↔
| .
2) Berdasarkan Teorema 3.11 1), bahwa setiap intejer positif −
membagi k. Jadi
=
↔
sehingga diperoleh :
Berdasarkan sifat ketiga pada Ringkasan 2.5 maka
polinomial
↔
− . Sebaliknya misalkan
untuk membuat field GF(pm) ber order pm. Misalkan
=
−
− , polinomial irredusibel dan berderajat m. Akan
f(x) pembagi dari
.
−
=1
− 1|
− 1.
≥ 1, maka
adalah produk dari semua irredusibel monik berderajat (−
, ( )) adalah pasti produk dari semua faktor
linear f(x). Jika f(x) tidak mempunyai faktor linear maka
( −
, ( ))
24
adalah pasti produk dari semua faktor irredusibel quadratik dari f(x). Jika f(x) tidak irredusibel maka harus dapat dibagi oleh beberapa polinomial /2 dan jika g(x) adalah faktor
irredusibel berderajat paling banyak
≤ /2 . Jadi
irredusibel dari f(x) berderajat minimum (misalkan k), maka ( −
, ( )) ≠ 1.
Hal
ini
kontradiksi
dengan −
Sebaliknya jika f(x) adalah irredusibel, maka untuk setiap 1 ≤
≤
cukup dites
pengandaian. , ( )
= 1,
. Jadi untuk mengetes f(x) adalah irredusibel, hal ini ,( )
−
= 1 untuk setiap intejer positif 1 ≤
. Dengan demikian dapat disimpulkan bahwa f(x) adalah irredusibel
≤
Teorema 3.12. Misalkan p adalah bilangan prima dan misalkan mempunyai faktor-faktor prima yang berbeda dari pm-1 adalah r1, r2, …, rt maka polinomial irredusibel 1≤
( )
≤ berlaku
( )[ ] adalah ≠ 1(
Bukti :
primitif jika dan hanya jika untuk setiap ( )) − 1 adalah
Misalkan p adalah bilangan prima dan misalkan faktorisasi dari
r1, r2, …, rt , dimana r1, r2, …, rt adalah polinomial irredusibel atas GF(p)[x].
Akan dibuktikan bahwa jika x adalah unsur primitif atas GF(pm)* maka berlaku ( ) untuk setiap 1 ≤
≠1
≤
Misalkan d dinotasikan order dari x. Kita tahu bahwa d adalah pembagi dari − 1 dan x adalah primitif jika dan hanya jika
Pertama, andaikan bahwa
1
≤
− 1/
sehingga pasti
( ) untuk 1 ≤
− 1 dan
<
≡ 1( ≠
≤ dan juga
− 1.
( )) untuk beberapa i, maka jelas bahwa
− 1. Sebaliknya, andaikan bahwa ≠
− 1)/ . Dengan demikian
kontradiksi dengan pernyataan bahwa
≠
− 1. Karena d adalah pembagi dari
− 1 maka terdapat polinomial irredusibel ri dimana 1 ≤
sedemikian sehingga ri adalah pembagi dari (
adalah pembagi (
=
≤
− 1)/ . Tetapi ini berakibat bahwa d
≠1
≡
( )
≡ 1(
( )). Hal ini
