PERNYATAAN MENGENAI TESIS DAN SUMBER INFORMASI
Dengan ini saya menyatakan bahwa tesis Konstruksi Algoritme Aritmetik (5 ) Dengan Operasi Dibangkitkan Dari Sifat Grup siklik adalah karya saya dengan arahan dari komisi pembimbing dan belum diajukan dalam bentuk apapun kepada perguruan tinggi manapun. Sumber informasi yang berasal atau dikutip dari karya yang diterbitkan maupun tidak diterbitkan dari penulis lain telah disebutkan dalam teks dan dicantumkan dalam Daftar Pustaka di bagian akhir tesis. Bogor, Agustus 2009 Ahmadi NRP G551070691
ABSTRACT AHMADI. The Construction of Arithmetic Algorithms ( ) Generated by Cyclic Group Properties. Supervised by SUGI GURITMAN and NUR ALIATININGTYAS. To construct a cryptographic algorithm, many arithmetic concepts are needed. ElGamal encryption for example, can be defined over cyclic group ∗ , the usual arithmetic concepts. If the use of this arithmetic is associated with security aspect, then it requires large computational work. This thesis aims to construct arithmetic algorithm as an alternative arithmetic that can be applied to any cryptographic scheme, especially public key scheme. This algorithm is imposed (5). Thus, the procedures to construct arithmetic algorithm from finite field are as follows. The first step is to choose primitive polynomial ( ) [ ]of lower degree. The second step is to find primitive root M(α) = 0 , thus the equation ( ) = 0 has a root α in (5). The resulted arithmetic algorithms (5 ): addition, are computational procedures for standard operation in multiplication, division, invertion, and exponentiation. It can be concluded that (5) are better than standard algorithms constructed arithmetic algorithms because some operations can be reduced using primitive polynomial or cyclic group properties, and using reduction of zero. Keywords: arithmetic, cyclic group,
(5), primitive polynomial, cryptography.
RINGKASAN (5 ) Dengan Operasi AHMADI. Konstruksi Algoritme Aritmetik Dibangkitkan Dari Sifat Grup siklik. Dibimbing oleh SUGI GURITMAN dan NUR ALIATININGTYAS. Masalah keamanan merupakan salah satu aspek penting dari sebuah sistem informasi. Untuk menjamin keamanan sebuah informasi yang bersifat rahasia diperlukan suatu teknik pengamanan baik secara fisik maupun non fisik. Salah satu teknik pengamanan secara non fisik yaitu dengan mengenkripsi informasi rahasia menggunakan teknik kriptografi. Kriptografi secara terminologi dasarnya terdiri dari dua tipe yaitu kriptografi simetrik dan kriptografi asimetrik atau sering disebut sebagai kriptografi kunci publik. Kunci simetris adalah jenis kriptografi yang paling umum digunakan. Kunci untuk membuat pesan yang disandikan sama dengan kunci untuk membuka pesan yang disandikan itu. Kunci asimetris merupakan pasangan kunci kriptografi yang salah satunya digunakan untuk proses enkripsi dan yang satu lagi untuk dekripsi. Contoh algoritme terkenal yang menggunakan kunci asimetrik adalah skema yang ditemukan oleh ElGamal pada tahun 1985. Skema ini didasarkan pada pemecahan problem logaritma diskret. Keamanan algoritme ini sangat tergantung pada pemilihan bilangan prima p. Semakin besar p maka algoritme ini akan semakin aman, akan tetapi semakin besar pula beban komputasi yang digunakan. Oleh karena itu pada masa sekarang, orang sudah mulai mencari alternatif lain untuk menggantikan aritmetik modular diantaranya ( ), kurva eliptik kriptografi, aritmetik yang dibangkitkan struktur finite field dan hipereliptik kriptografi. ( ) yang pernah Sebenarnya sudah banyak sekali penelitian tentang dilakukan, diantaranya adalah paper berjudul ”Montgomery Multiplication in GF(2k)” menunjukkan operasi perkalian = . . dalam field GF(2k) dimana r adalah unsur tetap dari field dapat diimplementasikan lebih cepat dalam perangkat lunak dibandingkan dengan operasi perkalian standar (Koc, 1998), paper berjudul ”Analysis and Construction of Galois Field for Efficient Storage Reliability” juga menganalisis adanya implementasi berdasarkan tabel dan teknik (2) (Greenan, 2007), dan optimasi operasi perkalian dan pembagian dalam thesis berjudul ”Konstruksi Algoritme Aritmetik (2) Dengan Operasi Perkalian Dibangkitkan Dari Sifat Grup Siklik” menyebutkan bahwa algoritme aritmetik hasil konstruksi cukup cepat dalam perhitungan komputasinya (Rosdiana, 2009). Dalam thesis ini peneliti mencoba mengkonstruksi aritmetik yang berbeda (5) dan dengan pendekatan yang sama dari dari sebelumnya yaitu aritmetik konstruksi yang telah dilakukan oleh Ibu Sri Rosdiana (2009) yaitu (5) didasarkan pada sifat bahwa mendefinisikan sekaligus mengkonstruksi (5 )∗ merupakan grup siklik yang dibangkitkan dari akar primitif. Penelitian ini bertujuan mengkonstruksi finite field (5) dengan memperhatikan segi kecepatan dan kapasitas memori yang digunakan. (5 ) dalam penelitian ini langkah Untuk mengkonstruksi aritmetik pertama adalah dengan memilih polinomial primitif berderajat m atas Z5, misal
( ) ∈ [ ] dimana ( ) = + +⋯ . Langkah kedua tentukan (5 ) unsur primitifnya misal α sehingga M(α) = 0. Lalu tentukan basisnya di sebagai ruang vektor atas Z5. Adapun basis dari polinomial primitifnya yaitu {1, α1, α2, …, αm-1}. Sehingga (5 ) = { . 1 + } . Kemudian | , ,…, +⋯ ∈ (5) ) ( semua unsur dari 5 direpresentasikan ke dalam bentuk ruang vektor berdimensi m atas . Algoritme hasil konstruksi terdiri atas Algoritme Penjumlahan, Algoritme Perkalian, Algoritme Invers, Algoritme Pembagian, dan Algoritme Eksponensial. Dari hasil penelitian yang telah dilakukan diperoleh kesimpulan : 1) Finite (5) dikonstruksi dari polinomial primitif. Untuk mengkonstruksi field algoritme aritmetik (5 ) dipilih polinomial primitif yang bersuku terkecil, hal ini akan mengakibatkan proses komputasi yang dijalankan lebih cepat dibandingkan dengan menggunakan polinomial primitif biasa. 2) Algoritme Reduksi Nol digunakan untuk mengurangi jumlah operasi pada sebuah algoritme. Algoritme ini digunakan pada Algoritme Penjumlahan, Algoritme Penjumlahan digunakan dalam Algoritme Perkalian, Algoritme Penjumlahan dan Algoritme Perkalian digunakan dalam Algoritme Invers, dan seterusnya. 3) Algoritme Geser Satu mampu mempercepat proses kerja suatu algoritme, karena pada algoritme ini hanya mengubah strukturnya saja dan menggeser bersifat konstan. Algoritme ini digunakan pada Algoritme Perkalian, Algoritme Perkalian digunakan dalam Algoritme Invers, dan seterusnya. 4) Algoritme aritmetik hasil konstruksi tidak membutuhkan ruang yang besar sehingga cukup cepat dalam komputasinya karena yang dipakai sebagai modulo digunakan polinomial primitif bersuku terkecil, melakukan reduksi nol yang berfungsi mengurangi jumlah operasi dalam algoritme, dan operasi geser satu. Kata kunci : algoritme, grup siklik, kriptografi.
(5 ), akar primitif, polinomial primitif,
©Hak cipta milik IPB, tahun 2009 Hak cipta dilindungi Undang-undang 1. Dilarang mengutip sebagian atau seluruh karya tulis ini tanpa mencantumkan atau menyebut sumber. a. Pengutipan hanya untuk kepentingan pendidikan, penelitian, penulisan karya ilmiah, penyusunan laporan, penulisan kritik atau tinjauan suatu masalah. b. Pengutipan tidak merugikan kepentingan yang wajar IPB. 2. Dilarang mengumumkan dan memperbanyak sebagian atau seluruh karya tulis dalam bentuk apapun tanpa izin IPB.
( KONSTRUKSI ALGORITME ARITMETIK DENGAN OPERASI DIBANGKITKAN DARI SIFAT GRUP SIKLIK
AHMADI
Tesis sebagai salah satu syarat untuk memperoleh gelar Magister Sains pada Departemen Matematika
SEKOLAH PASCASARJANA INSTITUT PERTANIAN BOGOR BOGOR 2009
)
Judul Tesis : Konstruksi Algoritme Aritmetik Dibangkitkan Dari Sifat Grup siklik Nama : Ahmadi NRP : G551070691
(5 ) Dengan
Operasi
Disetujui Komisi Pembimbing
Dra. Nur Aliatiningtyas, M.Si Anggota
Dr.Sugi Guritman. Ketua
Diketahui
Ketua Program Studi Matematika Terapan
Dekan Sekolah Pascasarjana
Dr. Ir. Endar H. Nugrahani, M.S.
Prof. Dr. Ir. Khairil A. Notodiputro, M.S.
Tanggal Ujian : 20 Agusutus 2009
Tanggal Lulus :
PRAKATA
Segala puji dan syukur penulis panjatkan kehadirat Allah SWT yang telah memberikan segala rahmat dan karunia-Nya, sehingga penulis dapat (5 ) menyelesaikan tesis yang berjudul “Konstruksi Algoritme Aritmetik Dengan Operasi Yang Dibangkitkan Dari Sifat Grup siklik”. Penulis menyadari bahwa dalam penyusunan tesis ini masih banyak terdapat kekurangan, hal ini karena peengetahuan yang dimiliki oleh penulis sangat terbatas. Dalam kesempatan ini penulis mengucapkan terimakasih yang sebesarbesarnya kepada yang terhormat 1. Bapak Dr. Sugi Guritman dan Ibu Dra. Nur Aliatiningtyas, MS selaku pembimbing, pendidik dan pengajar yang dengan penuh kesabaran memberikan bimbingan, arahan, nasehat serta motivasi kepada penulis. 2. Bapak Drs. Prapto Tri Supriyo, M.Kom. selaku penguji, pendidik dan pengajar yang telah memberikan saran dan kritikannya kepada penulis. 3. Departemaen Agama RI yang telah memberikan beasiswa kepada penulis untuk melanjutkan Sekolah Pascasarjana pada Institut Pertanian Bogor periode 2007 s.d 2009. 4. Ketua Departemen, ketua Program Studi, dan seluruh staf pengajar serta staf administrasi Fakultas Matematika dan Ilmu Pengetahuan Alam yang turut membantu proses penyelesaian tesis. 5. Kepala sekolah dan seluruh staf pengajar MTs At-Taqwa Gembongdadi yang turut mendoakan dan memotivasi penulis dalam menyelesaikan tesis ini. 6. Istri dan kedua orang tua yang senantiasa mendoakan penulis disetiap waktu dalam menyelesaikan tesis. 7. Seluruh teman-teman yang turut membantu penyelesaian tesis. Penulis doakan semoga segala bantuan, bimbingan dan pengarahan yang diberikan mendapat ganjaran yang berlipat ganda dari Allah SWT, dan semoga tesis ini bermanfaat bagi kita semua. Amin. Bogor, Agustus 2009 Ahmadi
RIWAYAT HIDUP
Penulis dilahirkan di Tegal pada tanggal 09 Januari 1980 dari ayah Kholil dan ibu Muninggar. Penulis merupakan putra kelima dari delapan bersaudara. Pendidikan dasar ditempuh di SD Negeri Karangjati 01 – Tarub - Tegal lulus tahun 1993, MTs. Hasyim Ay’ari Tarub lulus tahun 1996. Pendidikan atas ditempuh di SMA Hasyim Ay’ari Tarub lulus tahun 1999. Pendidikan sarjana ditempuh di Jurusan Pendidikan Matematika, Fakultas Keguruan dan Ilmu Pendidikan Universitas Pancasakti Tegal lulus tahun 2005. Setelah lulus pendidikan sarjana, penulis menjadi staf pengajar di MTs. AtTaqwa Gembongdadi sebagai guru honorer sampai dengan sekarang. Pada tahun 2007 penulis mendapat kesempatan untuk melanjutkan sekolah ke jenjang yang lebih tinggi yakni Program Magister. Penulis melanjutkan belajar Program Magister pada program studi Matematika Terapan Sekolah Pascasarjana Institut Pertanian Bogor melalui beasiswa BUD Departemen Agama Republik Indonesia.
Penguji Luar Komisi pada Ujian Tesis : Drs. Prapto Tri Supriyo, M.Kom.
DAFTAR ISI DAFTAR TABEL …………………………………………………………..... xii DAFTAR GAMBAR …………………………………………………...…… xiii DAFTAR ALGORITME ……………………………………………………. xiv DAFTAR LAMPIRAN ……………………………………………………… xv BAB I
BAB II
BAB III
PENDAHULUAN ……………………………………………..
1
1.1
Latar Belakang ………………………………………….. 1
1.2
Tujuan Penelitian ……………………………………….. 3
1.3
Manfaat Penelitian ……………………………………… 3
TINJAUAN PUSTAKA ………………………………………... 4 2.1
Teori Grup ……………………………………………….. 4
2.2
Grup Siklik ………………………………………………. 6
2.3
Grup Homomorfisme Dan Isomorphisme ………………. 6
2.4
Ring ………………………………….………………….. 7
2.5
Ring Polinomial …………..……………………………... 9
2.6
Perluasan Field ………………………………………….. 10
PEMBAHASAN TEOREMA DAN LEMMA YANG DIBUTUHKAN DALAM KONSTRUKSI ARITMETIK GF(5m) ………………………………………….. 14 3.1
BAB IV
BAB V
Polinomial Minimum ………….………………………… 18
KONSTRUKSI ALGORITME ARITMETIK GF(5m) ………...
25
4.1
Penjumlahan Polinomial …………….………………….. 28
4.2
Perkalian Polinomial …………………………….……… 30
4.3
Invers Polinomial …..……………………………………. 33
4.4
Pembagian Polinomial ………………………………….. 36
4.5
Eksponen Polinomial …………………………………… 37
KESIMPULAN DAN SARAN ……………………………….
39
5.1
Kesimpulan ……………..….…………………………… 39
5.2
Saran ………………………………..…………………..
39
DAFTAR PUSTAKA ………………………………………………………..
40
LAMPIRAN ………………………………………………………………….
41
DAFTAR TABEL
Halaman (5)…………….……………………………….. 1. Finite Field 2. Representasi Finite Field (5)………………………………..
17 26
DAFTAR ALGORITME Halaman 4.1
Pengetesan Polinomial Irredusibel
27
4.2
Pengetesan Polinomial Primitif
28
4.3
Penjumlahan Polinomial
29
4.4
Reduksi Nol
30
4.5
Kelipatan Vektor
30
4.6
Geser Satu
31
4.7
Perkalian Polinomial
32
4.8
Negasi Vektor
33
4.9
Pembagian Polinomial Tanpa Modulo m
34
4.10 Invers Polinomial
35
4.11 Pembagian Polinomial
37
4.12 Eksponen Polinomial
37
4.13 Modulus Bilangan Negatif
38
DAFTAR GAMBAR Halaman 1. Perluasan Field F (5 ) 2. Subfield dari
11 21
DAFTAR LAMPIRAN 1. Polinomial Primitif di dalam
(5)………………………………
41
BAB I PENDAHULUAN 1.1
Latar Belakang Masalah keamanan merupakan salah satu aspek penting dari sebuah sistem
informasi. Untuk menjamin keamanan sebuah informasi yang bersifat rahasia diperlukan suatu teknik pengamanan baik secara fisik maupun non fisik. Salah satu teknik pengamanan secara non fisik yaitu dengan mengenkripsi informasi rahasia menggunakan teknik kriptografi. Kriptografi secara terminologi dasarnya terdiri dari dua tipe yaitu kriptografi
simetrik dan kriptografi asimetrik atau sering disebut sebagai
kriptografi kunci publik. Kunci simetris adalah jenis kriptografi yang paling umum digunakan. Kunci untuk membuat pesan yang disandikan sama dengan kunci untuk membuka pesan yang disandikan itu. Jadi pembuat pesan dan penerimanya harus memiliki kunci yang sama persis. Siapapun yang memiliki kunci tersebut termasuk pihak-pihak yang tidak diinginkan dapat membuat dan membongkar rahasia ciphertext. Contoh algoritme kunci simetris yang terkenal adalah DES (Data Encryption Standard). Karya ini menjadi alat keamanan komersial elektronik di banyak institusi keuangan di seluruh dunia hingga pertengahan tahun 1990-an. DES secara DES tak aman sejak juli 1998. Walaupun demikian DES telah melandasi prinsip-prinsip sandi simetrik modern yang dewasa ini muncul produk-produk penggantinya seperti : AES (Advanced Encryption Standard), Blowfish, 3DES, RC5, dan lain sebagainya. Kunci asimetrik merupakan pasangan kunci kriptografi yang salah satunya digunakan untuk proses enkripsi dan yang satu lagi untuk dekripsi. Semua orang yang mendapatkan kunci publik dapat menggunakannya untuk mengenkripsikan suatu pesan,data ataupun informasi, sedangkan hanya satu orang saja yang memiliki rahasia tertentu dalam hal ini kunci privat untuk melakukan pembongkaran terhadap sandi yang dikirim untuknya. Pada algoritme kunci publik ini, semua orang dapat mengenkripsi data dengan memakai kunci publik penerima yang telah diketahui secara umum. Akan tetapi data yang telah terenkripsi tersebut hanya dapat didekripsi dengan menggunakan kunci privat
2 yang hanya diketahui oleh penerima. Contoh algoritme terkenal yang menggunakan kunci asimetrik adalah skema RSA yang ditemukan oleh Rivest, Shamir, dan Adleman pada tahun 1978. Skema ini didasarkan pada problem matematika yang sulit, yaitu pemecahan masalah faktorisasi integer besar. Bentuk praktis skema kunci publik lainnya ditemukan oleh ElGamal pada tahun 1985. Skema ini didasarkan pada pemecahan problem logaritma diskret. Keamanan algoritme ini sangat tergantung pada pemilihan bilangan prima p. Semakin besar p maka algoritme ini akan semakin aman, akan tetapi semakin besar pula beban komputasi yang digunakan. Oleh karena itu pada masa sekarang, orang sudah mulai mencari alternatif lain untuk menggantikan aritmetik modular diantaranya aritmetik yang dibangkitkan struktur finite field
, kurva eliptik kriptografi,
dan hipereliptik kriptografi. 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. Sebenarnya sudah banyak sekali penelitian tentang
yang pernah
dilakukan, diantaranya adalah paper berjudul ”Montgomery Multiplication in GF(2k)” menunjukkan operasi perkalian r adalah unsur tetap dari field
dalam field GF(2k) dimana
dapat diimplementasikan lebih cepat dalam
perangkat lunak dibandingkan dengan operasi perkalian standar (Koc, 1998), paper berjudul ”Analysis and Construction of Galois Field for Efficient Storage Reliability” juga menganalisis adanya implementasi berdasarkan tabel dan teknik optimasi operasi perkalian dan pembagian dalam thesis berjudul ”Konstruksi Algoritme Aritmetik
(Greenan, 2007), dan Dengan Operasi
Perkalian Dibangkitkan Dari Sifat Grup Siklik” menyebutkan bahwa algoritme aritmetik hasil konstruksi cukup cepat dalam perhitungan komputasinya (Rosdiana, 2009).
3 Dalam thesis ini peneliti mencoba mengkonstruksi aritmetik yang berbeda dan dengan pendekatan yang sama dari
dari sebelumnya yaitu aritmetik
konstruksi yang telah dilakukan oleh Sri Rosdiana (2009) yaitu mendefinisikan didasarkan pada sifat bahwa
sekaligus mengkonstruksi
merupakan grup siklik yang dibangkitkan dari akar primitif. 1.2
Tujuan Penelitian Penelitian ini bertujuan mengkonstruksi finite field
dengan
memperhatikan segi kecepatan yang didasarkan pada sifat-sifat grup siklik. 1.3. Manfaat Penelitian Manfaat dari penelitian ini adalah sebagai algoritme aritmetik alternatif yang dapat digunakan pada algoritme-algoritme kriptografi yang selanjutnya dapat
digunakan
secara
luas
pada
bidang
teknologi
informasi.
4
BAB II TINJAUAN PUSTAKA Untuk mencapai tujuan penulisan penelitian diperlukan beberapa pengertian dan teori yang berkaitan dengan pembahasan. Dalam subbab ini akan diberikan beberapa teori berupa definisi, lemma, dan teorema yang berkaitan dengan pembahasan. 2.1. Teori Grup Definisi 2.1. Struktur aljabar
tertutup terhadap operasi biner disebut
grup jika memenuhi aksioma-aksioma berikut: a) Operasi biner
bersifat asosiatif: a b c a b c , untuk setiap
a, b, c G . b) Terdapat unsur identitas e G , untuk * pada G sehingga berlaku a e e a a untuk setiap a G . c) Untuk setiap a G ada unsur a 1 G sehingga a a 1 a 1 a e . ( a-1 disebut invers a terhadap operasi *). Grup G disebut grup komutatif atau grup abelian jika operasi * bersifat komutatif yaitu: a b b a , untuk semua a, b G . Grup berhingga yaitu grup yang kardinalitasnya berhingga. Dalam hal ini kardinalitas suatu grup G disebut dengan order dari G, dinotasikan ord G atau
O G atau G . Definisi 2.2. Jika H himpunan bagian atas grup G adalah grup di bawah operasi G, maka H subgrup dari G. Teorema 2.3. (Uji satu langkah) Misalkan G grup dan H himpunan bagian yang tak kosong atas G. Maka H adalah subgrup atas G jika H tertutup di bawah operasi pembagian; yaitu jika
bilamana
5 Teorema 2.4. (Uji dua langkah) Misalkan G grup dan H himpunan bagian tak kosong atas G. Maka, H disebut subgrup dari G jika (tertutup terhadap perkalian), dan
bilamana
bilamana
(tertutup terhadap
invers) Sebagai contoh, Z dan Q merupakan subgrup dari R terhadap operasi +. Tentu saja Z Q R dan masing-masing merupakan grup terhadap operasi yang sama yaitu +. Misal G sembarang grup, a G , dan n bilangan bulat positif, maka: a n : aa ...a , n kali
1 1 a n : a a ... a1 , n kali
n -1
= (a )
dan a0 : e . Jika ada bilangan bulat tidak nol m sedemikian sehingga a m e , maka order dari unsur a, notasi O a , didefinisikan sebagai bilangan bulat positif terkecil n sedemikian sehingga a n e . Jika tidak ada bilangan bulat tidak nol n sedemikian sehingga a n e , maka dikatakan a mempunyai order di tak hingga (infinity). Ringkasan 2.5. Berikut ini 3 sifat dasar yang berkaitan dengan pengertian order. 1. Jika O a n , maka ada tepat n kuasa dari a (power of a) yang masingmasing berbeda, yaitu a 0 e, a, a 2 ,..., a n 1 . 2. Jika O a tak hingga, maka semua kuasa dari a berbeda. Artinya, jika r dan s yaitu dua bilangan bulat yang berbeda, maka a r a s . 3. Misalkan a yaitu unsur dari grup G dan O a n . Maka a t e jika dan hanya jika t yaitu kelipatan dari n (t kelipatan n artinya ada bilangan bulat q sehingga t=nq). Definisi 2.6. Misalkan H subgrup dari
grup G.
Himpunan
atas G disebut koset kiri atas H memuat himpunan bagian
bagian . Sedangkan
atas G disebut koset kanan atas H memuat .
6 Teorema 2.7. (Teorema Lagrange) Misalkan H subgrup dari grup berhingga G. Maka order dari H adalah pembagi dari order G. Teorema 2.8. Order dari unsur grup berhingga G membagi order G. Jika H merupakan subgrup dari grup G, indeks dari H di dalam G diartikan sebagai
jumlah
koset
sedangkan G : H
dari
H
di
dalam
G,
notasinya
G : H .
G H
2.2. Grup Siklik Grup G disebut siklik jika dan hanya jika ada unsur a G (a disebut generator) sehingga
G a an n Z .
Dalam kasus G grup aditif, dapat ditulis G a na n Z .
Ringkasan 2.9. (Sifat-sifat Grup Siklik) 1. Jika grup G berorder n, maka G siklik jika dan hanya jika ada a G sehingga
O a n . 2. Setiap grup siklik yaitu abelian. 3. Setiap subgrup dari grup siklik adalah siklik. 4. Jika G a dan b G , maka O b O a . 5. Jika G yaitu grup siklik berorder n dan suatu bilangan bulat k n , maka ada b G sehingga O b k .
6. Misalkan G yaitu grup abelian berorder mn dengan m dan n prima relatif. Jika G mempunyai suatu unsur a dengan O a m dan b dengan O b n , maka G yaitu grup siklik dengan G ab . 7. a r yaitu generator dari G a dengan G n jika dan hanya jika r dan n prima relatif. 2.3. Grup Homomorfisme dan Isomorphisme
7 Misal G dan H grup. Suatu homomorfisma (grup) dari G ke H yaitu suatu fungsi f : G H sedemikian sehingga untuk sembarang a dan b di dalam G,
f ab f a f b . Bayangan (Imej) dari f, dinotasikan Im f , yaitu Im f f G f x x G .
Kernel dari f, dinotasikan ker f , yaitu
ker f x G f x e (secara implisit e yaitu unsur identitas dari f).
Sifat-sifat dasar homomorfisma dinyatakan dalam Ringkasan berikut ini. Ringkasan 2.10. (Sifat-sifat Dasar Homomorfisma) Misalkan G dan H yaitu grup, f : G H homomorfisma, maka sifat-sifat berikut dipenuhi. 1.
f e e . untuk setiap a G .
2.
3. Im f merupakan subgrup dari H. 4. ker f merupakan subgrup dari G. Jika
homomorfisme yang bijektif, maka f disebut isomorfisme.
2.4. Ring Struktur aljabar dengan dua operasi biner yang paling umum yaitu Ring. Definisi 2.11. Ring R adalah himpunan dengan dua operasi + dan x (disebut dengan penjumlahan dan perkalian) yang memenuhi aksioma-aksioma berikut: a.
R, adalah grup abelian adalah asosiatif :
untuk setiap a, b, c R .
b.
Operasi
c.
Berlaku hukum distributif atas R : Untuk setiap a, b, c R memenuhi dan
8 Ring R disebut komutatif jika perkaliannya bersifat komutatif. Ring R disebut mempunyai
unsur
kesatuan
Definisi 2.12. Unsur bukan nol ada unsur bukan nol
jika
terdapat
dengan
unsur
dari Ring komutatif R disebut pembagi nol jika
sehingga
Definisi 2.13. Ring komutatif dengan unsur kesatuan
disebut daerah integral
jika tidak memuat pembagi nol Definisi 2.14. Karakteristik Ring R adalah sekurang-kurangnya integer positif sehingga
untuk setiap
. Jika tidak ada, R disebut berkarakteristik 0.
Teorema 2.15. Karakteristik daerah integral adalah 0 atau prima. Teorema 2.16. Di dalam sembarang Daerah Integral D dengan karakteristik p,
a b
p
a p b p untuk semua unsur a, b D .
Definisi 2.17. Field adalah suatu Ring komutatif, ada unsur kesatuan 1 dan setiap unsur tak nolnya mempunyai invers (multiplikatif) Teorema 2.18. Daerah integral yang berhingga adalah field. Akibat 2.19. Untuk setiap bilangan prima p, Ring Zp integer modulo p, adalah field Definisi 2.20. SubRing A dari Ring R disebut ideal dari R jika untuk setiap dan setiap
,
dan
.
Teorema 2.21. Misal R Ring, I R , I tidak kosong. Himpunan bagian I disebut ideal jika memenuhi: a. b.
dan
dan
.
Untuk setiap Ring R, {0} dan R adalah ideal atas R. Ideal {0} disebut ideal trivial. Misalkan R Ring komutatif dengan unsur kesatuan 1 dan
. Suatu himpunan
merupakan ideal. Ideal yang demikian disebut ideal utama yang dibangun oleh .
9 Definisi 2.22. Suatu ideal I atas Ring komutatif R disebut ideal prima atas R jika dan
sehingga
dan
. Suatu ideal B atas Ring komutatif R
disebut ideal maksimal atas R jika B adalah ideal atas R dan
maka
B = A atau B = R. Misalkan Ring R dan I merupakan ideal dari R. Karena R merupakan grup terhadap penjumlahan dan I subgrup dari R, maka Ring faktor sebagai
dapat ditulis
.
Teorema 2.23. Misal R Ring komutatif dengan unsur kesatuan 1. I ideal maksimal dari R. Maka R
I
adalah field jika dan hanya jika I ideal maksimal.
Definisi 2.24. Suatu homomorfisma dari Ring R ke Ring R ' yaitu suatu fungsi f : R R ' yang memenuhi,
berlaku :
a.
f a b f a f b , dan
b.
f ab f a f b .
Jika f surjektif, maka R ' disebut bayangan homomorfik dari R. Kernel dari f diDefinisikan
ker f x R f x 0 , dan range dari f diDefinisikan ran f f x x R .
Jika f homomorfisma yang bijektif, maka f disebut isomorfisma. Dalam hal ini R dan R ' dikatakan isomorfik, dinotasikan Teorema
2.25.
Misal
f : R R'
Ring
homomorfisma.
Maka
ker f x R f x 0 merupakan ideal dari R. Teorema 2.26. R I merupakan bayangan homomorfik dari R. Teorema 2.27. (Teorema dasar homomorfisme) Misalkan merupakan epimorfisme, dan misalkan K yaitu kernel dari f. Maka
f : R R' .
10
2.5. Ring Polinomial Misalkan R Ring komutatif dengan unsur kesatuan, dan x simbol yang tak disebut
tetap. Setiap ekspresi berbentuk polinomial dalam x dengan
. Polinomial dalam x dapat ditulis dengan
dan
lain-lain.
Misal merupakan
polinomial, derajat dari polinomial koefisien dari
yaitu bilangan terbesar n sehingga
bukan nol dan dinotasikan dengan deg
Polinomial
.
yang semua koefisiennya nol
disebut polinomial nol, dan dinotasikan dengan maka
sembarang
Jika polinomial
berderajat nol dan disebut polinomial konstan. Misalkan dan . Operasi penjumlahan dan
perkalian polinomial didefinisikan sebagai berikut :
Dimana
Dimana, Jika R Ring, maka
, untuk k = 0, …, m+n menotasikan himpunan semua polinomial dalam x yang
koefisiennya ada di R dengan operasi penjumlahan dan perkalian seperti yang didefinisikan sebelumnya. Teorema 2.28. Misal R Ring komutatif dengan unsur kesatuan 1. Maka R[x] merupakan Ring komutatif dengan unsur kesatuan 1. Teorema 2.29. Jika R adalah daerah integral, maka R[x] adalah daerah integral.
11 Definisi 2.30. Suatu polinomial
irredusibel atas F bila f(x) tidak dapat
dinyatakan sebagai perkalian
dimana
keduanya
berderajat lebih rendah dari f(x). Teorema 2.31. Misal F field dan Ring polinomial F x . Jika f x , g ( x) F x dengan g x 0 , maka ada polinomial unik q x , r ( x) F x sehingga
f ( x) q x g x r x dengan r x 0 atau derajat r x derajat g x . Teorema 2.32. Misal F field, I ideal tak nol di F[x], dan unsur jika dan hanya jika
Ideal
merupakan polinomial tak nol berderajat
terendah di I. Teorema 2.33. Semua ideal dari
merupakan ideal utama
Teorema 2.34. Misal F field dan hanya jika
.
ideal maksimal jika dan
irredusibel atas F.
Teorema 2.35.
ideal maksimal jika dan hanya jika
field.
2.6. Perluasan Field Definisi 2.36. Jika E field yang memuat subfield F, maka E disebut perluasan field dari F. Definisi 2.37. Misal E perluasan field dari field F dan c E . c disebut algebraic atas F jika f c 0 untuk f x F x yang tak nol.
F
E
c
Gambar 1. Perluasan Field F Definisi 2.38. Misal E perluasan field dari field F dan c E algebraic atas F. Polinomial monik p x merupakan polinomial irredusibel dengan akar c atas F
12 dinotasikan dengan irr c, F dan derajat dari polinomial irredusibel dengan akar c atas F dinotasikan dengan deg c, F Teorema 2.39. Misal F subfield dari field E, c E (indeterminate).
c : F x E
Pemetaan
yang
dan x tak tentu
diDefinisikan
dengan
c f x f c dimana f x a0 a1 x ... an x n , f x F x merupakan homomorfisma. Homomorfisma c disebut homomorfisma evaluasi dan berlaku
c x c serta c a a , a F . Kernel atas homomorfisma sehingga
merupakan himpunan semua polinomial . Jadi, kernel
berisi semua polinomial
sehingga c merupakan akar dari dinotasikan sebagai
. Misalkan kernel
, menurut Teorema 2.25 kernel untuk setiap homomorfisma
merupakan ideal, sehingga
merupakan ideal dari F[x]. Menurut Teorema 2.33
setiap ideal dari F[x] merupakan ideal utama. Karena dan berdasarkan Teorema 2.32, dengan
,
polinomial berderajat terendah. Dengan Definisi 2.30 mudah untuk
membuktikan bahwa
merupakan polinomial irredusibel. Misalkan
Sehingga dimana
merupakan ideal utama
,
. Hal ini tidaklah mungkin, karena
merupakan
polinomial berderajat terendah di dalam
. Sehingga
merupakan
polinomial berderajat lebih tinggi dari
Maka menurut Definisi 2.30,
merupakan polinomial irredusibel. Karena setiap konstanta pengali dari di
maka
monik. Sehingga dapat disimpulkan bahwa
polinomial minimum dari c atas F. Lalu bagaimana dengan Range dari
?
ada
merupakan
13 Range
Dari penjelasan di atas diperoleh dengan
merupakan epimorfisme,
polinomial irredusibel. Dengan menggunakan Teorema
dasar homomorfisme, maka
. Menurut Teorema 2.34, jika
polinomial irredusibel maka
merupakan ideal maksimal. Dan
berdasarkan Teorema 2.35 dapat disimpulkan bahwa field. Karena
maka
merupakan
juga merupakan field.
Teorema 2.40. Misal F field dan p x polinomial tak konstan di F x . Ada suatu perluasan field E dari F dan unsur c di E sehingga c akar dari p x . Definisi 2.41 V himpunan, F field, operasi di V yaitu penjumlahan dan perkalian skalar. V disebut ruang vektor atas F jika memenuhi aksioma berikut: 1. Untuk setiap a , b V terdapat tunggal c V sehingga tertutup terhadap penjumlahan: a b c . 2. Untuk setiap a , b , c V bersifat asosiatif: a b c a b c .
3.
4.
5.
Terdapat tunggal identitas 0 V , untuk setiap a 0 0a a . Untuk setiap a V terdapat tunggal invers a b b a 0 , b a . Untuk setiap a , b V bersifat komutatif: a b b a .
a V
sehingga
b V
sehingga
7.
Untuk setiap k F dan setiap a V terdapat tunggal b V sehingga tertutup terhadap perkalian: ka b . Untuk setiap k F dan setiap a , b V , k a b ka kb .
8.
Untuk setiap k , l F dan setiap a V , k l a ka la .
9.
Untuk setiap k , l F dan setiap a V , kl a k la .
6.
14 10.
Untuk setiap a V , 1a a ; 1 unsur identitas di F , .
Definisi 2.42. Misal E perluasan field dari field F. Jika E ruang vektor atas F berdimensi hingga n, maka E disebut perluasan hingga berderajat n atas F. Derajat E atas F sama dengan n dinotasikan E : F n . Definisi 2.43. Jika field E dibangun oleh unsur satu c atas field F: E F c , maka E disebut perluasan tunggal dari F dan unsur c disebut unsur primitif atau akar primitif untuk perluasan.
E F c dengan
Teorema 2.44. Misal
cE
algebraic atas F, dan
deg c, F n , n 1 . Setiap unsur dari E F c dapat dinyatakan secara unik dalam bentuk b0 b1c1 ... bn 1c n 1 , dimana bi F x . Teorema 2.45. Derajat dari
atas F sama dengan derajat dari polinomial
minimum dari c atas F. Sebagai contoh, i merupakan akar dari polinomial irredusibel R[x].
mempunyai derajat 2, menurut Teorema 2.44,
atas dengan
basisnya {1, i}. Setiap unsur dalam R[i] merupakan kombinasi linear dari 1 dan i yang
berbentuk
dimana
dan
dinotasikan
dengan
. Teorema 2.46. Misalkan berderajat m, maka
merupakan polinomial irredusibel adalah finite field berderajat
. Operasi
penjumlahan polinomial dan operasi perkalian polinomial dilakukan dalam modulo
.
Teorema 2.47. Misal E perluasan field dari field F dan c E algebraic atas F. Jika deg c, F n , maka F c ruang vektor atas F berdimensi-n dengan basis
1, c, c ..., c . 2
n 1
15 Lemma 2.48. Misal
basis dari ruang vektor K atas F dan
basis dari ruang vektor E atas K. Maka himpunan perkalian merupakan basis dari ruang vektor E atas field F.
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
BAB IV ( )
KONSTRUKSI ALGORITME ARITMETIK
(5) dapat
Seperti yang telah dijelaskan dalam Bab III, bahwa
direpresentasikan ke dalam bentuk polinomial dan vektor. Demi kemudahan
komputasi dalam tesis ini digunakan representasi vector. Berikut ini diberikan ilustrasi operasi penjumlahan dengan representasi vektor. Misalkan diberikan vektor ( )=
+2 +3
( ) = 2+2 +
(0 + 2)
dan
+3 +
vektor
=(0, 1, 2, 3) sebagai representasi dari
=(2, 2, 3, 1) sebagai reprentasi dari
(5), maka
dalam
=(0, 1, 2, 3) + (2, 2, 3, 1) = (5,1 + 2)
(5,2 + 3)
(5,3 + 1)
5
= (2, 3, 0,. 4)
Untuk mengkonstruksi aritmetik GF (5m) dalam penelitian ini langkah
pertamanya adalah dengan memilih polinomial primitif berderajat m atas Z5, misal
( ) ∈ [ ] dimana
( )=
+
+ ⋯+
sehingga diperoleh
unsur primitif α dengan M(α) = 0. Kemudian, tentukan basis dari GF(5m) sebagai ruang
vektor
atas Z5, yaitu {1, α1, α2, …, αm-1}. Dengan demikian, diperoleh (5 ) = {
himpunan
Kemudian semua unsur dari vektor berdimensi m atas
+
|
+⋯
,
,…,
}. (5)
∈
(5 ) direpresentasikan ke dalam bentuk ruang
. Tabel berikut ini menunjukkan adanya hubungan
antara representasi elemen primitif, representasi basis polinomial, representasi vektor penta, dan representasi integer dalam (5 ) yang dibangun oleh polinomial primitif
( )= +
+2
Tabel 2. Representasi finite field
No. 1
Elemen primitif 0
()
Representasi Basis
Vektor penta
Integer
0
(0, 0)
0
26
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
=1
1
(1, 0)
1
(0, 1)
5
3+4
(3, 4)
23
2+4
(2, 4)
22
2+3
(2, 3)
17
4+4
(4, 4)
24
2
(2, 0)
2
2
(0, 2)
10
1+3
(1, 3)
16
4+3
(4, 3)
19
4+
(4, 1)
9
3+3
(3, 3)
18
4
(4, 0)
4
4
(0, 4)
20
2+
(2, 1)
7
3+
(3, 1)
8
3+2
(3, 2)
13
1+
(1, 1)
6
3
(3, 0)
3
3
(0, 3)
15
4+2
(4, 2)
14
1+2
(1, 2)
11
1+4
(1, 4)
21
2+2
(2, 2)
12
Bagaimana memilih polinomial primitif? Sebagaimana telah dijelaskan sebelumnya, polynomial primitif adalah polinomial irredusibel yang akarnya adalah generator dari GF(5)*. Oleh karena itu, diperlukan pemilihan polinomial
27
irredusibel terlebih dahulu. Sesuai dengan Teorema 3.14, diperoleh Algoritme pengetesan polinomial irredusibel sebagai berikut : Algoritme 4.1. Pengetesan polinomial irredusibel Deskripsi : Mengetes Vektor Apakah Irredusibel atau Redusibel Input
: Vektor A
Output
: True atau False = ( /2)dibulatkan ke bawah
1.
a = banyaknya unsur A – 1,
2.
W = [0, 1]
3.
Untuk I dari 1 sampai m, lakukan secara berulang : 3.1. W = W pangkat 5 modulo A 3.2. U= Jumlahkan W dengan [0, 4] menggunakan algoritme 4.4 3.3. H = FPB(U,A) 3.4. h = banyaknya unsur H 3.5. jika h > 1, maka return(false)
4.
Return (True)
Setelah kita mendapatkan polinomial irredusibel, kemudian memeriksa apakah polinomial irredusibel yang didapatkan tersebut merupakan polinomial primitif atau bukan. Untuk memeriksa polinomial irredusibel adalah primitif, digunakan Algoritme 4.2. Berdasarkan Teorema 3.15 diperoleh Algoritme 4.2 sebagai berikut :
28
Algoritme 4.2. Pengetesan polinomial primitif Deskripsi : Mengetes Vektor Irredusibel Apakah Primitif atau Bukan Input
: Vektor A
Output
: True atau False 1.
m = banyaknya unsur A – 1, h = 5m – 1
2.
F = faktorkan h
3.
a = banyaknya unsur F
4.
Untuk i dari 1 sampai a, lakukan secara berulang 4.1. k = h/i 4.2. H = [0, 1] pangkat k modulo A 4.3. Jika H = [1], maka return(false)
5.
Return(True)
Untuk mempercepat komputasi, dipilih polinomial primitif yang bersuku (5)
terkecil. Hal ini sangatlah beralasan, sebab operasi pada finite field
dilakukan dalam modulo f(x), dimana f(x) merupakan polinomial primitif. Dengan memilih polinomial primitif
bersuku terkecil akan mengakibatkan proses
komputasi yang dijalankan lebih cepat dibandingkan dengan menggunakan polinomial primitif biasa. Adapun polinomial primitif
yang sudah diperoleh
dapat dilihat di Lampiran I. 4.1
Penjumlahan Polinomial Seperti telah dijelaskan di atas, solusi yang digunakan di sini dengan
menggunakan representasi vektor penta. Misal diberikan dua sembarang fungsi polinomial
( )=
+
+⋯
dan
( )=
maka bentuk field penjumlahannya adalah sebagai berikut : Fungsi =[ , =[ ,
( )+ ( ) =(
polinomial ,…,
,…,
],
a(x)
+
sedangkan
)+(
+
)
direpresentasikan fungsi
+ ⋯ +(
sebagai
polinomial b(x)
+ +
+⋯ )
vektor
penta
sebagai
vektor
]. Operasi penjumlahan yang digunakan di sini yaitu instruksi
29
xor. Sebagai contoh, diberikan sembarang fungsi polinomial 2
+4
( ):
( ):
( )=2+
dan = [3, 2, 2, 0, 4]
( ) = 3+2
+
. Maka bentuk representasi vektor penta
dan
bentuk
representasi vektor
penta
= [2, 0, 0, 0, 1]. Untuk menghemat pemakaian ruang yang besar dalam
komputasi, maka dilakukan reduksi nol pada vektor A atau B. Pada contoh di atas,
vektor A dan vektor B memiliki elemen yang sama, maka penjumlahannya sebagai berikut : C = A+B = [(3+2) mod 5, (2+0) mod 5, (2+0) mod 5, (0+0) mod 5, (4+1) mod 5] = [0, 2, 2, 0, 0]. Setelah diperoleh Vektor C,
kemudian
dilakukan
reduksi nol sehingga :
= [0, 2, 2].
Algoritme 4.3. Penjumlahan polinomial Deskripsi : Menambahkan vektor A dan B dalam modulo 5 Input
=[
: Vektor
,
,…,
,…,
]
intejer positif m Output
: Vektor
=[ ,
],
1.
Tentukan vektor A, dan vektor B
2.
Jika
3.
Jika B= [0], maka C = A
4.
=[ ,
vektor
,…,
], dan
=[0], maka C = B
Jika s=t, maka 4.1. )
={[(
+
}5]
)
5, ( +
)
5, … , ( +
4.2. Lakukan reduksi nol dengan menggunakan algoritme 4.4 5.
Jika s < t, maka 5.1.
={[(
Lainnya 6.
Return (C)
+
= {[(
)
+
)
5, ( +
5, (
)
+
)
5, … ,
5, … ,
]}5
5]}
Pembentukan Algoritme 4.3. ini didasarkan pada Teorema 2.45. Keistimewaan Algoritme ini adalah pada setiap melakukan operasi selalu melibatkan Algoritme Reduksi Nol. Algoritme Reduksi Nol dapat mengurangi
30
jumlah operasi pada konstruksi algoritme-algoritme aritmetik berikutnya sehingga secara otomatis akan mampu mempercepat proses komputasi. Hal ini mengakibatkan banyaknya operasi pada Algoritme 4.4 ini dapat diminimalkan sehingga akan mempercepat proses komputasinya. Algoritme 4.4. Algoritme Reduksi Nol Deskripsi : Mereduksi nol pada posisi sebelah kanan Input
: Vektor T dan bilangan posotof t.
Output
: Vektor 1. T = R, t = banyaknya unsur T 2. Untuk j selama T[t] = 0 dan t >1, lakukan berulang 2.1. Ganti unsur ke-j dari vektor T dengan himpunan kosong 2.2. t = t - 1 3. Return (R)
Algoritme Reduksi Nol di atas jika digunakan pada sebuah algoritme dapat mengurangi jumlah operasi pada algoritme itu sendiri sehingga secara otomatis akan mampu mempercepat proses komputasi. Cara kerja Algoritme ini adalah menghilangkan anggota sebuah vektor yang terletak di sebelah kanan dan bernilai nol. 4.2
Perkalian Polinomial Dua algoritme berikut ini yaitu Algoritme 4.5 dan Algoritme 4.6 digunakan
untuk menunjang Algoritme Perkalian sehingga proses komputasi yang digunakan akan lebih baik daripada melakukan perkalian biasa. Algoritme 4.5. Kelipatan vektor Deskripsi : Mengalikan vektor A dengan skalar n Input
: Vektor
Output
: Vektor
=[
,
,…,
], dan intejer positif
1. Jika n = 0, maka return([0]) 2. Jika n = 1, maka return(A) 3. Selainnya 4. Return (C)
=(
∗
)
5
{0, 1, . . . , 4}
31
Algoritme 4.5 ini sangatlah baik karena hanya melibatkan perkalian vektor dengan skalar. Algoritme 4.6. Geser satu Deskripsi : Menggeser vektor A satu langkah Input
: Vektor
Output
: Vektor
=[
,
,…,
], dan intejer positif
1. L = DatP[m] 2. t = banyaknya unsur vektor A 3. Jika t < m, maka tambahkan 0 di sebelah kiri pada vektor A, selainnya : 4. Tambahkan 0 di sebelah kiri pada vektor A yang telah direduksi pada unsur ke-m 5. Lakukan reduksi nol menggunakan Algoritme 4.3 6. Lipatkan vektor L dengan unsur ke-t pada vektor A menggunakan Algoritme 4.5 7. Jumlahkan hasil dari langkah ke-5 dengan hasil dari langkah ke-6 menggunakan Algoritme 4.4 8. Return(C) Keistimewaan dari algoritme ini adalah hanya mengubah strukturnya saja dan menggeser bersifat konstan. Oleh karena itu apabila digunakan pada suatu algoritme akan mempercepat algoritme tersebut. Dan selanjutnya algoritme ini akan digunakan dalam Algoritme Perkalian. Misalkan ( )=
+
diberikan +⋯
dua dan
sembarang ( )=
+
fungsi +⋯
polinomial serta diberikan
32
fungsi polinomial primitif p(x) sehingga bentuk field perkalian dengan modulo yaitu ( ). ( ) = ℎ( ) dimana ℎ( ) = ( 0 .
0)
+ ( 0.
1
( )
+
1
1 . 0)
+ ⋯+
.
Pada Algoritme 4.7, proses pertama yang dilakukan adalah mengetes apakah
kedua vektor mempunyai unsur yang sama ataukah berbeda. Jika kedua vektor mempunyai unsur yang berbeda, maka vektor yang mempunyai unsur yang lebih banyak ditempatkan sebagai vektor pertama. Hal ini bertujuan agar proses perhitungan dalam komputasinya lebih sedikit. Selanjutnya pada algoritme ini melibatkan algoritme kelipatan vektor, algoritme geser satu, dan algoritme penjumlahan. Algoritme 4.7. Perkalian Polinomial Deskripsi : Mengalikan
dua
vektor,
kemudian
hasil
perkaliannya
=[ ,
,…,
dimoduluskan dengan vektor primitif P Input
: Vektor
=[ ,
intejer positif m Output
: Vektor 1.
,…,
],
vektor
], dan
= [ , , … , ] dan c = nops(R).
Tentukan vektor A, vektor B, s = banyaknya unsur A, dan t = banyaknya unsur B =[0], atau B= [0], maka return([0])
2.
Jika
3.
Jika s < t, maka
3.1. S=B, T=A, a=s, s=t, t=a 3.2. R= Lipatkan vektor T dengan (op(1,S)) menggunakan algoritme 4.5. 3.3. Untuk j dari 1 sampai (s – 1 ), lakukan 3.3.1. T = Lakukan Geser satu dengan algoritme 4.6 3.3.2. V = Lipatkan vektor T dengan (op(j+1,S)) menggunakan algoritme 4.5. 3.3.3. R = Jumlahkan vektor R dan V dengan menggunakan algoritme 4.4 secara rekursif 4.
Return (R)
33
Pembentukan Algoritme 4.7. ini didasarkan pada Teorema 2.45. Karena pada algoritme ini melibatkan Algoritme Kelipatan Vektor, Algoritme Geser Satu, dan Algoritme Penjumlahan yang melibatkan Algoritme Reduksi Nol maka dapat dikatakan bahwa algoritme ini cukup baik karena tidak membutuhkan ruang yang cukup besar dan proses komputasinya cukup cepat. 4.3
Invers Polinomial Untuk menunjukkan bahwa setiap elemen tak nolnya mempunyai invers,
diambil [ ( )]
[ ]/〈 ( 〉)dengan [
) ≠ 0] . Karena [1] merupakan elemen
identitas terhadap operasi perkalian, maka akan ditunjukkan bahwa terdapat [ℎ( )]
[ ]/〈 ( 〉)
( ). ℎ( ) ≡ 1
f(x) tidak membagi
sedemikian
hingga
[ ( )]
atau
( ) . Karena f(x) merupakan polinomial irredusibel dan ( ), maka
( ), ( )
polinomial s(x) dan t(x) sedemikian hingga ( ). ( ) ≡ 1(
[ ( )]. [ℎ( )] = [1]
= 1. Akibatnya terdapat
( ). ( ) + ( ) ( ) = 1 atau
( )). Jadi diperoleh bahwa [ ( )]. [ ( )] = [1] sehingga
= [ ( )]. Untuk menentukan invers dari vekrtor A dapat menggunakan
Algoritme 4.10. Algoritme ini didasarkan pada Definisi 2.17.
Algoritme 4.8 dan Algoritme 4.9 digunakan untuk mendukung Algoritme Invers Polinomial. Algoritme 4.8. Negasi vektor Deskripsi : Mengubah vektor A dengan negasinya Input
: Vektor
Output
: Vektor
=[ ,
=[ ,
,…,
,…, ]
],
1. Petakan unsur x pada vektor A dengan –x 2. Return (C) Algoritme ini digunakan untuk memperoleh invers penjumlahan dari masingmasing anggotanya. Adapun invers dari masing – masing anggotanya adalah sebagai berikut :
34
1 inversnya 4, karena 1+4 = 0 2 inversnya 3, karena 2+3 = 0 3 inversnya 2, karena 3+2 = 0 4 inversnya 1, karena 4+1 = 0 Algoritme 4.9. Pembagian polinomial tanpa modulo m Deskripsi : Membagi dua polinomial tanpa modulo m Input
: Vektor
dan vektor
Output
: Vektor
=[
, dimana ] vektor Q sebagai hasil pembagian dan
vektor R sebagai sisa pembagian 1.
Jika S=[0], maka “false”
2.
R=T; Q=[0]; r = banyaknya unsur T; s = banyaknya unsur S; g = unsur ke-s dari vektor S
3.
4.
Jika s = 1, maka 3.1.
Q = lipatkan vektor R dengan operan S
3.2.
R = [0]
3.3.
Return ([Q, R])
Untuk i selama
≥ , lakukan
4.1.
k = r – s; t = unsur ke-r dari vektor R
4.2.
h = ( t*g) mod 5
4.3.
jika k = 0, maka 4.3.1. K = lipatkan vektor S dengan h 4.3.2. Q = jumlahkan vektor Q dengan [h]
4.4.
Selainnya 4.4.1. H = lipatkan vektor S dengan h 4.4.2. K = [seq(0,j=1..k),op(H)] 4.4.3. Q = jumlahkan (Q,[seq(0,j=1..k),h])
5.
K = negasikan vektor K
6.
R = jumlahkan vektor K dan vektor R
7.
Return ([Q, R])
35
Algoritme Pembagian di atas merupakan pembagian seperti biasa yang tidak melibatkan polinomial primitif
( )sebagai modulonya. Algoritme ini sangat
baik karena operasi-operasi yang digunakan menggunakan operasi penjumlahan dan operasi kelipatan vektor. Algoritme 4.10. Invers Polinomial Deskripsi : Invers polinomial dari suatu bilangan bulat m Input
: Vektor
Output
: Vektor
= [ , , … , ], dan intejer positif m = [ℎ , ℎ , … , ℎ ] dan r = nops(C).
1.
S = Negatifkan vektor (DatP(m)) menggunakan algoritme 1.5
2.
Jika
3.
Jika banyaknya unsur T = 1, maka return (T)
4.
RA = [op(S), seq(0, j = 1…(m – t)), 1];
=[0], maka “salah”
RB = T; QA = [0]; QB = [1]; 5.
L = Bagi vektor RA dan RB menggunakan algoritme 4.9
6.
RA = RB
7.
RB = Operan kedua dari L
8.
Untuk i selama RB tidak nol, maka lakukan langkah berikut berulang-ulang 8.1. Tmp = QA; QA = QB 8.2. H = Kalikan vektor QB dengan op(1,L) menggunakan algoritme 4.7 8.3. R = Negasikan vektor H menggunakan algoritme 4.8 8.4. QB
= Jumlahkan vektor Tmp
dengan
vektor R
menggunakan algoritme 4.4 8.5. L = Lakukan pembagian vektor RA dengan vektor RB menggunakan algoritme 4.9 8.6. RA = RB; RB = operan kedua dari L 9.
H = Lipatkan vektor QB dengan op(RA) menggunakan algoritme 4.5
10. Return (H)
36
Pada Algoritme 4.10, proses pertama yang dilakukan adalah negatifkan vektor dalam DatP(m) yang berfungsi sebagai polinomial primitif menggunakan Algoritme 4.8. Proses kedua adalah gabungkan vektor dalam DatP(m), vektor QA, dan vektor QB ke dalam vektor RA yang kemudian gunakan Algoritme 4.9 untuk menentukan vektor L, yaitu membagi vektor RA dengan vektor RB. Proses selanjutnya adalah selama sisa pembagiannya tidak nol, maka lakukan secara berulang-ulang dengan menggunakan Algoritme operasi rutin yaitu berturut-turut Algoritme 4.7
dan Algoritme 4.8 yang kemudian jumlahkan dengan
menggunakan Algoritme 4.4. Proses yang terakhir adalah gunakan Algoritme 4.5 untuk menentukan vektor H. Algoritme Invers Polinomial ini digunakan untuk menghitung invers (5) merupakan grup siklik multiplikatif. Algoritme ini
perkalian, karena
dapat dikatakan sangat baik secara komputasi dikarenakan didalamnya melibatkan Algoritme Perkalian Polinomial, Algoritme Penjumlahan Polinomial, dan Algoritme Kelipatan Vektor. Algoritme-algoritme tersebut selalu melibatkan proses reduksi nol, geser satu, dan polinomial primitif yang digunakan sebagai modulonya menggunakan polinomial primitif yang bersuku kecil. 4.4
Pembagian Polinomial Misalkan
( )=
+
diberikan
dua
+⋯
dan
sembarang ( )=
fungsi +
polinomial a(x) direpresentasikan sebagai vektor penta sedangkan fungsi polinomial b(x) sebagai vektor
+⋯
=[ ,
=[ ,
,…,
polinomial . ].
Fungsi ,…,
],
Berdasarkan Teorema 2.31, maka kita dapat membuat Algoritme pembagian polinomial (Algoritme 4.5). Pada Algoritme 4.5, langkah pertama adalah menginverskan vektor B dengan Algoritme 4.10, kemudian kalikan vektor A dengan invers vektor B dengan menggunakan Algoritme 4.7 sehingga diperoleh hasil yang diinginkan.
37
Algoritme 4.11. Pembagian Polinomial Deskripsi : Membagi dua polinomial dengan modulo m Input
: Vektor
=[ ,
intejer positif m Output
: Vektor
=[ ,
,…,
],
vektor
=[ ,
,…,
], dan
,…, ]
1.
iB = Inverskan vektor B menggunakan algoritme 4.10
2.
Kalikan vektor A dengan vektor iB menggunakan algoritme
Algoritme Pembagian Polinomial ini hanya melibatkan Algoritme Invers 4.7 Polinomial dan Polinomial yang didalamnya melibatkan operasi reduksi 3. Perkalian Return (C) nol dan kelipatan vektor yang tentunya membutuhkan ruang yang sedikit dan berakibat pada semakin cepatnya proses komputasi yang dijalankan. 4.5
Eksponen Polinomial Aritmetik eksponen polinomial dalam Algoritme 4.12 berfungsi untuk
mengalikan dua fungsi polinomial atau lebih dengan modulo m. Yang menjadi kekuatan dari Algoritme 4.12 ini adalah bahwa finite field sifat grup siklik.
(5) dibentuk dari
Algoritme 4.12. Eksponen Polinomial Deskripsi : Mengeksponensialkan polinomial dalam modulo m = [ , , … , ], intejer x dan intejer positif m Input : Vektor = [ℎ , ℎ , … , ℎ ] Output : Vektor 1. p = 5m – 1 2. k = moduluskan (x, p) menggunakan Algoritme 4.13 3. Jika ≥ 0, maka 3.1. X = konversi nilai k dalam basis 2; t = banyaknya unsur X 3.2. G = A; H = [1] 3.3. Jika X1 = 1, maka H = G 3.4. Untuk i mulai dari 2 sampai t, lakukan 3.4.1. G = kalikan vektor G dengan G menggunakan Algoritme 4.7 3.4.2. Jika Xi = 1, maka H = kalikan vektor H dengan G menggunakan Algoritme 4.7 4. n = -k 5. X = konversi nilai n dalam basis 2; t = banyaknya unsur X 6. G = inverskan vektor A dengan Algoritme 4.10; H = [1] 7. Jika x1 = 1 maka H = G 8. Untuk i mulai dari 2 sampai dengan t, lakukan 8.1. G = kalikan vektor G dengan G menggunakan Algoritme 4.7 8.2. Jika Xi = 1, maka H = kalikan vektor H dengan G menggunakan Algoritme 4.7 9. Return (H)
38
Misalkan
sembarang
polinomial
direpresentasikan dalam bentuk vektor =[ ,
,…,
] dimana
=[ ,
( )=
,…,
+
+ ⋯+
] dan barisan basis dua
[0, 1]serta polinomial primitif
( )berderajat m.
Derajat maksimal dari polinomial di sini berlaku sebagai modulus yaitu (5 − 1),
sedangkan eksponennya merupakan barisan basis dua yang diperoleh dari input i yang dimoduluskan dengan menggunakan Algroritme 4.13 seperti di bawah ini. Algoritme 4.13. Modulus bilangan negarif Deskripsi : Membagi dua polinomial dengan modulo m Input
: integer positif m dan a
Output
: integer b 1. 2. 3.
Hitung = = ( /2) , hasilnya dibulatkan ke bawah Jika b > c, maka 3.1. = −( − ) Return(b)
4. 5. Proses selanjutnya jika nilai yang dimoduluskan lebih dari atau sama dengan nol, maka konversi ke dalam basis dua. Jika hasil konversinya sama dengan 1, maka H = A. Jika hasilnya lebih dari sama dengan 2, maka kalikan vektor yang telah dihasilkan dengan algoritme 4.7 secara berulang. Jika hasilnya selain di atas (bernilai negatif), maka negatifkan hasilnya. Lalu lakukan langkah tersebut di atas secara berulang.
39
BAB V KESIMPULAN DAN SARAN
5.1
Kesimpulan Dari hasil penelitian yang telah dilakukan diperoleh kesimpulan sebagai
berikut : 1.
Finite
field
(5 )
dikonstruksi
mengkonstruksi algoritme aritmetik
dari
polinomial
primitif.
Untuk
(5) dipilih polinomial primitif yang
bersuku terkecil, hal ini akan mengakibatkan proses komputasi yang dijalankan lebih cepat dibandingkan dengan menggunakan polinomial primitif biasa. 2.
Algoritme Reduksi Nol digunakan untuk mengurangi jumlah operasi pada sebuah algoritme. Algoritme ini digunakan pada Algoritme Penjumlahan, Algoritme Penjumlahan digunakan dalam Algoritme Perkalian, Algoritme Penjumlahan dan Algoritme Perkalian digunakan dalam Algoritme Invers, dan seterusnya.
3.
Algoritme Geser Satu mampu mempercepat proses kerja suatu algoritme, karena pada algoritme ini hanya mengubah strukturnya saja dan menggeser bersifat konstan. Algoritme ini digunakan pada Algoritme Perkalian, Algoritme Perkalian digunakan dalam Algoritme Invers, dan seterusnya.
4.
Algoritme aritmetik hasil konstruksi tidak membutuhkan ruang yang besar sehingga cukup cepat dalam komputasinya karena yang dipakai sebagai modulo digunakan polinomial primitif bersuku terkecil, melakukan reduksi nol yang berfungsi mengurangi jumlah operasi dalam algoritme, dan operasi geser satu.
5.2
Saran Hasil konstruksi ini perlu dilanjutkan ke arah kurva eliptik kriptografi.
40
DAFTAR PUSTAKA
Cohen, Henri and Gerhard Frey.(2006). Handbook of Elliptic and Hyperelliptic Curve Cryptography. Chapman & Hall/CRC. Dummit;, D. S. and R. M. Foote. (1999). Abstract Algebra, john Wiley and Sons, Inc. Fraleigh (1994). Abstract Algebra. Gallian, J. A. (1998). Contemporary Abstract Algebra, Houghton Mifflin Company. Greenan, Kevin, M., Miller, Ethan, L., Scwarzh. 2007. Analysis and Construction of Galois Field for Efficient Storage Reliability. Technical Report UCSCSSRC-07-09 Guritman, S. (2004). Struktur Aljabar. Huffman, W. Carry and Vera Pless (2003). Fundamentals of Error-Correcting Codes. Cambridge University Press. Koc, K. Cetin, Acar, Tolga. Montgomery Multiplication in GF(2k). Designs, Codes and Cryptography 14(1), 57-69 Menezes, A., P. v. Oorschot, et al. (1996). Handbook of Applied Cryptography, CRC Press. Pinter, C. C. (1990). A Book of Abstract Algebra, McGraw-Hill, Inc. Pless, Vera (1990). Introduction to the Theory of Error-Correcting Codes, Second Edition. John Willey & Sons, Inc. Rosdiana, Sri (2009). Konstruksi Algoritme Aritmetik (5) Dengan Operasi Perkalian Dibangkitkan Dari Sifat Grup Siklik. Tesis.
41
Lampiran I.
POLINOMIAL PRIMITIF DI DALAM
No.
Derajat m
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 26 27 28 29 30 31 32 33 34 35 36 37
m=2 m=3 m=4 m=5 m=6 m=7 m=8 m=9 m = 10 m = 11 m = 12 m = 13 m = 14 m = 15 m = 16 m = 17 m = 18 m = 19 m = 20 m = 21 m = 22 m = 23 m = 24 m = 25 m = 26 m = 27 m = 28 m = 29 m = 30 m = 31 m = 32 m = 33 m = 34 m = 35 m = 36 m = 37
( )
Polinomial Primitif + +2 +3 +2 + + 2 +2 + 4 +2 + +2 + 3 +2 + + 2 +3 + +2 +3 + + +3 + 3 +2 + + 2 +3 + + 3 +2 + + + 2 +2 + +2 + + 3 +2 + 2 + 2 +2 + + 2 +2 + + 2 +2 + + 2 +3 + 4 +2 + + +3 + + 4 +3 + + + +2 + 2 + 3 +2 + + + 2 +2 + 4 +2 + + 2 +3 + + +3 + + 2 + +3 +3 +2 + + + 4 +2 + 2 + 2 +2 + + 2 +2 + + + 3 +2 + + 3 +2 + + 3 +2
42
38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70
m = 38 m = 39 m = 40 m = 41 m = 42 m = 43 m = 44 m = 45 m = 46 m = 47 m = 48 m = 49 m = 50 m = 51 m = 52 m = 53 m = 54 m = 55 m = 56 m = 57 m = 58 m = 59 m = 60 m = 61 m = 62 m = 63 m = 64 m = 65 m = 66 m = 67 m = 68 m = 69 m = 70
+
+ 3 + +2 + 2 + 3 +2 + + + 3 +3 + 4 +2 + + 3 + +2 + 3 +2 +2 + + + 3 +3 + 2 + 2 +2 + +2 + +3 + + + +2 + + + 2 +2 + + + 4 +2 + + +2 +3 + + +3 + + + + 2 +3 + 2 +2 + +3 + + + +3 + 3 + +2 + + + 4 +2 + 4 +2 + +2 + 2 +2 + +2 + +3 + + + 3 +3 + + 2 +3 + + + + +2 + + 2 + 2 + +3 + 4 +3 +3 + + +2 +2 +4 + +3 + + + +3 + +3 +3 + +2 + 3 +2 + + + + +2
