KONSTRUKSI ALGORITME ARITMETIK GF(3m)DENGAN OPERASI DIBANGKITKAN DARI

SIFAT GRUP SIKLIK

I L H A M

SEKOLAH PASCASARJANAINSTITUT PERTANIAN BOGOR

BOGOR2009

PERNYATAAN MENGENAI TESISDAN SUMBER INFORMASI

Dengan ini saya menyatakan bahwa tesis dengan judul Konstruksi AlgoritmeAritmetik GF(3m) dengan Operasi Dibangkitkan dari Sifat Grup Siklik adalah karya sayasendiri dengan arahan dari komisi pembimbing dan belum diajukan dalam bentuk apapunkepada perguruan tinggi mana pun. Sumber informasi yang berasal atau dikutip darikarya yang diterbitkan maupun tidak diterbitkan dari penulis lain telah disebutkan dalamteks dan dicantumkan dalam daftar pustaka di bagian akhir tesis ini.

Bogor, Agustus 2009

I L H A MNRP G551070631

ABSTRACT

ILHAM. The Construction of Arithmetic Algorithm (3 )mGF with Operation Generated

from Cyclic Group. 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 p , the usual arithmetic

concept. If the use of this arithmetic is associated with security aspect, then it requireslarge computational work. This thesis aims to construct arithmetic algorithm as analternative arithmetic to apply in any cryptographic scheme, especially public key

scheme. This algorithm is generated from finite field (3 )mGF . Thus, the procedures to

construct arithmetic algorithm as follows. Firstly, take the primitive polynomial

3( ) [ ]p x x as the minimum polynomial of degrees m with as a root. Secondly,

represent all elements of (3 )mGF as vectors in m-dimensional vector space over 3 . The

resulted arithmetic algorithms are computational procedures for standard operation in

(3 )mGF , i.e. addition, multiplication, division, invertion, and exponentiation.

Asymptotically, complexity of the algorithms is the same as the previous one, which isconstructed by irreducible polynomial. However, for a small value of m the resultedalgorithms are better because some operations can be reduced using primitivepolynomial or cyclic group properties.

Keywords: arithmetic, cyclic group, primitive polynomial, cryptography.

RINGKASAN

ILHAM. Konstruksi Algoritme Aritmetik GF(3m) dengan Operasi Dibangkitkan dariSifat Grup Siklik. Dibimbing oleh SUGI GURITMAN and NUR ALIATININGTYAS.

Perkembangan teknologi informasi memudahkan seseorang untuk mendapatkaninformasi yang dibutuhkan. Untuk mengamankan informasi yang sifatnya rahasiadiperlukan suatu teknik pengamanan. Teknik tersebut dapat dilakukan denganmengamankan baik secara fisik maupun non fisik. Salah satu pengamanan secara nonfisik adalah dengan mengenkripsi informasi rahasia menggunakan teknik kriptografi.

Terdapat dua tipe umum dari algoritme yang berbasis kunci, yaitu AlgoritmeSimetrik dan Algoritme Asimetrik (kunci publik) (Schneier 1996). Kriptografi simetrikdisebut juga kriptografi konvensional, yaitu kunci enkripsi dapat dihitung dari kuncideskripsi atau sebaliknya, karena kunci yang digunakan adalah sama. Kriptografisimetrik tergantung pada kerahasiaan kunci yang digunakan. Kriptografi asimetrikdisebut juga kriptografi kunci publik yang didesain bahwa yang digunakan untukenkripsi berbeda dengan kunci yang digunakan untuk deskripsi. Kriptografi kunci publikterdiri atas dua buah kunci yaitu kunci publik dan kunci pribadi. Kunci publik digunakanuntuk mengenkripsi suatu pesan kedalam siferteks sedangkan kunci pribadi digunakanuntuk mendekripsi siferteks menjadi pesan asli.

Salah satu contoh penyandian dengan menggunakan kunci publik adalahpenyandian kunci publik ElGamal dengan aritmetik modular atas dasar sifat grup siklik

p yang pertama kali diperkenalkan oleh Taher ElGamal pada tahun 1985 dan sampai

saat ini masih dipercaya sebagai metode penyandian. Kunci publik yang digunakan

dalam penyandian ElGamal ini adalah ( , , mod )ap p dimana kunci pribadinya

adalah a . Dengan demikian, untuk keamanan penyandian ElGamal ini dibuatlah p

dengan memilih p yang sangat besar dalam proses kalkulasi aritmetik untuk

membangkitkan kunci yang digunakan (Menezes 1997). Jika penggunaan aritmetik padapenyandian ElGamal dikaitkan dengan aspek keamanan, maka memerlukan bebankomputasi yang cukup besar sehingga dalam dekade terakhir diperlukan aritmetikalternatif sebagai pengganti aritmetik modular. Aritmetik-aritmetik pengganti tersebut di

antaranya adalah aritmetik yang dibangkitkan dari srtuktur field berhingga (3 )mGF ,

kurva eliptik, atau kurva hipereliptik.

Dalam peneltian ini, penulis menitikberatkan pada pembahasan aritmetik yang

dibangkitkan dari struktur field berhingga (3 )mGF sebagai perluasan dari field 3 . Atas

dasar inilah, maka penelitian ini bertujuan untuk mengkonstruksi field berhingga

(3 )mGF dari 3 berdasarkan sifat perluasan field, mengonstruksi algoritme aritmetik

(3 )mGF seperti operasi penjumlahan, operasi perkalian, operasi invers, operasi

pembagian, dan operasi exponensial, dan mengukur kinerja algoritme yang dihasilkan

berdasarkan kompleksitas. Untuk mengonstruksi algoritme aritmetik (3 )mGF dalam

penelitian ini dilakukan dengan prosedur sebagai berikut.

Pertama, mengambil polinomial primitif berderajat m atas 3 yang merupakan

polinomial minimum 0 1( ) ... mmm x a a x a x dimana merupakan akar primitifnya

sedemikian sehingga ( ) 0m . Pengambilan polinomial primitif ini dilakukan secara

komputasi dengan langkah-langkah sebagai berikut. Tes apakah polinomial ( )m x adalah

irreducible, tes apakah polinomial irreducible adalah primitif, selanjutnya memilihpolinomial primitif yang bersuku kecil, yaitu dari polinomial primitif yang bersuku dua,polinomial primitif yang bersuku tiga, atau polinomial primitif yang bersuku empat.

Kedua, representasikan semua elemen dari (3 )mGF sebagai vektor dalam ruang vektor

berdimensi-m atas 3 . Untuk kepentingan komputasi, elemen (3 )mGF dapat

direpresentasikan sebagai vektor terner dari derajat terkecil ke derajat terbesar dalambentuk 0 1 1[ , , . . . , ]ma a a .

Algoritme aritmetik (3 )mGF yang dihasilkan dikonstruksi dari polinomial

primitif bersuku kecil yang terdiri atas algoritme operasi penjumlahan, algoritme operasiperkalian, algoritme operasi invers, algoritme operasi pembagian, dan algoritme operasieksponensial. Secara umum, algoritme yang dihasilkan secara asimptotik mempunyaikinerja yang sama dengan algoritme sebelumnya yang didasarkan pada pengambilanpolinomial irreducible. Dengan demikian, secara rata-rata algoritme yang dihasilkanmenjadi lebih baik karena beberapa operasi dapat direduksi menggunakan polinomialprimitif atau sifat dari grup siklik.

Kata kunci: aritmetik, grup siklik, polinomial primitif, kriptografi.

© Hak Cipta Milik IPB, tahun 2009Hak Cipta Dilindungi Undang-undang

1. Dilarang mengutip sebagian atau seluruh karya tulis ini tanpa mencantumkanatau menyebutkan sumbera. Pengutipan hanya boleh untuk kepentingan pendidikan penelitian, penulisan

karya ilmiah, penyusunan laporan, penulisan kritik, atau tinjauan suatumasalah.

b. Pengutipan tidak merugikan kepentingan yang wajar IPB.2. Dilarang mengumumkan dan memperbanyak sebagian atau seluruh karya tulis

dalam bentuk laporan apapun tanpa ijin IPB.

PRAKATA

Puji dan syukur penulis panjatkan kepada Allah SWT atas segala karunia danhidayahNya sehingga karya ilmiah berjudul Konstruksi Algoritme Aritmetik GF(3m)dengan Operasi Dibangkitkan dari Sifat Grup Siklik berhasil diselesaikan.

Terima kasih penulis ucapkan kepada Bapak Dr. Sugi Guritman dan Ibu Dra. NurAliatiningtyas, M. Si. yang telah membimbing penulis selama melakukan penelitian danbanyak memberikan masukan dan saran, serta Ibu Dr. Ir. Sri Nurdiati, M. Sc. selakupenguji luar komisi pada ujian tesis yang telah memberikan masukan dan saran. Tak lupapenulis sampaikan penghargaan atas segala kerjasama dan dukungan dari Ibu Dr. Ir.Endar H. Nugrahani, MS. selaku Ketua Program Studi Matematika Terapan, Ibu Dr.Berlian Setiawaty selaku Ketua Departemen Matematika, dan Departemen AgamaRepublik Indonesia yang telah memberikan beasiswa kepada penulis selama menempuhstudi di Institut Pertanian Bogor.

Akhirnya, ucapan terima kasih yang tak terhingga penulis berikan kepada ayah,ibu, istri, dan putra-putri tercinta atas segala pengorbanan dan dukungannya selamapenulis menyelesaikan studi. Semoga karya ilmiah ini dapat bermanfaat bagi kemajuanilmu pengetahuan dan teknologi di masa mendatang.

Bogor, Agustus 2009

I L H A M

RIWAYAT HIDUP

Penulis dilahirkan di Desa Risa Kecamatan Woha Kabupaten Bima pada tanggal20 Oktober 1971 dari Bapak Usman Zakaria dan Ibu Sitti Hawa H. Bahari. Penulismerupakan putra kedua dari enam bersaudara.

Tahun 1990 penulis lulus dari SMA Negeri 1 Woha Kabupaten Bima danmelanjutkan studi pada IAIN Alauddin Makassar dengan memilih Program Studi TadrisMatematika Fakultas Tarbiyah dan lulus pada tahun 1995. Penulis mendapatkankesempatan untuk melanjutkan studi ke program magister pada Program StudiMatematika Terapan Institut Pertanian Bogor pada tahun 2007 dengan mendapatkanbeasiswa pendidikan dari Departemen Agama Republik Indonesia.

Saat ini penulis telah menikah dengan Faridah, S. Ag dan dikaruniai satu orangputra yang bernama Muhammad Farid berusia 12 tahun dan dua orang putri, yangmasing-masing bernama Dewi Arifah berusia 11 tahun, dan Berlian Setiawati berusia 1tahun 2 bulan. Tahun 2001 penulis diangkat sebagai Pegawai Negeri Sipil padaDepartemen Agama Republik Indonesia dan mengajar Bidang Studi Matematika padaMadrasah Aliyah Korleko Kabupaten Lombok Timur Nusa Tenggara Barat. Kemudianpada tahun 2003 penulis dimutasikan pada Madrasah Tsanawiyah Negeri Kandai IIKabupaten Dompu Nusa Tenggara Barat sebagai Guru Matematika sampai sekarang.

KONSTRUKSI ALGORITME ARITMETIK GF(3m)DENGAN OPERASI DIBANGKITKAN DARI

SIFAT GRUP SIKLIK

I L H A M

TesisSebagai salah satu syarat untuk memperoleh gelar

Magister Sains padaProgram Studi Matematika Terapan

SEKOLAH PASCASARJANAINSTITUT PERTANIAN BOGOR

BOGOR2009

Penguji Luar Komisi pada Ujian Tesis : Dr. Ir. Sri Nurdiati, M. Sc.

Judul Tesis : Konstruksi Algoritme Aritmetik (3 )mGF dengan Operasi Dibangkitkan

dari Sifat Grup SiklikNama : I l h a mNRP : G551070631

Disetujui

Komisi Pembimbing

Dr. Sugi Guritman Dra. Nur Aliatiningtyas, M. Si.Ketua Anggota

Diketahui

Ketua Progam Studi Dekan Sekolah PascasarjanaMatematika Terapan

Dr. Ir. Endar H. Nugrahani, M.S. Prof. Dr. Ir. Khairil A. Notodiputro, M.S.

Tanggal Ujian: 12 Agustus 2009 Tanggal Lulus:

DAFTAR ISI

Halaman

DAFTAR ALGORITME .…………………………………………………... iv

BAB I PENDAHULUAN ................................................................................ 1

1.1 Latar Belakang Masalah ………………………………............... 11.2 Tujuan Penelitian ………………………………......................... 31.3 Manfaat Penelitian ....................................................................... 3

BAB II LANDASAN TEORI .......................................................................... 4

2.1 Grup dan Subgrup ......................................................................... 42.2 Grup Siklik ................................................................................... 62.3 Homomorfisma Grup dan Isomorfisma ..………………………. 72.4 Grup Faktor dan Subgrup Normal .............................................. 92.5 Ring ....………………………………………………………….122.6 Ring Polinomial .………………………………………………...172.7 Ruang Vektor .....………………………………………..........… 202.8 Perluasan Field ....................... .................................................... 212.9 Kompleksitas Komputasi ............................................................. 24

BAB III BAHASAN KONSTRUKSI (3 )mGF ...........…………………........... 26

BAB IV BAHASAN ALGORITME ARITMETIK (3 )mGF ..………………. 36

4.1 Operasi Penjumlahan ................................................................... 374.2 Operasi Perkalian ......................................................................... 394.3 Operasi Invers .............................................................................. 414.4 Operasi Pembagian ...................................................................... 424.5 Operasi Exponen .......................................................................... 42

BAB V PENERAPAN ARITMETIK (3 )mGF PADA

ALGORITME DIFFIE-HELLMAN KEY EXCHANGE …………... 47

BAB VI SIMPULAN DAN SARAN ...……………………………...………… 50

6.1 Simpulan ..………………………………………………………. 506.2 Saran ..........................................………………………………... 50

DAFTAR PUSTAKA ........................................................................................ 51

LAMPIRAN …………………………………………………………………... 52

DAFTAR ALGORITME

Algoritme Halaman

3.1 Prosedur untuk mengubah desimal ke vektor terner ..................................... 30

3.2 Prosedur untuk membangkitkan vektor terner berdimensi m dengan

elemen pertama tak-nol secara acak ........................................................... . 31

3.3 Prosedur untuk pengecekan Vektor Irreducible atau tidak .......................... 31

3.4 Prosedur untuk memeriksa apakah Vektor Irreducible adalah Primitif ........ 31

3.5 Prosedur untuk membangkitkan Vektor Primitif bersuku dua ...................... 32

3.6 Prosedur untuk membangkitkan Vektor Primitif bersuku tiga ...................... 32

3.7 Prosedur untuk membangkitkan Vektor Primitif bersuku empat ….............. 33

4.1 Prosedur untuk mereduksi nol ...................................................................... 37

4.2 Operasi Penjumlahan ................................................................................... 38

4.3 Prosedur untuk mengalikan kelipatan vektor ................................................ 39

4.4 Prosedur untuk menggeser satu langkah ....................................................... 39

4.5 Operasi Perkalian ......................................................................................... 40

4.6 Prosedur untuk membagi vektor tanpa modulo ............................................ 41

4.7 Operasi Invers .............................................................................................. 42

4.8 Operasi Pembagian ...................................................................................... 43

4.9 Prosedur untuk menghitung a mod m dalam rentang negatif ....................... 45

4.10 Operasi Exponen .......................................................................................... 45

5.1 Prosedur untuk pembangkitan Prima Relatif secara acak ............................ 47

5.2 Prosedur untuk pembangkitan elemen Primitif Acak ................................. 48

5.3 Prosedur untuk Diffie-Hellman Key Exchange ............................................ 48

BAB IPENDAHULUAN

1.1 Latar Belakang Masalah

Dalam perkembangan teknologi informasi, disadari atau tidak orang sudah

banyak mengenal tentang kriptografi dan banyak algoritme yang digunakan untuk

mengamankan informasi rahasia. Kriptografi adalah ilmu dan seni untuk menjaga

kerahasiaan pesan dengan cara menyandikan isi informasi menjadi suatu kode-kode yang

yang tidak dapat dimengerti sehingga apabila disadap maka si penyadap akan kesulitan

untuk mengetahui isi informasi yang sebenarnya (Schneier 1996). Metode penyandian ini

menitikberatkan pada kerahasiaan suatu algoritme yang digunakan. Karena penggunaan

metode ini tidak efisien maka algoritme rahasia mulai ditinggalkan dan memperkenalkan

suatu metode baru yang disebut dengan algoritme kunci. Metode ini tidak

menitikberatkan pada keamanan suatu algoritme, tetapi pada kerahasiaan kunci yang

digunakan pada proses penyandian.

Menezes (1997) mendefinisikan kriptografi sebagai studi teknik matematika yang

berhubungan dengan aspek keamanan informasi seperti kerahasiaan, integritas data,

otentikasi, dan non-repudiasi. Algoritme kriptografi adalah suatu fungsi matematika

yang digunakan untuk enkripsi dan deskripsi (Schneier 1996). Terdapat dua tipe umum

dari algoritme yang berbasis kunci, yaitu Algoritme Simetrik dan Algoritme Asimetrik

(kunci publik) (Schneier 1996). Kriptografi simetrik disebut juga kriptografi

konvensional, yaitu kunci enkripsi dapat dihitung dari kunci deskripsi atau sebaliknya,

karena kunci yang digunakan adalah sama. Kriptografi simetrik tergantung pada

kekuatan kunci yang digunakan.

Kriptografi asimetrik disebut juga kriptografi kunci publik yang didesain bahwa

yang digunakan untuk enkripsi berbeda dengan kunci yang digunakan untuk deskripsi.

Kriptografi kunci publik terdiri atas dua buah kunci yaitu kunci publik dan kunci pribadi.

Kunci publik digunakan untuk mengenkripsi suatu pesan ke dalam siferteks sedangkan

kunci pribadi digunakan untuk mendekripsi siferteks menjadi pesan asli.

2

Salah satu contoh penyandian dengan menggunakan kunci publik adalah

penyandian kunci publik ElGamal dengan aritmetik modular atas dasar sifat grup siklik

p yang pertama kali diperkenalkan oleh Taher ElGamal pada tahun 1985 dan sampai

saat ini masih dipercaya sebagai metode penyandian. Kunci publik yang digunakan

dalam penyandian ElGamal ini adalah ( , , mod )ap p dimana kunci pribadinya

adalah a . Keamanan algoritme ini sangat tergantung pada pemilihan bilangan prima p

yang sangat besar dalam proses kalkulasi aritmetik untuk membangkitkan sebuah kunci.

yang digunakan (Menezes 1997). Jika penggunaan aritmetik pada penyandian ElGamal

ini dikaitkan dengan aspek keamanan, maka diperlukan beban komputasi yang cukup

besar sehingga dalam dekade terakhir diperlukan aritmetik alternatif sebagai pengganti

aritmetik modular. Aritmetik-aritmetik pengganti tersebut di antaranya adalah aritmetik

yang dibangkitkan dari srtuktur field berhingga (3 )mGF , kurva eliptik, atau kurva

hipereliptik.

Beberapa penelitian yang mengarah pada konsep aritmetik yang dibangkitkan

dari srtuktur field berhingga di antaranya adalah Bertoni et al. (2003) dalam papernya

yang berjudul ”Efficient ( )mGF p Arithmetic Architectures for Cryptographic

Applications” yang memberikan kontribusi dalam membangun aritmetik ( )mGF p

dimana p adalah bilangan prima yang direduksi dari polinomial irreducible. Adapun

Truong et al. (1988) dalam papernya yang berjudul ”Efficient Multiplication Algorithm

Over the Finite Field ( )mGF q where q = 3, 5 ”. Omran et al. (2007) dalam papernya

berjudul “Software Implementation of Arithmetic in3m ” membangun algoritme

multiplikatif cepat dalam3m dengan menggunakan representasi basis polinomial dan

basis normal gaussian.

Dlam peneltian ini, penulis menitikberatkan pada pembahasan aritmetik yang

dibangkitkan dari struktur field berhingga (3 )mGF sebagai perluasan dari field 3 yang

didasarkan pada sifat grup siklik bahwa setiap elemen ( )mGF p memenuhi polinomial

1 1 0mp dan selalu mempunyai akar sebagai elemen pembangun ( )mGF p

(Menezes 1997). Atas dasar inilah, penulis mencoba untuk mengonstruksi algoritme

3

aritmetik (3 )mGF dengan mengambil polinomial primitif berderajat m atas 3 yang

merupakan polinomial minimum 0 1( ) ... mmm x a a x a x dimana merupakan akar

primitifnya sedemikian sehingga ( ) 0m . Selanjutnya, semua elemen (3 )mGF

direpresentasikan sebagai ruang vektor berdimensi-m atas 3 dari derajat terkecil ke

derajat terbesar dalam bentuk 0 1 1[ , ,..., ]ma a a .

1.2 Tujuan Penelitian

1. Mengonstruksi field berhingga (3 )mGF dari 3 berdasarkan sifat perluasan field.

2. Mengonstruksi algoritme aritmetik (3 )mGF seperti operasi penjumlahan, operasi

perkalian, operasi invers, operasi pembagian, dan operasi exponensial.

3. Mengimplementasikan algoritme-algoritme yang dihasilkan pada Software MAPLE

11 dengan mempertimbangkan kecepatan operasinya.

1.3 Manfaat Penelitian

Manfaat dari aritmetik yang dihasilkan dalam penelitian ini adalah sebagai kajian

akademik yang mengarah pada perkembangan cabang matematika diskret, sebagai

aritmetik alternatif untuk diterapkan pada algoritme kriptografi, dan untuk konstruksi

Error Correcting Codes, serta diharapkan dapat diaplikasikan pada pengembangan yang

lebih luas khususnya pada teknologi informasi.

BAB IILANDASAN TEORI

Untuk mencapai tujuan penelitian, diperlukan beberapa pengertian dan teori yang

relevan dengan pembahasan. Dalam bab ini akan diberikan beberapa teori berupa

definisi, teorema, maupun lemma yang berkaitan dengan konsep struktur aljabar.

2.1 Grup dan Subgrup

Definisi 2.1 Grup G adalah sebuah sistem aljabar yang terdiri atas suatu himpunan tak

kosong G dan suatu operasi biner (*) yang didefinisikan dalam G serta memenuhi

aksioma-aksioma berikut ini:

(1) Operasi * bersifat assosiatif, yaitu a * ( b * c) = (a * b) * c, untuk setiap a, b, c G.

(2) Terdapat elemen identitas Ge sedemikian sehingga a e e a a , untuk setiap

Ga .

(3) Untuk setiap Ga , terdapat elemen 1 Ga sedemikian sehingga

1 1a a a a e .

Sebuah Grup G disebut sebagai grup komutatif atau grup abelian jika operasi * bersifat

komutatif yang memenuhi aksioma:

(4) a * b = b * a, untuk setiap a, b G (Fraleigh 2003).

Jika sebuah grup G memiliki jumlah elemen yang berhingga maka disebut grup

berhingga (finite group) dan jika jumlah elemen dari suatu grup G tak berhingga maka

disebut grup tak berhingga (infinite group). Order dari sebuah grup G sama dengan

banyaknya elemen dalam grup G yang dinotasikan dengan G (Guritman 2004).

Contoh grup yang tidak asing lagi adalah bilangan bulat terhadap operasi

penjumlahan. Misalkan, merupakan himpunan bilangan bulat

{..., 3, 2, 1,0,1,2,3,...} . ( , ) merupakan suatu grup, karena untuk setiap ,a b

maka ( )a b . Bila , ,a b c maka ( ) ( )a b c a b c juga elemen

(memenuhi sifat assosiatif). 0 dan untuk setiap a maka 0 0 0a a (0

elemen identitas. Bila a maka terdapat a sedemikian sehingga

( ) ( ) 0a a a a ( a elemen invers). Grup ini juga merupakan grup komutatif,

karena a b b a .

5

Misalkan grup G dan S sembarang himpunan bagian tidak kosong dari G, maka

berikut merupakan definisi subgrup yang saling ekuivalen, yaitu sebuah himpunan

bagian S dari grup G disebut subgrup dari G jika S sendiri membentuk grup di bawah

operasi yang sama dengan yang dimiliki G (Aliatiningtyas 2002). Sebagai contoh, ,

dan merupakan subgrup dari terhadap operasi penjumlahan. Tentu saja

dan masing-masing merupakan grup terhadap operasi yang sama yaitu

penjumlahan.

Misalkan S adalah himpunan bagian dari sebuah grup G. S dikatakan subgrup

dari G jika dan hanya jika memenuhi sifat berikut ini.

i). S tertutup dalam operasi dalam G, yaitu jika , Sa b maka Sab .

ii). S tertutup terhadap inversnya, yaitu Sa maka 1 Sa (Aliatiningtyas 2002).

Bilangan bulat adalah grup terhadap operasi penjumlahan. Misalkan S adalah

himpunan bagian dari yang terdiri atas seluruh perkalian bilangan bulat positif m,

yaitu S {... , 2 , , 0, , 2 , ...}m m m m . Dengan menggunakan sifat di atas, maka

dapat ditunjukkan bahwa S adalah subgrup dari G.

Hubungan antara grup dan subgrupnya dapat ditambahkan dengan satu definisi

yang disebut dengan koset.

Definisi 2.2 Misalkan S adalah subgrup dari grup G. Untuk setiap Ga , maka

himpunan yang dinotasikan dengan S { S}a as s disebut koset kiri dari S yang

memuat a dan S { S}a sa s disebut koset kanan dari S yang memuat a (Aliatiningtyas

2002).

Teorema 2.3 (Teorema Lagrange) Misalkan G yaitu grup berhingga dan S yaitu subgrup

dari G, maka order dari S membagi order dari G (Aliatiningtyas 2002).

Jika S merupakan subgrup dari grup G, maka indeks dari S di dalam G dapat

diartikan sebagai banyaknya koset dari S di dalam G, dinotasikan (G : S) (Aliatiningtyas

2002).

6

Misalkan adalah sebuah grup bilangan bulat dalam penjumlahan dan subgrup

3 {..., -6, -3, 0, 3, 6, ...} terdiri atas kelipatan 3. Terdapat tiga koset kiri yang

berbeda dari 3 dalam , yaitu 0 + 3 = 3 = {..., -6, -3, 0, 3, 6, ...}, 1 + 3 = {...,

-5, -2, 1, 4, 7, ...}, 2 + 3 = {..., -4, -1, 2, 5, 8, ...}. Meskipun dan 3 keduanya tak

berhingga, indeks dari 3 dalam adalah berhingga, yaitu ( :3 ) = 3 adalah

banyaknya koset.

2.2 Grup Siklik

Sebelum mendefinisikan tentang grup siklik, maka berikut ini diberikan beberapa

definisi yang terkait dengan order suatu unsur grup. Misalkan G adalah sembarang grup,

Ga dan bilangan bulat positif m , maka

kali

: ...m

m

a aa a ,

1 1 1

kali

: ...m

m

a a a a , dan

0 :a e (Guritman 2004).

Jadi, jika G adalah suatu grup dan Ga , maka untuk semua bilangan bulat

positif m dan n berlaku hukum eksponen berikut ini.

1). m n m na a a

2). ( )m n mna a

3). 1 1( ) ( )m m ma a a .

Misalkan G grup, dan Ga . Order dari elemen a dinotasikan ( )O a

didefinisikan sebagai bilangan bulat positif terkecil m sehingga ma e . Jika tidak ada

bilangan demikian, maka dikatakan order tak hingga (infinity) atau nol (Aliatiningtyas

2002).

Teorema 2.4 1). Jika ( )O a m , maka ada tepat m kuasa dari a (power of a) yang

masing-masing berbeda, yaitu 0 2 1, , ,..., ma e a a a . 2). Jika ( )O a tak hingga, maka

semua kuasa dari a berbeda. Artinya, jika r dan s adalah dua bilangan bulat yang berbeda

7

maka r sa a . 3). Misalkan a adalah unsur dari grup G dan ( )O a m , maka ta e jika

dan hanya jika t adalah kelipatan dari m (t kelipatan m, artinya ada bilangan bulat q

sehingga t mq ) (Aliatiningtyas 2002).

Definisi 2.5 Sebuah grup G dan sebuah elemen Ga (a disebut elemen pembangun).

Jika G { }ma a m maka G disebut grup siklis (cyclic group).

Jika G berhingga dan berorder m , maka dapat ditunjukkan

0 2 1{ , , , ..., }mG a a e a a a .

Jika G adalah grup aditif, maka dapat ditunjukkan

G { }a ma m

dan jika berorder m , maka dapat ditunjukkan

{0 0, , 2 , ..., (m-1) }G a a a a a (Guritman 2004).

2.3 Homomorfisma Grup dan Isomorfisma

Definisi 2.6 Diberikan grup G dan H. Suatu homomorfisma grup dari G ke H adalah

suatu fungsi : G Hf sedemikian sehingga untuk sembarang a dan b di dalam G,

berlaku ( ) ( ) ( )f ab f a f b (Fraleigh 2003).

Terkait dengan jenis fungsi, maka terdapat empat jenis homomorfisma f , yaitu:

1). Jika f bersifat injektif, maka f disebut monomorfisma.

2). Jika f bersifat surjektif, maka f disebut epimorfisma. Dalam hal ini, H disebut imej

homomorfik dari G oleh f .

3). Jika f bersifat bijektif, maka f disebut isomorfisma. Dalam hal ini, G dan H

dikatakan isomorfik.

8

4). Jika f bersifat bijektif dan GH, maka f disebut automorfisme (Aliatiningtyas

2002).

Definisi 2.7 Kernel dari f , ditulis Ker( f ) adalah himpunan dari elemen G yang

imagenya adalah elemen identitas e dari H, yaitu Ker ( ) { G : ( ) }f a f a e .

Sedangkan Bayangan (Image) dari f , ditulis f(G) atau Im( f ) terdiri dari image-image

dari elemen-elemen G dalam f , yaitu Im ( ) { : ( )}f b H b f a , untuk beberapa

Ga (Guritman 2004).

Sebagai contoh, diberikan fungsi 6 3: , ,f dengan ( ) (mod 3)f x x ,

6x maka f merupakan homomorfisma, sebab 1 2 6,x x berlaku

f(x1 +x2) = (x1 + x2) mod 3

= (x1 mod 3) + (x2 mod 3)

= f(x1) + f(x2)

dan 6ker( ) { ( ) 0}f x f x

6{ (mod 3) 0}x x

{0, 3} .

Dengan demikian, 3 disebut bayangan homomorfik dari G oleh f .

Teorema 2.8 Misalkan G dan H adalah grup. Suatu fungsi : G Hf adalah

homomorfisma, maka sifat-sifat berikut dipenuhi.

1). ( )f e e (secara implisit bahwa e pada ruas kiri adalah unsur identitas G dan e pada

ruas kanan adalah unsur identitas H).

2). 1 1( ) [ ( )]f a f a untuk setiap a G .

3). Im( )f merupakan subgrup dari H.

4). Ker( )f merupakan subgrup dari G (Guritman 2004).

Selanjutnya, dua grup G dan Hdikatakan isomorfik (dinotasikan G H ), jika

ada suatu isomorfisma dari G ke H. Sifat penting yang terkandung dari makna isomorfik

adalah walaupun secara fisik kedua grup tersebut berbeda, tetapi dari segi struktur adalah

9

sama. Kesamaan struktur memegang peranan penting dalam matematika secara umum,

karena timbulnya konsep matematika berangkat dari konsep abstraksi. Jika kita

mempelajari bangun segitiga, maka kita tidak akan mempertanyakan segitiga itu terbuat

dari apa, namun bagaimana sifat-sifat dan struktur segitiga itu. Dari makna ini, jika

G H (walaupun mungkin elemen dan operasi dari keduanya berbeda), maka sifat-sifat

yang terkait dengan elemen dan operasinya sama. Hal ini dapat disajikan dalam teorema

berikut ini.

Teorema 2.9 Sifat-sifat isomorfik

1). Untuk grup berhingga, maka G H

2). G abelian jika dan hanya jika H abelian.

3). G siklik jika dan hanya jika H siklik.

4). G dibangkitkan oleh dua unsur jika dan hanya jika H dibangkitkan oleh dua unsur.

5). Jumlah unsur yang mempunyai invers dirinya sendiri di dalam GdanH adalah sama

(Guritman 2004).

Misalkan G adalah grup bilangan real dalam penjumlahan dan H adalah grup dari

bilangan positif real dalam perkalian dengan pemetaan : G Hf yang didefinisikan

oleh ( ) 3af a , maka pemetaan f merupakan homomorfisma karena

( ) 3 3 3 ( ) ( )a b a bf a b f a f b . Selanjutnya, f adalah injektif karena ( ) ( )f a f b

3 3a b a b dan f adalah surjektif karena untuk setiap 3a H terdapat a G

sedemikian sehingga ( ) 3af a . Dengan demikian, maka f adalah sebuah isomorfisma.

2.4 Grup Faktor dan Subgrup Normal

Definisi 2.10 Misalkan G grup dan S subgrup dari G. Maka S disebut subgrup normal

dari G jika untuk setiap Gg , s S , 1 Sgsg (Aliatiningtyas 2002).

Teorema 2.11 Misalkan G grup, S subgrup dari G, maka S subgrup normal dari G jika

dan hanya jika gS = Sg untuk setiap Gg (Aliatiningtyas 2002).

10

Jika S adalah subgrup normal dari grup G, maka koset dari S dalam G

membentuk sebuah grup /G S di bawah operasi ( )( )aS bS abS . Grup ini disebut grup

faktor (quotient) dari G dan S. Pernyataan ini dapat disajikan dalam teorema berikut.

Teorema 2.12 Misalkan S adalah subgrup normal dari grup G. Koset dari S dalam G

membentuk sebuah grup /G S berorder :G S (Fraleigh 2003).

Misalkan adalah grup bilangan bulat dalam operasi penjumlahan dan misalkan

3 adalah subgrup dari grup yang terdiri atas perkalian 3, maka 3 adalah subgrup

normal dari karena adalah grup komutatif. Misalkan 0 , 1, dan 2 berturut-turut

menyatakan 3 koset yaitu:

0 0 3 {..., 3,0,3,6,...}

1 1 3 {..., 2,1,4,7,...}

2 2 3 {..., 1, 2,5,8,...}

maka grup faktor / 3 adalah {0, 1, 2}. Grup ini biasa disebut dengan ”Bilangan Bulat

Modulo 3” dan dinyatakan dengan 3 . Dengan cara yang sama, untuk setiap bilangan

bulat positif m, terdapat grup faktor m yang disebut dengan bilangan bulat modulo m.

Terkait dengan definisi grup di atas, maka berikut ini diberikan konsep tentang

grup bilangan bulat modulo m. Misalkan m adalah bilangan bulat positif. Untuk

sembarang bilangan bulat x, modulox m dinotasikan dengan modx m , yaitu sisa dari x

dibagi oleh m. Aturan jumlah modulo m (digunakan notasi umum ” + ”) pada bilangan

bulat diartikan sebagai ( ) modx y z z x y m , sedangkan aturan kali modulo

m (digunakan notasi kali pada umumnya) pada integer diartikan sebagai

( ) modxy z z xy m (Guritman 2004).

Misalkan {0, 1, 2,..., ( 1)}m m . Jumlah modulo m merupakan operasi pada

m , dan dapat ditunjukkan bahwa m merupakan grup abelian yang selanjutnya disebut

dengan grup bilangan bulat modulo m. Dalam hal ini, 0 adalah elemen identitas, jika

ma maka invers dari a adalah –a. Di sisi lain, kali modulo m merupakan operasi pada

11

m yang bersifat asosiatif, komutatif dan 1 adalah elemen identitas. Namun tidak semua

elemen m mempunyai invers, khususnya 0. Apapun nilai m maka elemen 0 tidak

mempunyai invers (tidak ada elemen m jika dikalikan 0 menghasilkan 1). Jelas bahwa

m bukan grup terhadap operasi kali modulo m. Dengan demikian, cukup beralasan jika

mendefinisikan himpunan * {0}m m . Pertanyaannya, apakah *m akan menjadi grup

terhadap kali modulo m ?. Jawabannya bisa ya dan bisa juga tidak, hal ini tergantung

pada nilai m. Proposisi berikut merupakan dasar dari konsep ini.

Proposisi 2.13 *m akan merupakan grup terhadap operasi kali jika dan hanya jika m

adalah bilangan prima (Guritman 2004). ■

Sebagai contoh, misalkan *6 {1, 2, 3, 4, 5} . Hal ini dapat ditunjukkan bahwa

*6 bukan merupakan grup karena 2 dan 3 tidak mempunyai invers. Selanjutnya jika p

adalah prima, maka * {1, 2, 3, ..., 1}p p merupakan grup abelian terhadap operasi

kali modulo p dan jika *ps maka invers dari s merupakan solusi dari persamaan

1 modsx p .

Teorema 2.14 Misalkan : G Hf adalah epimorfisma dengan S = Ker( f ), maka

/H G S (Herstein 1964). ■

Teorema 2.14 disebut dengan Teorema Fundamental Homomorfisma yang

menyatakan bahwa setiap imej homomorfik dari G adalah isomorfik dengan grup faktor

dari G. Sebagai contoh, jika diberikan 6 3:f dengan ( ) 2f x x untuk setiap

6x . Fungsi f adalah epimorfisma, karena untuk setiap 32x terdapat 6x

sehingga ( ) 2f x x .

Di sisi lain, 6ker( ) { ( ) 0}f S x f x

6{ 2 0}x x

{0, 3} .

Berdasarkan Teorema 2.14, maka 6 3S .

12

2.5 Ring

Definisi 2.15 Ring R adalah sebuah sistem aljabar yang dibentuk oleh suatu himpunan

tak kosong R dengan dua operasi biner yaitu penjumlahan (+) dan perkalian (.) yang

didefinisikan dalam R , dan memenuhi sifat berikut:

1) (R, +) adalah grup abelian.

2) Operasi perkalian bersifat asosiatif, yaitu a.(b.c) = (a.b).c untuk semua a, b, c R.

3) Operasi perkalian bersifat distributif terhadap penjumlahan.

Untuk setiap a, b, c R memenuhi :

Hukum distributif kiri, yaitu a . (b + c) = (a . b) + (a . c), dan

Hukum distributif kanan, yaitu : (b + c) . a = (b . a) + (c . a) (Fraleigh 2003).

Jenis-jenis ring didefinisikan dengan menambahkan beberapa sifat operasi

perkalian yang lain pada Definisi 2.15 (2). Misalnya, jika operasi perkalian bersifat

komutatif pada ring R, maka R disebut dengan ring komutatif. Jika R mempunyai unsur

identitas di bawah operasi perkalian (dinotasikan 1) dan . 1 1 . ,x x x x R ,

maka R disebut dengan unsur kesatuan. Suatu ring yang hanya mempunyai satu unsur

yaitu 0 maka disebut dengan ring trivial, sedangkan ring yang lebih dari satu unsur

disebut dengan ring nontrivial. Beberapa contoh ring yang tidak asing lagi adalah

, , , dan . Keempat contoh tersebut merupakan ring tak-hingga dan ring

komutatif dengan unsur kesatuan 1, sedangkan untuk ring berhingga dapat diambil m

dengan operasi penjumlahan modulo m, dan operasi perkalian modulo m.

Definisi 2.16 Misalkan R adalah ring komutatif, a R , 0a . Unsur a disebut pembagi

nol jika ada 0b , b R sehingga 0ab . Selanjutnya, suatu ring R dikatakan tidak

memuat pembagi nol jika dan hanya jika 0ab , maka 0a atau 0b (Aliatiningtyas

2002).

Jika R adalah ring dengan unsur kesatuan 1 dan Ra yang memenuhi

1 1 1aa a a untuk setiap 1 Ra , maka a disebut berinvers (invertible) dan 1a

disebut invers dari a. Untuk 0 yang merupakan identitas dari R terhadap operasi

13

penjumlahan tidak berinvers karena andaikata berinvers maka ada 1 Ra sedemikian

sehingga 10 1 0 1a .

Definisi 2.17 Suatu ring yang komutatif dengan unsur kesatuan 1 dan tidak memuat

pembagi nol disebut daerah integral (Aliatiningtyas 2002).

Misalkan, 6 memuat pembagi nol. Ambil 62,3 maka 2 dan 3 disebut

memuat pembagi nol dalam 6 , karena 2.3 = 0 (perkalian dalam modulo 6). Jadi 6

bukan daerah integral. 5 tidak memuat pembagi nol, karena setiap elemen tak-nol

dalam 5 mempunyai invers, yaitu 1.1 = 1, 2.3 = 1, 3.2 = 1 dan 4.4 = 1. Jadi 5

merupakan daerah integral.

Definisi 2.18 Bilangan m disebut karakteristik dari ring R jika m adalah bilangan bulat

positif terkecil sehingga . 0m a untuk setiap a R . Jika tidak ada bilangan seperti ini

maka dikatakan m berkarakteristik 0 (Aliatiningtyas 2002).

Ring berkarakteristik 0, sebab tidak ada bilangan bulat m sehingga . 0m a

untuk setiap a . Pada hanya untuk 0m sehingga 0. 0a untuk setiap a .

Sedangkan m mempunyai karakteristik m .

Teorema 2.19 Di dalam suatu daerah integral D dengan karakteristik tidak nol, maka

karakteristiknya pasti bilangan prima (Gallian 1990). ■

Teorema 2.20 Di dalam suatu daerah integral D dengan karakteristik bilangan prima p ,

maka ( ) p p p untuk setiap elemen , D (Guritman 2004). ■

Definisi 2.21 Suatu ring komutatif ada unsur kesatuan 1 dan setiap unsur tak nolnya

mempunyai invers disebut field (Menezes, 1997).

Dari Definisi 2.21, dapat diamati bahwa definisi field diperoleh dari mengganti

sifat (2) pada Definisi 2.15 dengan pernyataan bahwa R\ 0 adalah grup komutatif

terhadap operasi perkalian. Dengan demikian, misalkan R adalah suatu ring yang

komutatif maka , ,. disebut field jika memenuhi sifat , adalah grup komutatif,

14

{0}, . adalah grup komutatif, dan sifat distributif berlaku ( )a b c ab ac dan

( )a b c ac bc . Contoh field tak-hingga di antaranya adalah , dan .

Sedangkan contoh field berhingga dapat diambil m .

Dari contoh sebelumnya bahwa 5 tidak mamuat pembagi nol, maka 5

merupakan daerah integral. Selanjutnya, karena setiap elemen tak-nol dalam 5

mempunyai invers, yaitu 1.1 = 1, 2.3 = 1, 3.2 = 1 dan 4.4 = 1 maka 5 juga merupakan

field. Hal ini menunjukkan bahwa untuk setiap daerah integral berhingga berkarakteristik

bilangan prima adalah field dan setiap field adalah daerah integral. Hal ini dapat disajikan

dalam teorema berikut.

Teorema 2.22 p adalah field jika dan hanya jika p adalah bilangan prima (Menezes

1997). ■

Sebagaimana di dalam bahasan tentang subgrup, suatu himpunan tak-kosong S di

dalam ring R disebut subring jika S sendiri merupakan ring terhadap operasi yang

dimiliki oleh R. Dalam pembahasan ring secara keseluruhan, sub ring tidak begitu

berperan dibandingkan dengan ideal. Jadi disini lebih menekankan penggunaan ideal dari

pada subring.

Definisi 2.23 Suatu himpunan bagian tak-kosong I dari ring R disebut ideal jika

memenuhi aksioma-aksioma berikut ini.

a. Tertutup terhadap pengurangan, yaitu , ( )a b I a b I .

b. I menyerap produk di dalam R, yaitu a I dan r R ar I dan ra I

(Guritman 2004).

Misalkan adalah ring dan m didefinisikan himpunan semua bilangan bulat

genap, maka m adalah sebuah ideal dari . Hal ini dapat ditunjukkan dengan

menggunakan definisi 2.23. Jelas 0 m . Misalkan ,x y m , maka terdapat ,k l

sehingga x mk dan y ml diperoleh ( )x y mk ml m k l . Jadi ( )m k l m .

Selanjutnya, untuk setiap r , maka . ( ) ( )x r mk r m kr juga elemen dari m .

Dengan demikian, m adalah sebuah ideal dari .

15

Definisi 2.24 Misalkan R adalah ring komutatif dengan unsur kesatuan 1 dan a R .

Suatu himpunan, dilambangkan a , didefinisikan sebagai { }a ra r R merupakan

ideal. Ideal yang demikian disebut ideal utama (Principal Ideal) yang dibangun oleh a

(Guritman 2004).

Contoh, misalkan adalah ring. Ideal dari adalah himpunan semua bilangan

bulat genap yang dibangun oleh 6 adalah 6 {..., 18, 12, 6,0,6,12,18,...} dan

merupakan ideal utama.

Definisi 2.25 Suatu homomorfisma dari ring R ke ring 'R adalah suatu fungsi

':f R R yang memenuhi:

a. ( ) ( ) ( )f a b f a f b , dan

b. ( ) ( ) ( )f ab f a f b , untuk setiap ,a b R .

Jika f surjektif, maka 'R disebut bayangan homomorfik dari R. Kernel dari f

didefinisikan Ker( ) { ( ) 0}f x R f x , dan Range dari f didefinisikan

Ran( ) { ( ) }f f x x R . Jika f adalah homomorfisma yang bijektif, maka f disebut

isomorfisma. Dalam hal ini R dan 'R dikatakan isomorfik, dinotasikan 'R R

(Guritman 2004).

Sebagai ilustrasi, untuk setiap integer m kita dapat mendefinisikan sebuah fungsi

: mf oleh ( ) (mod )f x x m . Fungsi f merupakan homomorfisma ring,

misalkan ,a b maka

( ) ( )(mod )f a b a b m

(mod ) (mod )a m b m

( ) ( )f a f b

dan ( ) ( )(mod )f ab ab m

(mod ) . (mod )a m b m

( ) ( )f a f b

Di sisi lain, kernel dari homomorfisma f adalah

16

ker( ) { ( ) 0}f a f a

{ (mod ) 0}a a m

{ . , }ma a k m k .

m = m .

Teorema 2.26 Misalkan ':f R R homomorfisma ring, maka

ker( ) { ( ) 0}f x R f x merupakan ideal dari R (Gallian 1990). ■

Definisi 2.27 Misalkan R ring dan I ideal dari R. Untuk a R , { }I a i a i I

disebut koset dari I di dalam R. Operasi penjumlahan dan perkalian pada koset-koset

didefinisikan sebagai ( ) ( ) ( )I a I b I a b dan ( )( )I a I b I ab (Guritman

2004).

Dari contoh sebelumnya bahwa 6 {..., 18, 12, 6,0,6,12,18,...} adalah ideal

utama dengan koset-kosetnya adalah

6 0 {..., 18, 12, 6,0,6,12,18,...} 0 ,

6 1 {..., 17, 11, 5,1,7,13,19,...} 1 .

6 2 {..., 16, 10, 4, 2,8,14, 20,...} 2

6 3 {..., 15, 9, 3,3,9,15, 21,...} 3

6 4 {..., 14, 8, 2, 4,10,16, 22,...} 4

6 5 {..., 13, 7, 1,5,11,17,23,...} 5

Jadi himpunan koset-koset yang dibangun oleh 6 adalah

6 {0, 1, 2, 3, 4, 5} .

Teorema 2.28 R I dengan operasi penjumlahan dan operasi perkalian merupakan ring

dan disebut ring faktor dari R oleh I (Guritman 2004). ■

17

Teorema 2.29 Jika I adalah ideal dari ring R, maka fungsi R I adalah ring dan

merupakan bayangan homomorfisma dari R (Herstein 1964). ■

Teorema 2.30 Misalkan R dan 'R adalah masing-masing ring dan ':f R R adalah

epimorfisma dengan K adalah kernel dari f , maka 'R R K (Aliatiningtyas 2002). ■

Misalkan adalah ring seperti pada contoh sebelumnya, ker( ) 6f adalah

ideal, dan / 6 adalah ring faktor (quosen), maka / 6 isomorfik dengan 6 .

Definisi 2.31 Suatu ideal utama I dari suatu ring R dikatakan ideal maksimal jika tidak

ada ideal T dari R sedemikian sehingga I T (Guritman 2004).

Teorema 2.32 Misalkan R adalah ring komutatif dengan unsur kesatuan dan I adalah

ideal dari R, maka I adalah ideal maksimal jika dan hanya jika ring faktor R I adalah

field (Gallian 1990). ■

2.6 Ring Polinomial

Misalkan R adalah ring komutatif dengan unsur kesatuan 1 dan x merupakan

simbol yang tak tetap, maka setiap ekspresi dari 1 10 1 1... m m

m ma a x a x a x disebut

polinomial dalam x dengan koefisien ia R atau lebih sederhana disebut polinomial

dalam x atas R. Ekspresi dari0

mi

ii

a x

disebut terminologi dari polinomial.

Polinomial dalam x dimodelkan dengan simbol ( ), ( ), ( )a x b x f x , dan lain-lain.

Misalkan 1 10 1 1

0

( ) ...m

m m im m i

i

f x a a x a x a x a x

merupakan sembarang

polinomial. Derajat dari polinomial ( )f x yaitu bilangan terbesar m sehingga koefisien

dari mx bukan nol dan dinotasikan dengan deg ( )f x . Polinomial

1 1( ) 0 0 ... 0 ...mf x x x yang semua koefisiennya nol disebut polinomial nol,

dinotasikan dengan ( ) 0f x , dan disebut polinomial tak berderajat. Jika polinomial tak

nol 1 10 1 1( ) ... m m

m mf x a a x a x a x mempunyai derajat m, maka ma disebut

18

koefisien depan. Jika polinomial 0( )f x a , maka ( )f x berderajat nol dan disebut

polinomial konstan. Sembarang polinomial yang koefisien depannya sama dengan 1

disebut polinomial monik.

Misalkan 1 10 1 1( ) ... m m

m mf x a a x a x a x berderajat m dan

10 1( ) ... n

ng x b b x b x berderajat n, maka ( ) ( )f x g x jika dan hanya jika m n dan

i ia b untuk setiap 0,1,...,k m . Operasi penjumlahan dan perkalian dalam ring

polinomial sistemnya sama seperti dalam aljabar elementer. Misalkan fungsi

10 1( ) ... m

mf x a a x a x dan 10 1( ) ... n

ng x b b x b x , maka operasi penjumlahan

didefinisikan

10 1( ) ( ) ... k

kf x g x c c x c x ,

dengan i i ic a b untuk setiap i . Operasi perkalian didefinisikan

10 1( ) ( ) ... m n

m nf x g x c c x c x

dimana 0 1 1 1 1 00

...i

i k i k i i i ik

c a b a b a b a b a b

.

Definisi 2.33 Misalkan R adalah ring komutatif, ring polinomial [ ]R x adalah ring yang

dibentuk oleh himpunan dari semua polinomial-polinomial dalam x yang koefisiennya

ada dalam R dengan operasi penjumlahan polinomial dan operasi perkalian polinomial

(Menezes 1997).

Sebagai contoh, 20 0 0 0 ...x x , 21 1 0 0 ...x x , 20 1 0 ...x x x ,

2 20 0 1 ...x x x , dan sebagainya. Dengan demikian, [ ]R x dapat dinyatakan secara

unik sebagai 20 1 2{ ... }m

ma a x a x a x dimana ia R .

Teorema 2.34 Jika R ring komutatif, maka [ ]R x juga merupakan ring komutatif dan jika

R memiliki unsur kesatuan 1 maka 1 juga merupakan unsur kesatuan dalam [ ]R x . ■

Teorema 2.35 Jika D adalah daerah integral, maka [ ]D x juga daerah integral. ■

19

Teorema 2.36 Jika adalah field, maka [ ]x daerah integral. ■

Karena adalah daerah integral maka [ ]x adalah daerah integral dan karena

5 adalah field maka 5[ ]x adalah daerah integral.

Teorema 2.37 Misalkan adalah field dan ring polinomial [ ]x . Jika

( ), ( ) [ ]f x g x x dengan ( ) 0g x , maka ada polinomial unik ( ), ( ) [ ]q x r x x

sehingga ( ) ( ) ( ) ( )f x q x g x r x dengan ( ) 0r x atau derajat ( ) derajat ( )r x g x

(Fraleigh 2003). ■

Akibat 2.38 Misalkan adalah field. Elemen c dalam adalah dari ( ) [ ]f x x jika

dan hanya jika x c adalah faktor dari ( )f x dalam [ ]x (Gilbert 2004).

Akibat 2.39 Sebuah polinomial berderajat m atas field mempunyai paling banyak m

akar dalam (Gilbert 2004). ■

Definisi 2.40 Misalkan ( ), ( ) [ ]g x h x x keduanya tidak nol, maka Greatest Common

Divisor dari ( ) dan ( )g x h x dinotasikan gcd( ( ), ( ))g x h x adalah polinomial monik

berderajat terbesar dalam [ ]x dimana keduanya membagi ( ) dan ( )g x h x (Menezes

1997).

Definisi 2.41 Suatu polinomial non-konstanta ( ) [ ]f x x dikatakan irreducible atas

[ ]x jika ( )f x tidak dapat dinyatakan sebagai perkalian ( ) ( )g x h x dimana ( )g x dan

( )h x adalah dua polinomial dalam [ ]x yang keduanya berderajat lebih rendah dari

derajat ( )f x (Fraleigh 2003).

Teorema 2.42 Misalkan adalah field dan ( ) [ ]f x x . Setiap ideal dalam [ ]x

adalah ideal utama dan ideal ( )f x adalah ideal maksimal jika dan hanya jika ( )f x

adalah irreducible atas (Gallian 1990). ■

20

2.7 Ruang Vektor

Definisi 2.43 Misalkan adalah field dan misalkan sembarang himpunan V yang

didefinisikan aturan jumlah dan aturan perkalian skalar. V disebut ruang vektor atas

jika memenuhi 10 sifat-sifat berikut:

1. Untuk setiap ,u v V maka terdapat tunggal w V sehingga tertutup terhadap

operasi penjumlahan: u v w .

2. Untuk setiap , ,u v w V berlaku sifat assosiatif: ( ) ( )u v w u v w .

3. Untuk setiap u V , terdapat tunggal identitas 0 V sehingga 0 0u u u .

4. Untuk setiap u V , terdapat tunggal invers v V sehingga 0u v u v

( v u ).

5. Untuk setiap , ,u v w V berlaku sifat komutatif: u v v u .

6. Untuk setiap k , dan setiap u V maka terdapat tunggal v V sehingga tertututp

terhadap operasi perkalian ku v .

7. Untuk setiap k , dan setiap ,u v V maka ( )k u v ku kv .

8. Untuk setiap ,k l , dan setiap u V maka ( )k l u ku lu .

9. Untuk setiap ,k l , dan setiap u V maka ( ) ( )kl u k lu .

10. Untuk setiap u V maka 1u u , dimana 1 adalah unsur identitas dari ( ,.) .

Unsur dari V disebut vektor dan unsur dari disebut skalar (Guritman 2005).

Definisi 2.44 Misalkan V adalah vektor atas field .

1. Vektor 1 2, ,..., mv v v dalam ruang vektor V disebut bebas linear atas field jika

1 1 2 2 ... 0m mc v c v c v mengakibatkan semua skalar 1 2, ,..., mc c c harus sama

dengan nol.

2. Vektor 1 2, ,..., mv v v dalam ruang vektor V disebut bergantung linear atas field jika

terdapat skalar 1 2, ,..., mc c c yang tidak semuanya nol sehingga

1 1 2 2 ... 0m mc v c v c v (Guritman 2005).

Vektor-vektor 1 2, ,..., mv v v akan membentuk basis untuk ruang vektor V jika dan

hanya jika 1 2, ,..., mv v v bebas linear dan merentang V .

21

2.8 Perluasan Field

Definisi 2.45 Field disebut suatu perluasan dari field jika memuat subfield

(Fraleigh 2003).

Definisi 2.46 Suatu elemen c dari perluasan field dari field adalah algebraic atas

jika ( ) 0f c untuk beberapa polinomial tidak-nol ( ) [ ]f x x . Jika c bukan

algebraic atas , maka c disebut dengan transendental atas (Fraleigh 2003).

Misalkan adalah subfield dari field , dan c adalah elemen dalam .

Didefinisikan : [ ]c x dengan aturan pemetaan ( ( )) ( )c f x f c , dimana

0 1( ) ... mmf x a a x a x berderajat m dan 0ma dalam [ ]x . Dengan menggunakan

Definisi 2.25, maka dapat ditunjukkan bahwa c merupakan homomorfisma.

Bagaimana dengan Kernel dari c ?

( ) { ( ) [ ] ( ( )) 0}c cKer f x x f x

= { ( ) [ ] ( ) 0}f x x f c

= 0 1{ ( ) [ ] ... 0}mmf x x a a c a c

Jadi ( )cKer adalah himpunan semua polinomial-polinomial ( )f x atas [ ]x

dan mempunyai akar c . Berdasarkan Teorema 2.26, ( )cKer adalah ideal dari [ ]x dan

setiap ideal dalam [ ]x adalah ideal utama, terdapat ( ) [ ]p x x sehingga

( ) ( )cKer p x = ( ). ( ) ( ) [ ]h x p x h x x , dimana ( )p x adalah polinomial non

konstanta berderajat terkecil, irreducible dan monik dimana c merupakan akar dari

( )p x .

Selanjutnya akan dicari bayangan dari c .

Im( ) { ( ( )) , ( ) [ ]}c c f x f x x

{ ( ) , ( ) [ ]}f c f x x

22

0 1{ ... , ( ) [ ]}mma a c a c f x x

( )c

Dengan demikian, diperoleh : [ ] ( )c x c adalah epimorfisma dengan

ker( ) ( )c p x , dimana ( )p x adalah polinomial berderajat terkecil maka berdasarkan

Teorema 2.30 berlaku [ ] ( ) ( )x f x c .

Karena ( )p x adalah polinomial irreducible, maka berdasarkan Teorema 2.42

( )p x adalah ideal maksimal. Selanjutnya, berdasarkan Teorema 2.32 maka ring faktor

[ ] ( )x p x adalah field. Karena isomorfik, akibatnya ( )c juga field.

Dari uraian di atas, diperoleh teorema berikut ini.

Teorema 2.47 Misalkan adalah field dan ( ) [ ]p x x adalah polinomial irreducible

atas . Jika c merupakan akar dari ( )p x dalam beberapa perluasan maka

[ ] ( ) [ ]x p x c adalah field (Gallian 1990).

Selanjutnya, jika akar c , maka ( )c . Sebaliknya jika c dan c adalah

algebraic maka ( )c merupakan perluasan field dari . Karena [ ] ( ) ( )x p x c ,

maka [ ] ( )x p x juga merupakan perluasan field dari .

Definisi 2.48 Misalkan perluasan field dari field . Jika berdimensi berhingga m

sebagai ruang vektor atas , maka disebut perluasan berhingga berderajat m atas

(Rosdiana 2009).

Definisi 2.49 Suatu perluasan field dari field disebut perluasan tunggal jika

( )c untuk suatu c (Rosdiana 2009).

Teorema 2.50 Misalkan ( )c dengan c algebraic atas . Misalkan derajat dari

perluasan yaitu 1m , maka setiap elemen dari ( )c dapat dinyatakan secara

unik dalam bentuk 1 10 1 1... m

mb b c b c dimana [ ]ib x (Fraleigh 2003). ■

23

Teorema 2.51 Misalkan perluasan field dari field dan c algebraic atas . Jika

derajat dari perluasannya m , maka ( )c adalah ruang vektor atas berdimensi-m

dengan basis 0 1 2 1{ , , , ... , }mc c c c (Fraleigh 2003). ■

Sebagai contoh, bilangan rasional merupakan field tak hingga, dan 2 .

2 bukan merupakan akar dari sembarang polinomial monik berderajat 1 atas ,

karena polinomial 2 [ ]x x . Tetapi 2 merupakan akar dari polinomial 2 2x ,

maka 2 adalah elemen algebraic atas . Karena 2 adalah elemen algebraic atas

, maka polinomial 2 2x merupakan polinomial minimum atas . Jadi derajat dari

perluasan adalah ( 2) 2 dengan basisnya {1, 2}. Dengan demikian, setiap

elemen dalam ( 2) merupakan kombinasi linear dari 1 dan 2 yang berbentuk

2a b dimana ,a b , dinotasikan dengan ( 2) { 2 , }a b a b .

Teorema 2.52 (Eksistensi dan kekhasan finite field)

1. Jika adalah finite field maka terdiri dari mp elemen dengan p adalah bilangan

prima dengan 1m .

2. Untuk setiap prima berorder mp , terdapat finite field yang khas berorder mp . Field ini

dinotasikan dengan ( )mGF p (Menezes 1997). ■

Teorema 2.53 Misalkan ( ) [ ]pf x x adalah polinomial irreducible berderajat m ,

maka [ ] ( )p x f x adalah finite field berorder mp . Operasi penjumlahan polinomial

dan operasi perkalian polinomial dilakukan dalam modulo ( )f x (Menezes 1997). ■

Dua teorema berikut ini merupakan dasar dari algoritme untuk pengecekan

apakah polinomial ( )f x irreducible atau tidak, dan pengecekan apakah polinomial

irreducible ( )f x adalah primitif atau tidak.

Teorema 2.54 Jika p adalah bilangan prima dan m adalah integer positif, maka berlaku:

1). Produk dari semua polinomial irreducible monik dalam [ ]p x yang derajatnya

membagi m atau faktor dari m sama denganmpx x .

24

2). Misalkan ( )f x adalah polinomial berderajat m dalam [ ]p x , maka ( )f x irreducible

atas [ ]p x jika dan hanya jika gcd( ( ), ) 1ipf x x x , untuk setiap 1

2

mi

.

Teorema 2.55 Misalkan p adalah bilangan prima dan misalkan mempunyai faktor-faktor

prima yang berbeda dari 1mp adalah 1 2, ,..., tr r r , maka polinomial ireducible

( ) [ ]pf x x adalah primitif jika dan hanya jika untuk setiap 1 i t berlaku

( 1) / 1(mod ( ))m

ip rx f x .

Definisi 2.56 Misalkan ( )mGF p adalah finite field berkarakteristik p , dan misalkan

( )mc GF p . Polinomial minimum dari c atas p adalah polinomial monik berderajat

terkecil atas [ ]p x dengan c sebagai akarnya (Menezes 1997).

Teorema 2.57 Jika c adalah algebraic atas , maka polinomial minimum ( )m x

atas p mempunyai sifat:

1. ( )m x adalah polnomial irreducible atas [ ]p x .

2. Derajat dari ( )m x adalah pembagi dari m .

3. Misalkan t adalah bilangan bulat terkecil sedemikian sehinggatpc c , maka

1

0

( ) ( )i

tp

i

m x x c

(Menezes 1997).

2.9 Kompleksitas Komputasi

Algoritme aritmetik yang dihasilkan dapat dianalisis dari segi fungsi

kompleksitas waktu (time-complexity function), yaitu sebagai fungsi untuk mengukur

banyaknya operasi dalam suatu algoritme yang mempunyai variabel input n . Yang

dimaksud dengan banyaknya operasi adalah banyaknya operasi dasar (jumlah, kurang,

kali dan bagi) ditambahkan dengan assignment dan perbandingan (ekspresi logika).

Setelah mendefinisikan fungsi ( )f n untuk suatu algoritme, kemudian dengan Tabel O-

Besar kita tentukan order dari f sebagai ukuran efisiensi algoritme yang bersangkutan

(Guritman 2004). Namun demikian, algoritme aritmetik yang dihasilkan dalam penelitian

25

ini tidak terlalu membutuhkan informasi berapa jumlah operasi dasar tersebut, akan

tetapi yang dibutuhkan adalah perkiraan kasar kebutuhan waktu algoritme dan seberapa

cepat fungsi kebutuhan waktu itu tumbuh. Kinerja algoritme akan tampak untuk n yang

sangat besar, bukan pada n yang berukuran kecil. Untuk n yang berukuran kecil maka

perbedaan kecepatannya tidak akan terlihat. Tetapi, bila algoritme tersebut diterapkan

untuk n yang berukuran lebih besar maka perbedaan kecepatannya akan terlihat sangat

berarti.

BAB III

BAHASAN KONSTRUKSI (3 )mGF

Untuk mengonstruksi (3 )mGF dalam penelitian ini dapat dilakukan dengan

mengacu pada konsep perluasan filed pada Bab II bagian 2.8.

Karena 3 adalah bilangan prima, maka berdasarkan Teorema 2.22 3 adalah field

berhingga yang himpunan elemennya {0, 1, 2} dengan operasi penjumlahan dan operasi

perkalian dilakukan dalam modulo 3 dan merupakan ring komutatif. Karena 3 adalah

ring komutatif, maka berdasarkan Teorema 2.34 3[ ]x adalah himpunan dari semua

polinomial dalam x atas 3 dengan operasi penjumlahan dan perkalian polinomial

merupakan ring komutatif yang dinyatakan sebagai

13 0 1 1 3[ ] { ... }m m

m m ix a a x a x a x a . Operasi penjumlahan pada 3[ ]x

bersifat asosiatif, terdapat elemen identitas yaitu polinomial nol, setiap polinomial

3( ) [ ]a x x terdapat polinomial ( )a x sebagai elemen invers, dan merupakan grup

komutatif. Di lain pihak, operasi perkalian pada 3[ ]x bersifat asosiatif, distributif

terhadap operasi penjumlahan.

Misalkan 3( ) [ ]p x x adalah polinomial irreducible berderajat m , jika ada akar

c sehingga ( ) 0p c , maka himpunan semua polinomial yang dibangun oleh ( )p x

merupakan ideal utama ( )p x dan dapat dibentuk ring faktor 3[ ] ( )x p x . Karena

( )p x adalah polinomial irreducible berderajat m , maka berdasarkan Teorema 2.42

( )p x merupakan ideal maksimal. Dengan mengacu pada Teorema 2.32, maka

3[ ] ( )x p x adalah field. Berdasarkan Teorema 2.47, 3 3[ ] ( ) [ ]x p x c merupakan

perluasan dari field 3 . Selanjutnya berdasarkan Teorema 2.50, elemen-elemen 3[ ]c

dapat dinyatakan secara unik dalam bentuk 1 10 1 1 3{ ... }m

m ib b c b c b . Di lain

pihak, berdasarkan Teorema 2.51, 3[ ]c merupakan ruang vektor berdimensi-m atas 3 .

Untuk kepentingan komputasi, maka elemen 3[ ]c dapat direpresentasikan sebagai

vektor terner dari derajat terkecil ke derajat terbesar dalam bentuk 0 1 1[ , , . . . , ]ma a a .

27

Berdasarkan Teorema 2.52, setiap field berhingga (3 )mGF mempunyai elemen

sebanyak pangkat dari bilangan prima berorder 3m . Akibatnya, berdasarkan Teorema

2.53 maka 3(3 ) [ ] ( )mGF x p x . Dari proses di atas, maka (3 )mGF merupakan

himpunan dari semua polinomial berderajat kurang dari m yang dinyatakan dalam

teorema berikut.

Teorema 3.1 Misalkan ( )p x adalah polinomial irredusible berderajat m atas 3 , maka

10 1 1 3(3 ) { ... }m m

m iGF a a x a x a adalah field berhingga.

Bukti :

Diketahui ( )p x adalah polinomial irredusibel berderajat m atas 3 .

Misalkan 3: [ ] (3 )mf x GF adalah fungsi yang didefinisikan

( ( )) ( )(mod ( ))f g x g x p x .

Misalkan 1 2 3( ), ( ) [ ]g x g x x maka f merupakan homomorfisma, karena

1 2 1 2( ( ) ( )) ( ( ) ( ))(mod ( ))f g x g x g x g x p x

1 2( ( ))(mod ( )) ( ( ))(mod ( ))g x p x g x p x

1 2( ( )) ( ( ))f g x f g x

1 2 1 2( ( ) ( )) ( ( ) ( ))(mod ( ))f g x g x g x g x p x

1 2( ( ))(mod ( ))( ( ))(mod ( ))g x p x g x p x

1 2( ( )) ( ( ))f g x f g x

Fungsi f juga surjektif, karena untuk setiap ( )(mod ( )) (3 )mg x p x GF maka terdapat

3( ) [ ]g x x sedemikian sehingga ( ( )) ( )(mod ( ))f g x g x p x .

Kernel dari f adalah 3ker( ) { ( ) [ ] ( ( )) 0}f g x x f g x

3{ ( ) [ ] ( )(mod ( )) 0}g x x g x p x

( )p x

28

Karena fungsi f homomorfisma yang surjektif maka f merupakan epimorfisma

dengan ker( ) ( )f p x . Berdasarkan Teorema Dasar Homomorfisma (Teorema 2.30),

maka 3 3[ ] ( ) [ ] (3 )mx p x c GF . Akibatnya, (3 )mGF adalah field yang elemen-

elemennya merupakan himpunan semua polinomial-polinomial berderajat paling banyak

1m yang dinyatakan secara unik sebagai 10 1 1 3(3 ) { ... }m m

m iGF a a x a x a . ■

Dari keisomorfikan (3 )mGF dengan 3 3[ ] ( ) [ ]x p x c , maka operasi dan

representasi elemen-elemennya dapat dijelaskan sebagai berikut.

Misalkan, diberikan fungsi polinomial 10 1 1 3( ) { ... }m

m ia x a a x a x a dan

10 1 1 3( ) { ... }m

m ib x b b x b x b . Operasi penjumlahan dalam (3 )mGF

didefinisikan sebagai ( ) ( ) ( )c x a x b x 10 1 1... m

mc c x c x dengan

0 0 0( ) mod 3c a b , 1 1 1( ) mod 3c a b , . . . , 1 1 1( ) mod 3m m mc a b . Operasi

perkalian dalam (3 )mGF didefinisikan sebagai perkalian polinomial modulo ( )p x , yaitu

mengambil sisa dari perkalian ( )a x dan ( )b x setelah dibagi dengan ( )p x dinotasikan

( ) ( ) ( ) mod ( )c x a x b x p x .

Elemen (3 )mGF dapat direpresentasikan sebagai bentuk polinomial

10 1 1 3{ ... }m

m ia a x a x a , bentuk basis baku 2 1{1, , , . . . , }mc c c , bentuk

koordinat vektor 0 1 1[ , , . . . , ]ma a a .

Karena (3 )mGF adalah field berhingga, maka himpunan elemen-elemen tak-nol

dari (3 )mGF membentuk grup siklik terhadap operasi perkalian, dinotasikan *(3 )mGF .

Hal ini disajikan dalam teorema berikut ini.

Teorema 3.2 Grup *(3 )mGF merupakan grup siklik terhadap operasi perkalian berorder

3 1m .

Bukti :

Misalkan (3 )mGF .

29

Karena *(3 )mGF berorder 3 1m , maka i paling banyak merupakan 3 1m elemen

berbeda sehingga terdapat r , dimana 1 3 1mr berlaku

r i i ( . ). .r i i i i ( . ) 1r i i

sehingga diperoleh 1r . Jadi r minimum sehingga ( )O r .

Selanjutnya, misalkan r adalah order maksimal dari elemen *(3 )mGF terhadap operasi

perkalian, maka akan berlaku 1 0r , untuk setiap (3 )mGF . Karena setiap

elemen dari (3 )mGF merupakan akar dari polinomial 1r , akibatnya polinomial

berderajat r dapat mempunyai paling banyak r akar.

Karena *(3 )mGF grup siklik terhadap operasi perkalian maka terdapat (3 )mGF ,

dan 3 1mr tetapi 3 1mr , hal ini menunjukkan bahwa 3 1mr . Dengan

demikian, * 2 3 2(3 ) {1, , ,..., }mmGF dan berorder 3 1m .

Terbukti *(3 )mGF siklik. ■

Definisi 3.3 Suatu elemen dalam finite field *(3 )mGF disebut elemen primitif atau

generator dari (3 )mGF , jika * 2 3 2(3 ) {1, , ,..., }mmGF (Ling 2004).

Definisi 3.4 Polinomial irreducible ( ) (3)[ ]f x GF x berderajat m disebut polinomial

primitif dengan akar , jika adalah generator dari (3 )mGF (Menezes 1997).

Berdasarkan sifat dari grup siklik bahwa setiap elemen (3 )mGF memenuhi

polinomial 3 1 1 0m

dan selalu mempunyai akar primitif sebagai pembangun

(3 )mGF . Untuk membangun algoritme aritmetik (3 )mGF dalam penelitian ini

dilakukan dengan mengambil polinomial primitif berderajat m atas 3 yang merupakan

polinomial minimum 0 1( ) ... mmm x a a x a x dimana merupakan akar primitifnya

sedemikian sehingga ( ) 0m . Selanjutnya tentukan basisnya di (3 )mGF sebagai ruang

vektor atas 3 . Misalkan (3 )mGF adalah field berhingga dan adalah elemen primitif

dalam (3 )mGF , maka bentuk basis standar dari polinomial primitifnya adalah

30

2 3 2{1, , , ..., }m

dan setiap elemen (3 )j mGF dapat dinyatakan secara unik

sebagai 10 1 1...j m

ma a x a x dimana 3ia . Untuk kepentingan komputasi,

maka bentuk basis j dapat direpresentasikan sebagai koordinat vektor terner dari

derajat terkecil ke derajat terbesar dalam bentuk 0 1 1[ , , . . . , ]jma a a .

Pengambilan polinomial primitif dalam penelitian ini dapat dilakukan secara

komputasi menggunakan Software Maple 11 dengan langkah-langkah sebagai berikut.

Pertama-tama tes apakah polinomial irreducible atau tidak. Selanjutnya, tes polinomial

irreducible primitif atau tidak. Adapun Algoritme 3.1 dan Algoritme 3.2 merupakan

algoritme rutin yang akan digunakan pada Algoritme 3.3 dan Algoritme 3.4.

Algoritme 3.1

Deskripsi : Prosedur untuk menghitung Ax mod BInput : Vektor 0 1[ , , . . . , ]sA a a a , vektor 0 1[ , , . . . , b ]tB b b , dan integer x

Output : modxH A B

1. Ubah x dalam basis 22. Isi G = H, H = [1]3. Jika X1 = 1, maka H = G4. Untuk i mulai 2 sampai panjang vektor X, lakukan

4.1 Hitung K = perkalian G dengan G4.2 Hitung G = sisa hasil bagi K dengan B4.3 Jika Xi = 1, maka lakukan

4.3.1 Hitung L = perkalian H dengan G4.3.2 Hitung H = sisa hasil bagi L dengan B

5. Return(H)

Algoritme 3.2

Deskripsi : Prosedur untuk menghitung Gcd dari vektor A dan vektor BInput : Vektor 0 1[ , , . . . , ]sA a a a , vektor 0 1[ , , . . . , b ]tB b b

Output : ( , )RA Gcd A B

1. Hitung a = panjang vektor A dan b = panjang vektor B2. Isi RA = A, RB = B3. Jika a < b, maka RA = B dan RB = A4. Jika RB = [0], maka return(RA)5. Hitung L = sisa hasil bagi RA dengan RB6. Isi RA = RB dan RB = L7. Untuk i selama RB ≠ [0], maka lakukan berulang-ulang

7.1 Hitung L = sisa hasil bagi RA dengan RB

31

7.2 Isi RA = RB dan RB = L8. Return(RA)

Vektor terner yang dibangkitkan, cek apakah irreducible atau tidak menggunakan

Algoritme 3.3. Algoritme ini didasarkan pada Teorema 2.55.

.Algoritme 3.3

Deskripsi : Prosedur untuk memeriksa polinomial irreducible atau tidakInput : Vektor 0 1[ , , . . . , ]sA a a a

Output : Apakah irreducible ?

1. Hitung a = panjang vektor A - 1

2. Hitung m =2

m

3. Isi [0,1]W

4. Untuk i dari 1 sampai m, lakukan

4.1 Hitung modxW A B menggunakan Algoritme 3.14.2 Hitung U = jumlah vektor W dengan [0, 2]4.3 Hitung H = Gcd(A,B) menggunakan Algoritme 3.24.4 Hitung h = panjang vektor H

4.4.1 Jika h > 1, maka return(false)5. Return(true)

Selanjutnya, cek apakah primitif atau tidak dengan menggunakan Algoritme 3.4.

Algoritme ini didasarkan pada Teorema 2.56.

Algoritme 3.4

Deskripsi : Prosedur untuk memeriksa polinomial irreducible adalah primitifInput : Vektor 0 1[ , , . . . , ]sA a a a

Output : Apakah polinomial primitif ?

1. Hitung m = panjang vektor A – 1

2. Hitung 3 1mh 3. Hitung F = faktor prima dari h4. Hitung a = panjang vektor F5. Untuk i dari 1 sampai a , lakukan

5.1 Hitung / ik h F

5.2 Hitung H = [0, 1]k mod A menggunakan Algoritme 3.15.3 Jika H = [1], maka return(false)

6. Return(true)

32

Pembangkitan vektor terner yang primitif dalam penelitian ini dapat dilakukan

dengan memilih vektor yang bersuku kecil, yaitu vektor bersuku dua dengan

menggunakan Algoritme 3.5, vektor bersuku tiga dengan menggunakan Algoritme 3.6,

vektor bersuku empat dengan menggunakan Algoritme 3.7.

Algoritme 3.5

Deskripsi : Prosedur untuk membangkitkan polinomial primitif bersuku duaInput : Bilangan bulat positif mOutput : Vektor primitif bersuku dua Y

1. Untuk i dari 1 sampai 4, lakukan1.1 Jika (i mod 3) 0, maka

1.1 Ubah X = dari desimal ke vektor terner1.2 Hitung x = panjang elemen X1.3 Isi vektor Y = [X, 0...(m - x), 1]1.4 T = Test irreducible Y menggunakan Algoritme 3.3

1.4 Jika T = true, maka1.4.1 U = Test Primitif Y menggunakan Algoritme 3.41.4.2 Jika U = true, maka

2. Return(Y)

Jika vektor primitif bersuku dua tidak ada maka vektor primitifnya dapat dipilih

dari vektor primitif bersuku tiga dengan menggunakan Algoritme 3.6.

Algoritme 3.6

Deskripsi : Prosedur untuk membangkitkan polinomial primitif bersuku tigaInput : Bilangan bulat positif m dan floor((m+1)/2)Output : Vektor primitif bersuku tiga Y

1. Untuk i dari 1 sampai 2, lakukan1.1 Untuk j dari 1 sampai 2, lakukan

1.1.1 T = Test irreducible menggunakan Algoritme 3.31.1.2 Jika T = true, maka

U = Test Primitif menggunakan Algoritme 3.41.1.3 Jika U = true, maka Return(Y)

1.2 Untuk k dari 1 sampai (m-2), lakukan1.1.1 T = Test irreducible menggunakan Algoritme 3.31.1.2 Jika T = true, maka

U = Test Primitif menggunakan Algoritme 3.41.1.3 Jika U = true, maka Return(Y)

2. Return(Y)

33

Jika vektor primitif bersuku tiga tidak ada maka vektor primitifnya dapat dipilih

dari vektor primitif bersuku empat atau lebih dengan menggunakan Algoritme 3.7.

Algoritme 3.7

Deskripsi : Prosedur untuk membangkitkan polinomial primitif bersuku tigaInput : Bilangan bulat positif m dan floor((m+1)/2)Output : Vektor primitif bersuku tiga Y

1. Untuk i dari 1 sampai 2, lakukan1.1 Untuk j dari 1 sampai 2, lakukan

1.1.1 Untuk k dari 1 sampai 2, lakukan1.1.1.1 T = Test irreducible menggunakan Algoritme 3.31.1.1.2 Jika T = true, maka

U = Test Primitif menggunakan Algoritme 3.41.1.1.3 Jika U = true, maka Return(Y)

1.1.2 Untuk l dari 1 sampai (m-3), lakukan1.1.2.1 T = Test irreducible menggunakan Algoritme 3.31.1.2.2 Jika T = true, maka

U = Test Primitif menggunakan Algoritme 3.41.1.2.3 Jika U = true, maka Return(Y)

1.1.2 Untuk l dari 1 sampai (m-3), lakukan1.1.2.1 T = Test irreducible menggunakan Algoritme 3.31.1.2.2 Jika T = true, maka

U = Test Primitif menggunakan Algoritme 3.41.1.2.3 Jika U = true, maka Return(Y)

2. Return(Y)

Pemilihan polinomial primitif bersuku kecil dimaksudkan agar dapat

mempercepat proses kalkulasi aritmetik field (3 )mGF . Polinomial primitif bersuku kecil

yang digunakan dalam penelitian ini dapat dilihat pada Lampiran II. Selanjutnya, untuk

kepentingan komputasi polinomial primitif yang dipilih direpresentasikan sebagai vektor

terner yang dipilih akan disimpan dalam basis data. Untuk menggunakan basis data

tersebut cukup dipanggil derajat tertinggi.

Sebagai contoh, misalkan pilih 3m . Untuk membangun field 3(3 )GF dapat

dikerjakan dari 3 , karena 3 merupakan subfield dari 3(3 )GF . Ambil polinomial

primitif 33( ) 2 1 [ ]m x x x x yang merupakan polinomial minimum berderajat 3

dimana adalah akar primitifnya. Periksa apakah akar merupakan algebraic atau

tidak.

34

Ambil (3)GF sedemikian sehingga ( ) 0m .

Untuk 0 , maka 3(0) 0 2.0 1 1m . Jadi 0 bukan akar dari ( )m x .

1 , maka 3(1) 1 2.1 1 1m . Jadi 1 bukan akar dari ( )m x .

2 , maka 3(2) 2 2.2 1 1m . Jadi 2 bukan akar dari ( )m x .

Karena untuk 0 , 1 , dan 2 bukan akar dari polinomial ( )m x , ini

menunjukkan bahwa merupakan algebraic. Pilih akar pada perluasan field 3

sedemikian sehingga ( ) 0m mengakibatkan 3 3( ) 2 1 0 2m .

Dengan 3 2 dapat digunakan untuk membangun perluasan field yang memuat

semua akar-akar dari polinomial 3( ) [ ]m x x , sehingga diperoleh

4 3 2 2 , 5 4 22 2 , 6 5 2 1 ,

7 6 22 2 2 , 8 7 22 2 , 9 8 1 ,

10 9 2 , . . . , 25 24 22 1 , 26 25 0 1 .

Selanjutnya, karena polinomial ( )m x berderajat 3 maka 2{1, , } bebas linear

atas 3( ) . Artinya 2{1, , } merupakan basis dari 3( ) , sehingga 3( )

merupakan ruang vektor berdimensi 3 atas 3 . Selanjutnya, subfield dari 3(3 )GF terdiri

dari 3 dan 3(3 )GF dengan masing-masing ordernya adalah 3 dan 27. Elemen-elemen

dari subfield yang berorder 3 adalah {0, 1, 2}, sedangkan elemen-elemen subfield yang

berorder 27 adalah field itu sendiri yaitu 25{0, 1, , ..., } dengan basisnya

25{1, , ..., } . Jadi 3 25(3 ) 27 {0, 1, , ..., }GF dengan basisnya adalah

25{0, 1, , ..., } dan jika elemen nol dikeluarkan maka 3(3 )GF akan membentuk grup

siklik yang dibangkitkan oleh , dinotasikan 3(3 )GF . Jadi

3 25(3 ) 26 {1, , ..., }GF dengan basisnya adalah 25{1, , ..., } .

Dengan demikian, himpunan semua polinomial-polinomial berderajat kurang dari

3 atas 3 yang dibangun oleh polinomial primitif 33( ) 2 1 [ ]m x x x x adalah

35

2 2 2

2 2 2 2 2 2

2 2 2 2 2 2 2

2 2

{0, 1, 2, , 1, 2, 2 , 2 1, 2 2, , 1, 2,

, 2 , 1, 2, 2 1, 2 2,

2 , 2 1, 2 2, 2 , 2 1, 2 2, 2 2 ,

2 2 1, 2 2 2}

Dengan mengambil 3 , dan 2 9 , maka diperoleh hubungan antara

representasi elemen primitif, representasi basis polinomial, representasi vektor terner,

dan representasi integer dapat dilihat pada Tabel 3.1.

Tabel 3.1 Galois Field dari 3(3 )GF

NoElemenPrimitif

RepresentasiBasis

VektorTerner

RepresentasiInteger

123456789101112131415161718192021222324252627

0α0 = α26

α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

01αα2

α + 2α2 + 2α

2α2 + α + 2α2 + α + 1α2 + 2α + 2

2α2 + 2α + 1α2 + α

α2 + α + 2α2 + 2

22α2α2

2α + 12α2 + α

α2 + 2α + 12α2 + 2α + 22α2 + α + 1α2 + 12α + 2

2α2 + 2α2α2 + 2α + 1

2α2 + 1

[0, 0, 0][1, 0, 0][0, 1, 0][0, 0, 1][1, 2, 0][0, 2, 1][2, 1, 2][1, 1, 1][2, 2, 1][2, 0, 2][1, 1, 0][0, 1, 1][2, 1, 1][2, 0, 1][2, 0, 0][0, 2, 0][0, 0, 2][1, 2, 0][0, 1, 2][1, 2, 1][2, 2, 2][1, 1, 2][1, 0, 1][2, 2, 0][0, 2, 2][1, 2, 2][1, 0, 2]

01395152313172041214112618720162622108242519

BAB IV

BAHASAN ALGORITME ARITMETIK (3 )mGF

Telah dijelaskan sebelumnya bahwa dalam mengonstruksi field (3 )mGF

diperoleh dari perluasan field 3 dengan memilih polinomial primitif berderajat m atas

3 yang dalam hal ini dapat dilihat pada Tebel 3.1, yaitu representasi basis polinomial

dan representasi vektor terner. Operasi penjumlahan disini menggunakan operasi jumlah

modulo 3, sedangkan operasi perkalian sama seperti perkalian pada umumnya tetapi pada

saat penjumlahannya tetap menggunakan operasi jumlah modulo 3.

Contoh :

1. Operasi Penjumlahan

2

2

2

1 2 2 1 2 2

1 0 2 1 2

2 2 1 2 2

2. Operasi Perkalian

2 2 2 3 4 2

2 3 4

1 2 2

1 0 2 (1+2 +2 )(1+2 ) = 2 1+2 +2

2 1 1 = 1+2 + + +

2 30 0 0 (2 + 2 ) (mod +2 1)

1 2 2

1 2 1 1 1

Berikut ini akan dijelaskan beberapa algoritma yang berkaitan dalam

mengkonstruksi algoritma aritmetik atas (3 )mGF dengan menggunakan Software

MAPLE 11. Algoritme aritmetik yang dihasilkan akan dianalisis untuk mengukur kinerja

algoritme berdasarkan fungsi kompleksitas, yaitu sebagai fungsi untuk mengukur

banyaknya operasi dalam suatu algoritme yang mempunyai variabel input n

ditambahkan dengan assignment dan operasi perbandingan (ekspresi logika).

37

Proses kalkulasi aritmetik dalam penelitian ini akan menggunakan Algoritme

Reduksi Nol (Algoritme 4.1), yaitu sebagai algoritme rutin untuk mereduksi elemen nol

yang tidak berpengaruh dalam representasi vektor. Algoritme Reduksi Nol ini akan

digunakan oleh algoritme-algoritme pada operasi dasar, yaitu operasi penjumlahan dan

operasi perkalian sehingga dapat menghemat pemakaian ruang yang besar dan jumlah

operasi.

Misalkan, diberikan polinomial 10 3( ) 2a x x x x . Ini menunjukkan bahwa

polinomial primitif ( )a x memiliki derajat 10 sehingga

10 3 4 5 6 7 8 91 2 2 0 0 0 0 0 0x x x x x x x x x dan jika ditulis dalam bentuk vektor

maka ( ) [1,2,0, 2,0,0,0,0,0]A x . Jadi dengan menggunakan Algoritme Reduksi Nol

maka vektor ( ) [1, 2,0,2]A x .

Algoritme 4.1

Deskripsi : Prosedur untuk mereduksi nol pada posisi sebelah kananInput : Vektor T dan Bilangan bulat positif tOutput : Vektor R

1. T = R, t = banyaknya elemen T2. Untuk j selama [ ] 0T t dan 1t , lakukan

2.1 Reduksi nol pada vektor T2.2 t = t - 1

3. Return(”R”)

Banyaknya operasi dalam Algoritme 4.1 melibatkan rata-rata 2n operasi,

dimana n adalah panjang vektor T.

4.1 Operasi Penjumlahan

Sebagaimana dijelaskan sebelumnya, representasi yang digunakan disini adalah

representasi basis polinomial yang dikonversi ke dalam representasi vektor terner dari

derajat terkecil ke derajat yang terbesar. Misalkan fungsi polinomial

0 1( ) ... mmf x a a x a x dan fungsi polinomial 0 1( ) ... m

mg x b b x b x . Fungsi

polinomial ini akan direpresentasikan sebagai vektor terner, yaitu 0 1[ , , ..., ]mA a a a

38

dan 0 1[ , , ..., ]mB b b b , maka operasi penjumlahan vektor A dan vektor B didefinisikan

sebagai

0 0 1 1([( ) mod 3, ( ) mod 3,..., ( ) mod 3])m mA B a b a b a b .

Algoritme 4.2

Deskripsi : Prosedur untuk menjumlahkan dua vektorInput : Vektor 1 2 1 2[ , , ..., ], vektor [ , , ..., ]s tA a a a B b b b , dan integer positif m.

Output : 1 2Vektor [ , , ..., ]rC A B c c c

1. Hitung s, dan t yaitu banyaknya elemen vektor A dan B2. Jika s t , maka hitung

1.1 0 0 1 1([( ) mod 3, ( ) mod 3,..., ( ) mod 3])s tA B a b a b a b

1.2 Reduksi Nol menggunakan Algoritme 4.12. Jika s t , maka hitung

2.1 1 1 2 2( ) mod3, ( ) mod 3 ,..., mod3ta b a b b

Lainnya, 1 1 2 2( ) mod3, ( ) mod3 ,..., mod 3sa b a b a

3. Return(“C”)

Banyaknya operasi dalam Algoritme 4.2 melibatkan rata-rata menggunakan n

modulo 3. Jadi fungsi kompleksitasnya adalah ( )O n .

Sebagai contoh, misalkan 3m dimana polinomial primitifnya disimpan dalam

basis data DatT[m] = [2, 1] dan diberikan fungsi polinomial 2( ) 1 2a x x x dan

2( ) 2b x x x . Kedua polinomial tersebut akan direpresentasikan sebagai vektor

(1, 1, 2)A dan vektor (0, 2, 1)B . Karena banyak elemen vektor A sama dengan

banyaknya elemen pada vektor B, maka penjumlahan vektor A dan vektor B dengan

menggunakan Algoritme 4.9 adalah

C A B

([(1 0) mod3, (1 2) mod3, (2 1) mod3])C .

([1, 0, 0])C .

Elemen nol pada posisi paling kanan direduksi menggunakan Algoritme 4.8,

maka vektor [1]C A B . Jika vektor [1]C dikembalikan ke representasi

polinomial, maka fungsi polinomialnya adalah 0( ) 1 1c x x .

39

4.2 Operasi Perkalian

Operasi perkalian dalam (3 )mGF dilakukan dalam perkalian polinomial biasa

kemudian mengambil sisa dari hasil pembagian dengan polinomial primitif ( )p x .

Operasi perkalian dalam penelitian ini menggunakan Algoritme 4.5. Jika Algoritme 4.5

diimplementasikan pada program Software MAPLE 11 maka proses pertama yang

dilakukan adalah mengecek apakah kedua vektor tersebut mempunyai elemen yang

sama? Jika banyaknya elemen vektor kedua kurang dari banyaknya elemen vektor

pertama maka vektor tersebut saling ditukarkan. Hal ini bertujuan agar tidak

menggunakan ruang yang besar dalam kalkulasi aritmetik dalam komputasi. Selanjutnya,

gunakan algoritme rutin dalam operasi kelipatan vektor, yaitu Algoritme 4.3, yaitu untuk

mengalikan kelipatan vektor. Proses kedua menggunakan algoritme rutin dalam operasi

geser satu, yaitu untuk menggeser satu langkah dalam setiap perkalian elemen-

elemennya menggunakan Algoritme 4.4. Kemudian menjumlahkan proses pertama

dengan proses kedua secara rekursif menggunakan Algoritme 4.2.

Algoritme 4.3

Deskripsi : Prosedur untuk mengalikan kelipatan vektorInput : Vektor 1 2[ , , ..., ]sA a a a , dan bilangan bulat positif {0,1,2}m .

Output : vektor R

1. Jika m = 0, maka return([0])2. Jika m = 1, maka return(A), selainnya R = Negatifkan vektor A3. Return(”R”).

Banyaknya operasi dalam Algoritme 4.3 melibatkan rata-rata menggunakan n

operasi. Jadi fungsi kompleksitasnya adalah ( )O n .

Algoritme 4.4

Deskripsi : Prosedur untuk menggeser satu langkahInput : Vektor 1 2[ , , ..., ]sA a a a , dan bilangan bulat positif m.

Output : vektor R

1. L = vektor dalam basis data2. t = banyaknya elemen vektor A3. Jika t m maka isi vektor R dengan 0 sebanyak t selainya

3.1 Isi R dengan 0 dan mereduksi elemen ke-m pada vektor A

40

3.2 Reduksi Nol dengan menggunakan Algoritme 4.13.3 Kalikan vektor L dengan elemen ke-t pada vektor A menggunakan

Algoritme 4.133.4 Jumlahkan hasil langkah 3.2 dengan langkah 3.3 menggunakan

Algoritme 4.24. Return(”R”).

Banyaknya operasi dalam Algoritme 4.4 melibatkan rata-rata menggunakan .n n

operasi. Jadi fungsi kompleksitas waktunya adalah 2( )O n .

Algoritme 4.5

Deskripsi : Prosedur untuk menghitung perkalian dua vektorInput : Vektor 1 2 1 2[ , , ..., ], vektor [ , , ..., ]s tA a a a B b b b , dan bilangan bulat

positif m.Output : 1 2Vektor . [ , , ..., ]rR A B c c c

1. Vektor S = A, vektor T = B, s, dan t masing-masing banyaknya elemenvektor A dan B

2. Jika s t maka lakukan2.1 Tukarkan vektor A dengan vektor B2.2 Hitung perkalian vektor B dengan elemen 1 vektor A menggunakan

Algoritme 4.32.3 Untuk j dari 1 sampai ( 1)s , lakukan

2.3.1 Geser vektor satu langkah menggunakan Algoritme 4.42.3.2 Hitung perkalian vektor pada langkah 2.3.1 dengan elemen

(j+1) vektor A menggunakan Algoritme 4.32.3.3 Hitung adisi langkah 2.2 dengan langkah 2.3.2 menggunakan

Algoritme 4.23. Return(”R”).

Banyaknya operasi dalam Algoritme 4.5 melibatkan rata-rata menggunakan .n n

operasi. Jadi fungsi kompleksitas waktunya adalah 2( )O n .

Sebagai contoh, misalkan 3m dimana polinomial primitifnya disimpan dalam

basis data DatT[m] = [2, 1] dan diberikan fungsi polinomial 2( ) 2 2a x x x dan

2( ) 2 2 2b x x x . Kedua polinomial tersebut akan direpresentasikan sebagai

vektor [2,1,2] dan vektor [2,2,2]A B . Tentukan vektor R dengan menggunakan

algoritme 4.3, yaitu kalikan vektor B dengan elemen pertama pada vektor A yang

hasilnya dalah 1 [1, 1, 1]R . Proses kedua menentukan vektor T dengan menggunakan

Algoritme 4.2, yaitu T1 = [1, 1, 2] lalu kalikan elemen ke-2 pada vektor A menghasilkan

41

vektor V1 = [ 1, 1, 2] kemudian jumlahkan dengan vektor R1 menggunakan Algoritme

4.9 menghasilkan vektor R2 = [2, 2]. Selanjutnya ulangi proses kedua untuk memperoleh

vektor T2 = [1, 0, 1] lalu kalikan elemen ke-3 pada vektor A menghasilkan vektor V2 =

[ 2, 0, 2] kemudian jumlahkan dengan vektor R2 menggunakan Algoritme 4.3

menghasilkan vektor 3 [1, 2, 2]R . Dengan demikian diperoleh hasil perkalian vektor A

dan vektor B yaitu 3 [1, 2, 2]R . Jika vektor 3 [1, 2, 2]R dikembalikan ke representasi

polinomial maka fungsi polinomialnya adalah 2( ) 1 2 2r x x x .

4.3 Operasi Invers

Misalkan sembarang fungsi polinomial 0 1( ) ... ttf x a a x a x , dan fungsi

polinomial primitif ( )p x berderajat m. Representasikan fungsi ( )f x sebagai vektor

terner 0 1[ , , ..., ]tA a a a , maka untuk menentukan invers dari vektor A dapat

menggunakan Algoritme 4.7. Jika Algoritme 4.7 diimplementasikan pada program

Software MAPLE 11 maka proses pertama adalah Negatifkan vektor dalam DatT(m)

yang berfungsi sebagai polinomial primitif menggunakan Algoritme 1.4 (Lampiran I),

jika elemen A adalah nol maka vektor A tidak mempunyai invers, dan jika banyak

elemen vektor A adalah 1 maka inversnya adalah vektor itu sendiri. Proses kedua adalah

isi vektor RA, vektor RB = T, vektor QA = [0], dan vektor QB = [1] yang kemudian

gunakan Algoritme 4.6 untuk menentukan vektor L, yaitu membagi vektor RA dengan

vektor RB. Proses selanjutnya adalah selama RB = op(2, L) tidak nol, maka lakukan

secara berulang-ulang dengan menggunakan algoritme operasi rutin yaitu berturut-turut

Algoritme 1.8, dan Algoritme 1.4 (Lampiran I), yang kemudian jumlahkan dengan

menggunakan Algoritme 4.2. Pada proses terakhir gunakan Algoritma 4.3 untuk

menentukan vektor H.

Algoritme 4.6

Deskripsi : Prosedur untuk pembagian vektor tanpa moduloInput : Vektor 1 2[ , , ..., ]tT a a a , 1 2[ , , ..., ]sS b b b

Output : Vektor / [[ ],[ ]]H A B Q R

1. R = A, Q = [0]2. r, s masing-masing banyaknya elemen vektor T dan S3. g = elemen ke-s pada vektor S

42

4. Jika s = 1, maka4.1 Q = kalikan vektor R dengan setiap elemen pada vektor S

menggunakan Algoritme 4.34.2 R = [0]4.3 Return([Q, R])

5. Untuk i selama r s lakukan5.1 Hitung k r s , t = elemen ke-r pada R3.2 Hitung ( . ) mod 3h t g

3.3 Jika k = 0, maka3.3.1 K = Kalikan S dengan h menggunakan Algoritme 4.33.3.2 Q = Jumlahkan hasil bagi Q dengan vektor h menggunakan

Algoritme 4.2. Selainnya,3.3.3 H = Kalikan S dengan h menggunakan Algoritme 4.33.3.4 K = Isi 0 depan elemen H sebanyak k3.3.5 Q = Jumlahkan Q dengan [0...k, h] gunakan Algoritme 4.2

6. K = Negatifkan vektor K7. R = Jumlahkan K dengan R menggunakan Algoritme 4.38. r = banyaknya elemen R9. Return(”[Q, R]”)

Banyaknya operasi dalam Algoritme 4.6 melibatkan rata-rata menggunakan .n n

operasi. Jadi fungsi kompleksitas waktunya adalah 2( )O n .

Algoritme 4.7

Deskripsi : Prosedur untuk menentukan invers vektorInput : Vektor 1 2[ , , ..., ]tT a a a , dan integer positif m.

Output : 11 2Vektor [ , , ..., ]rH A c c c

1. Negatifkan vektor S2. s = banyaknya elemen S, t = banyaknya elemen T3. Jika T = [0], maka return(false)4. Jika t = 1, maka return(T)5. RA = [S, 0...(m - t), 1], RB = T, QA = [0], QB = [1]6. Hitung pembagian vektor RA dengan RB menggunakan Algoritme 4.67. RA = RB, RB = elemen kedua pada langkah 68. Untuk i selama A tidak nol, maka lakukan langkah berikut berulang-ulang

8.1 Tmp = QA, QA = QB8.2 Hitung perkalian QB dengan elemen pertama pada langkah 6

menggunakan Algoritme 1.88.3 Negatifkan pada langkah 8.28.4 Hitung penjumlahan Tmp dengan langkah 8.3 menggunakan

Algoritme 4.28.5 Hitung pembagian RA dengan RB menggunakan Algoritme 4.69.6 RA = RB, RB = elemen kedua pada hasil langkah 8.5

9. Hitung perkalian hasil langkah 8.4 dengan RA gunakan Algoritme 4.310. Return(”H”)

43

Banyaknya operasi dalam Algoritme 4.7 melibatkan rata-rata menggunakan .n n

operasi. Jadi fungsi kompleksitas waktunya adalah 2( )O n .

Sebagai contoh, misalkan 3m dimana polinomial primitifnya disimpan dalam

basis data DatT[m] = [2, 1] dan diberikan fungsi polinomial 2( ) 1 2t x x x yang

direpresentasikan menjadi vektor terner yaitu [1, 2, 1]T , Gunakan Algoritma 1.4

untuk menegatifkan vektor DatT(m), yaitu S = [1, 2]. Selanjutnya, isi vektor RA dengan

vektor QA = [0], dan vektor QB =[1], yaitu [1, 2,0,1]RA dan vektor RB = T yang

kemudian gunakan Algoritme 4.6 untuk menentukan vektor L, yaitu membagi vektor RA

dengan vektor RB, outputnya adalah vektor L = [[1, 1], [0, 2]], isi RA = [1, 2, 1], RB =

[0, 2], karena [0]RB maka lakukan berulang-ulang sampai [0]RB . Isi Tmp = [0],

QB = [1], gunakan Algoritma 1.8 untuk mengalikan vektor QB dengan vektor RA, yaitu

H = [1, 1].

Kemudian gunakan Algoritme 1.4 untuk menegatifkan vektor H, yaitu R = [2, 2],

selanjutnya gunakan Algoritme 4.2 untuk menjumlahkan Tmp dan R, yaitu QB = [2, 2].

Gunakan Algoritme 4.6 untuk menentukan vektor L, yaitu membagi vektor RA dengan

vektor RB, outputnya adalah vektor L = [[1, 2], [2]], jadi RA = [0, 2] dan RB = [1].

Karena [0]RB , maka ulangi langkah-langkah sebelumnya sampai mendapatkan

[0]RB . Dengan demikian, jika [0]RB maka gunakan Algoritme 4.3 untuk

menentukan [2, 0, 2]H yang dalam hal ini vektor H merupakan invers dari vektor T.

Jika vektor [2, 0, 2]H direpresentasikan ke bentuk polinomial maka polinomialnya

adalah 2( ) 2 2h x x

4.4 Operasi Pembagian

Untuk menghitung operasi pembagian dalam penelitian ini dapat dilakukan

melalui proses menggunakan Algoritme 4.7 untuk menentukan invers vektor B kemudian

kalikan dengan vektor A menggunkan Algoritme 4.5.

Algoritme 4.8

Deskripsi : Prosedur untuk menghitung pembagian vektor

44

Input : Vektor 1 2[ , , ..., ]tA a a a , vektor 1 2[ , , ..., ]sB b b b dan integer positif m.

Output : 1 2Vektor / [ , , ..., ]rC A B c c c

1. Hitung invers vektor B menggunakan Algoritme 4.72. Hitung perkalian vektor A dengan langkah 1 menggunakan Algoritme 4.53. Return(”C”)

Banyaknya operasi dalam Algoritme 4.8 melibatkan rata-rata menggunakan . .n n n

operasi. Jadi fungsi kompleksitas waktunya adalah 3( )O n .

Sebagai contoh, misalkan 3m dimana polinomial primitifnya disimpan dalam

basis data DatT[m] = [2, 1] dan diberikan fungsi polinomial 2( ) 2 2a x x x dan

2( ) 2 2 2b x x x . Kedua polinomial tersebut akan direpresentasikan sebagai

vektor [2,1,2] dan vektor [2,2,2]A B . Untuk menghitung pembagian

vektor [2,1,2] dan vektor [2,2,2]A B , langkah pertama adalah menentukan invers

dari vektor B dengan menggunakan Algoritme 4.7, yaitu iB = [2, 2, 1] kemudian

mengalikan vektor A dengan iB menggunakan Algoritme 4.5 sehingga output pembagian

vektor A dengan vektor B adalah [2, 0, 1]. Jika dikembalikan dalam bentuk polinomial,

maka fungsi polinomialnya adalah 22C .

4.5 Operasi Exponensial

Aritmetik dalam operasi exponen berfungsi untuk mengalikan dua fungsi

polinomial atau lebih. Misalkan sembarang fungsi polinomial 0 1( ) ... ssf x a a x a x

direpresentasikan dalam vektor 1 2[ , ,..., ]sA a a a dan barisan basis dua

0 1[ , , ..., ]ik k k k , dimana [0,1]i , serta fungsi polinomial primitif ( )p x berderajat m.

Derajat maksimal dari fungsi polinomial di sini berlaku sebagai modulus yaitu (3 1)m ,

sedangkan exponennya merupakan barisan basis dua yang diperoleh dari nilai input i

yang dimoduluskan dengan menggunakan algoritme operasi rutin, yaitu Algoritme 4.9.

Proses selanjutnya, jika nilai yang dimoduluskan (3 1)m lebih dari atau sama

dengan nol, maka konversi ke dalam basis 2. Jika hasil konversinya sama dengan 1,

maka H = A. Untuk hasil konversi mulai dari 2, maka gunakan Algoritme 4.12 untuk

menentukan perkalian A dengan A yaitu vektor G dan jika elemen ke-i pada konversi

45

sama dengan 1 maka gunakan Algoritme 4.5 untuk menentukan perkalian H dengan G

dan jika nilai yang dimoduluskan (3 1)m adalah negatif maka konversi ke dalam basis 2

lalu gunakan Algoritme 4.7 untuk menentukan invers A, isi H = [1]. Jika elemen pertama

hasl konversi sama dengan 1, maka H = G. Untuk elemen hasil konversi mulai dari 2,

maka gunakan Algoritme 4.5 untuk menentukan perkalian G dengan G dan jika elemen

ke-i pada hasil konversi sama dengan 1 maka gunakan Algoritme 4.5 untuk menentukan

perkalian H dengan G.

Algoritme 4.9

Deskripsi : Prosedur untuk menghitung a mod m dalam rentang negatifInput : Integer positif m dan aOutput : Integer b

1. Hitung modb a m

2. / 2c m 3. Jika b c , maka

3.1 b = - (m – b)4. Return(”b”)

Banyaknya operasi dalam Algoritme 4.9 melibatkan rata-rata n operasi. Jadi

fungsi kompleksitas waktunya adalah ( )O n .

Algoritme 4.10

Deskripsi : Prosedur untuk menghitung exponen dalam vektorInput : Vektor 1 2[ , , ..., ]sA a a a , integer positif m dan i

Output : 1 2Vektor [ , , ..., ]irH A c c c

1. Hitung 3 1mp

2. Hitung k = modulo i , p menggunakan Algoritme 4.9

3. Jika 0k , maka lakukan3.1 X = ubah k dalam basis 23.2 Isi G = A, H = [1]3.3 Jika X1 = 1, maka H = G3.4 Untuk i mulai dari 2 sampai t , maka lakukan

3.4.1 Hitung perkalian vektor G.G menggunakan Algoritme 4.53.4.2 Jika Xi = 1, maka hitung H = H.G menggunakan Algoritme 4.5

4. Jika n k , maka lakukan4.1 X = ubah n dalam basis 24.2 Hitung G = Invers vektor A menggunakan Algoritme 4.74.3 Jika X1 = 1, maka H = G4.4 Untuk i mulai dari 2 sampai t , maka lakukan

46

4.4.1 Hitung perkalian G.G pada langkah 4.2 gunakan Algoritme 4.54.4.2 Jika Xi = 1, maka hitung H = H.G gunakan Algoritme 4.5

5. Return(”H”)

Banyaknya operasi dalam Algoritme 4.10 melibatkan rata-rata menggunakan

log . . .p n n n operasi. Jadi fungsi kompleksitas waktunya adalah 3(log . )O p n .

Sebagai contoh, misalkan fungsi polinomial 2 3 4 6( ) 1 2 2 2f x x x x x x ,

nilai input i = 5, dan fungsi polinomial primitif 3 10( ) 2m x x x x . Fungsi polinomial

direpresentasikan sebagai vektor terner [1, 2, 1, 2, 1, 0, 2]A dan fungsi polinomial

primitif direpresentasikan sebagai vektor terner [1, 2, 0, 2]M dengan derajat

maksimal 10 yang menunjukkan berada pada field 10(3 )GF . Dengan menggunakan

Algoritme 4.9 diperoleh modulus derajat maksimal yaitu 103 1 59048 dan dari input i

= 5 diperoleh barisan basis duanya adalah [1, 0, 1] sebagai exponennya. Dengan

menggunakan Algoritme 4.5, maka diperoleh outputnya adalah

[2, 1, 1, 2, 2, 0, 1, 0, 0, 1]H dan jika output ini dikembalikan ke dalam bentuk

fungsi polinomial maka 2 3 4 6 9( ) 2 2 2h x x x x x x x .

BAB V

PENERAPAN ALGORITME ARITMETIK (3 )mGF

PADA ALGORITME DIFFIE-HELLMAN KEY EXCHANGE

Seperti yang telah dijelaskan sebelumnya bahwa dalam mengonstruksi aritmetik

(3 )mGF didasarkan pada sifat *(3 )mGF yang merupakan grup siklik dibangkitkan dari

akar primitif. Salah satu contoh penerapan (3 )mGF adalah pada Algoritme Diffie-

Hellman Key Exchange.

Diffie-Hellman Key Exchange adalah metode dimana subjek menukar kunci

rahasia melalui media yang tidak aman tanpa mengekspos kunci. Metode ini

diperkenalkan oleh Dr. W. Diffie dan Dr. M. E. Hellman pada tahun 1976 pada papernya

yang berjudul ”New Direction in Cryptography” (Menezes 1997). Metode ini

memunginkan dua pengguna untuk bertukar kunci rahasia melalui media yang tidak

aman tanpa kunci tambahan. Metode ini memiliki dua parameter sistem yaitu P dan .

Kedua parameter tersebut publik dan dapat digunakan oleh semua pengguna sistem.

Berikut ini diberikan contoh penerapan aritmetik (3 )mGF yang

diimplementasikan dengan menggunakan Software MAPLE 11. Misalkan dua orang

yang berkomunikasi adalah Alice dan Bob. Pertama-tama Alice dan Bob menyepakati

untuk mengambil sembarang grup siklik berorder 3 1m kemudian membangkitkan

bilangan prima relatif secara acak menggunakan Algoritme 5.1. Algoritme 5.1

merupakan prosedur untuk membangkitkan bilangan prima relatif secara acak dari

3 1m . Algoritme 5.2 merupakan prosedur untuk membangkitkan elemen primitif secara

acak dari prima relatif acak.

Algoritme 5.1

Deskripsi : Prosedur untuk membangkitkan prima relatif secara acakInput : Bilangan bulat positif mOutput : Bilangan Prima Acak R

1. Tentukan 3 1mp

2. R = Acak Integer ( )p

3. Hitung gcd( , )h R p

2.1 Untuk i, selama 1h maka lakukan

48

2.1.1 R = Acak Integer ( )p

2.1.1 gcd( , )h R p

4. Return( R ).

Fungsi kompleksitas waktu pada Algoritme 5.1 adalah 2((log ) )O p .

Algoritme 5.2

Deskripsi : Prosedur untuk membangkitkan elemen primitif secara acakInput : Bilangan bulat positif mOutput : Vektor R

1. Tentukan prima relatif acak menggunakan Algoritme 5.12. Hitung elemen primitif menggunakan Algoritme 4.103. Return( ”R” ).

Fungsi kompleksitas waktu pada Algoritme 5.2 adalah 2((log ). )O p n .

Selanjutnya, baik Alice maupun Bob dapat menggunakan Algoritme 5.3 yaitu sebagai

prosedur yang digunakan dalam pertukaran kunci rahasia.

Algoritme 5.3

Deskripsi : Prosedur untuk membangkitkan kunciInput : Bilangan bulat mOutput : Kunci Alice

1. Tentukan elemen primitif menggunakan Algoritme 5.22. Bangkitkan x secara acak integer3. Hitung AK menggunakan Algoritme 4.10

4. Bangkitkan y secara acak integer

5. Hitung BK menggunakan Algoritme 4.10

6. Alice membangkitkan kunci menggunakan Algoritme 4.107. Return(“Kunci Alice ”)

Misalkan Alice dan Bob memilih 27m maka akan dibangkitkan secara acak

273 1 7625597484986p dengan menggunakan fungsi MAPLE ( )rand p . Selama

gcd( ( ), ) 1rand p p , maka lakukan terus menerus sehingga diperoleh

gcd( ( ), ) 1rand p p . Selanjutnya, dipilih secara acak generator (elemen primitif)

dengan menggunakan Algoritme 5.2, misalnya Alice dan Bob memilih elemen primitif

[2,2,1,1,1,1, 2,0,0,1, 2,0,0,0,1,0,1,0, 2,1,0,1,1, 2] . Selanjutnya, Alice membangkitkan

bilangan bulat acak yang besar x dari 273 1 7625597484986p dengan

49

menggunakan fungsi MAPLE AcIn(p), misalkan 7396366352238x kemudian

menghitung modxXA m menggunakan Algoritme 3.10 diperoleh

[0,0,0, 2,2,2,1, 2,1,1,1,1,1,0,0,1,0, 2, 2, 2,1,0,2,1,1,2,2]XA dan mengirim ke Bob.

Sebaliknya Bob membangkitkan bilangan bulat acak yang besar y dari

273 1 7625597484986p dengan menggunakan fungsi MAPLE AcIn(p), misalkan

2578459254750y kemudian menghitung modyYB m menggunakan Algoritma

3.10 diperoleh [2,1,1,1,0,1,2,2,1,2,1,0,0,2, 2,0,2,0,1,0,2,0,2,0, 2,1]YB dan mengirim

ke Alice.

Dari proses ini, Alice menggunakan Algoritme 5.3 sebagai prosedur untuk

membangkitkan kunci sehingga diperoleh

[0,0, 2, 2, 2,2,0,1,0,0,0,1,0,1,1,1,1,0, 2, 2,1,1,2,2,1,0, 2]KAlice .

Dengan cara yang sama Bob juga dapat membangkitkan kunci untuk

berkomunikasi dengan Alice. Dengan demikian, kunci yang digunakan baik Alice

maupun Bob adalah [0,0,2,2, 2, 2,0,1,0,0,0,1,0,1,1,1,1,0,2,2,1,1, 2, 2,1,0,2] .

BAB VISIMPULAN DAN SARAN

6.1 Simpulan

Dari hasil penelitian yang dilakukan dapat disimpulkan, sebagai berikut.

1. Secara umum, finite field (3 )mGF dapat dikonstruksi dengan mengambil polinomial

irreducible. Namun dalam penelitian ini, finite field (3 )mGF dikonstruksi dengan

mengambil polinomial primitif dimana generator dari grup siklik (3 )mGF sehingga

secara langsung dapat ditentukan sebagai akar primitif. Untuk mempercepat operasi

aritmetiknya, finite field (3 )mGF dikonstruksi dengan memilih polinomial primitif

bersuku kecil, khususnya polinomial-polinomial bersuku dua, polinomial-polinomial

bersuku tiga, dan polinomial-polinomial bersuku empat.

2. Dalam konstruksi algoritme aritmetik (3 )mGF menggunakan Algoritme Reduksi

Nol, yaitu sebagai algoritme rutin untuk mereduksi elemen nol pada representasi

vektor anggota (3 )mGF yang tidak mempengaruhi makna keterlibatannya dalam

operasi dapat diabaikan. Algoritme Reduksi Nol ini akan dipanggil oleh algoritme

operasi penjumlahan. Operasi penjumlahan akan di panggil secara berulang-ulang

oleh operasi perkalian sehingga dapat menghemat baik dalam penggunaan ruang

yang besar maupun dalam jumlah operasinya. Kedua operasi dasar ini pada

gilirannya akan mempengaruhi kecepatan Algoritme Pembagian, Algoritme Invers,

dan Algoritme Exponensial.

3. Algoritme aritmetik (3 )mGF yang dihasilkan secara asimptotik mempunyai kinerja

yang sama dengan algoritme sebelumnya yang dikonstruksi dari pengambilan

polinomial irreducible. Dengan demikian, secara rata-rata algoritme aritmetik

(3 )mGF yang dihasilkan akan menjadi lebih baik karena beberapa operasi dapat

direduksi menggunakan polinomial primitif atau sifat dari grup siklik.

6.2 Saran

1. Konstruksi algoritme aritmetik ( )mGF p dapat dilanjutkan untuk memilih bilangan

prima p yang lebih besar dari 3.

2. Algoritme aritmetik (3 )mGF hasil konstruksi dalam penelitian ini dapat dilanjutkan

ke arah Kurva Eliptik Kriptografi.

DAFTAR PUSTAKA

Aliatiningtyas N. 2002. Struktur Aljabar, Departemen Matematika Fakultas MIPA IPBBogor.

Bertoni G. Guajardo J. Kumar S. Orlando G. Paar C. Wollinger T. 2003. Efficient

( )mGF p Arithmetic Architectures for Cryptographic Applications, Topics in

Cryptology – CT-RSA 2003, LNCS 2612, pp. 158-175, San Francisco, CA,USA, Springer-Verlag Berlin Heidelberg.

Fraleigh JB. 2003. A First Course In Abstract Algebra, Seventh Edition, Addison-Wesley Publishing Company, Inc.

Gallian JA. 1990. Contemporary Abstract Algebra, Second Edition, D.C.Heath andCompany.

Gilbert WJ. Nicholson WK. 2004. Modern Algebra with Applications, Second Edition, AJohn-Wiley & Sons, Inc.

Guritman S. 2003. Pengantar Kriptografi, Departemen Matematika Fakultas MIPA IPBBogor.

Guritman S. 2004. Struktur Aljabar, Departemen Matematika Fakultas MIPA IPBBogor.

Herstein IN. 1999. Abstract Algebra, Third Edition, John-Wiley & Sons, Inc.

Lidl R. Niederreiter H. 1986. Introduction to Finite Field and their Applications,Cambridge University Press.

Menezes A. Oorschot PV. Vanstone S. 1997. Handbook of Applied Cryptography, CRCPress, Inc.

Omran A. Hankerson D. Menezes A. 2007. Software Implementation of Arithmetic in

3m , Lecture Notes in Computer Science, Springer Berlin/Heidelberg, vol. 4547

p. 85-102.

Rosdiana S. 2009. Konstruksi Algoritma Aritmetik (2 )mGF dengan Operasi Perkalian

Dibangkitkan dari Sifat Grup Siklik [Tesis]. Bogor: Program Pascasarjana,Institut Pertanian Bogor.

Schneier B. 1996. Applied Cryptography: Protocol, Algorithms, and Source Code in C,Second Edition, John-Wiley & Sons, Inc.

Truong T.K. Hsu I.S. Cheung K.M. Reed I.S. 1988. Efficient Multiplication Algorithm

Over the Finite Field ( )mGF q where 3,5q , TDA Progress report 42-93.

LAMPIRAN

53

Lampiran I: Implementasi Program Algoritme Aritmetik (3 )mGF menggunakan

Software MAPLE 11.

1.1 Algoritme UbahTerKeDes : Prosedur untuk mengubah vektor terner ke desimaldari order rendah ke order tinggi.

UbahTerKeDes := proc( N::list )

local D1, D2 :: list, Des::integer;

D1:=map(x -> 3^x,[seq(i,i=0..(nops(N)-1))]):

D2:=[seq(N[j]*D1[j],j=1..nops(N))]:

Des:=add( i, i=D2 );

end proc:

1.2 Algoritme UbahTerKeDes : Prosedur untuk mengubah vektor terner ke desimaldari order rendah ke order tinggi.

UbahDesKeTer := proc(B::integer)

local Kv::list:

Kv:=convert(B,base,3):

end proc:

1.3 Algoritme Acakter : Prosedur untuk membangkitkan vektor terner m bit secaraacak

AcakTer:=proc(m::posint)

local AcIn::procedure, p::integer:

AcIn := rand(3^m):

p:=AcIn():

UbahDesKeTer(p);

end proc:

1.4 Algoritme AcakterX : Prosedur untuk membangkitkan vektor terner m bitdengan elemen pertama tak-nol secara acak

AcakTerX:=proc(m::posint)

local AcIn::procedure, p,q,i::integer:

54

AcIn := rand(3^m):

p:=AcIn():

q:=p mod 3:

for i while q=0 do

p:=AcIn():

q:=p mod 3:

end do:

UbahDesKeTer(p);

end proc:

1.5 Algoritme ReduNol : Prosedur untuk mereduksi elemen nol yang paling kanan

ReduNol:=proc(R::list)

local T::list, j,t::integer:

T:=R: t:=nops(T):

for j while T[t]=0 and t>1 do

T:=subsop(t=NULL,T):

t:=t-1:

end do:

return(T);

end proc:

1.6 Algoritme AdisiT : Prosedur untuk menjumlahkan dua vektor

AdisiT:=proc(S::list,T::list)

local R::list, s,j,t::integer:

s:=nops(S): t:=s:

if S=[0] then return(T);

elif T=[0] then return(S);

elif s=nops(T) then

R:=[seq((op(i,S)+op(i,T)) mod 3,i=1..s)];

R:=ReduNol(R);

elif nops(S)<nops(T) then

55

subsop(seq(i=(op(i,S)+op(i,T) mod

3),i=1..nops(S)),T);

else

subsop(seq(i=(op(i,T)+op(i,S) mod

3),i=1..nops(T)),S);

end if:

end proc:

1.7 Algoritme NegT : Prosedur untuk menegatifkan elemen vektor

NegT:=proc(L::list)

map(x->(-x mod 3),L);

end proc:

1.8 Algoritme KVekT : Prosedur untuk menghitung kelipatan vektor

KVekT:=proc(L::list,n::integer[0..2])

if n=0 then return([0]);

elif n=1 then return(L);

else return(NegT(L)) end if;

end proc:

1.9 Algoritme GSatuT : Prosedur untuk menggeser elemen vektor

GSatuT:=proc(T::list,m::posint)

local R,H,L::list, t::integer:

L:=DatT[m]:

t:=nops(T):

if t<m then

R:=[0,op(T)];

else

R:=[0,op(subsop(m=NULL,T))]:

R:=ReduNol(R);

H:=KVekT(L,op(t,T)):

56

AdisiT(R,H);

end if:

end proc:

1.10 Algoritme MultiT : Prosedur untuk menghitung perkalian dua vektor

MultiT:=proc(A::list,B::list,m::posint)

local R,U,V,S,T::list, s,j,t,a::integer:

if A=[0] or B=[0] then return([0]) end if;

s:=nops(A): t:=nops(B):

S:=A: T:=B:

if t<s then

S:=B: T:=A:

a:=s: s:=t: t:=a:

end if:

R:=KVekT(T,op(1,S));

for j from 1 to (s-1) do

T:=GSatuT(T,m):

V:=KVekT(T,op(j+1,S)):

R:=AdisiT(R,V):

end do:

return(R);

end proc:

1.11 Algoritme KaliT : Prosedur untuk menghitung perkalian dua vektor tanpa modulo

KaliT:=proc(A::list,B::list)

local R,U,V,S,T::list, s,j,t,a::integer:

if A=[0] or B=[0] then return([0]) end if;

s:=nops(A): t:=nops(B):

S:=A: T:=B:

if t<s then

S:=B: T:=A:

a:=s: s:=t: t:=a:

57

end if:

R:=KVekT(T,op(1,S));

for j from 1 to (s-1) do

T:=[0,op(T)];

V:=KVekT(T,op(j+1,S)):

R:=AdisiT(R,V):

end do:

return(R);

end proc:

1.12 Algoritme BagiT : Prosedur untuk menghitung pembagian dua vektor tanpamodulo

BagiT:=proc(T::list,S::list)

local K,Q,R,H::list, i,g,r,s,k,h,t::integer:

if S=[0] then return(false) end if:

R:=T: Q:=[0]:

r:=nops(T): s:=nops(S):

g:=op(s,S):

if s=1 then

Q:=KVekT(R,op(S)):

R:=[0]:

return([Q,R]);

end if:

for i while r>=s do

k:=r-s: t:=op(r,R):

h:=(t*g) mod 3:

if k=0 then

K:=KVekT(S,h):

Q:=AdisiT(Q,[h]):

else

H:=KVekT(S,h):

K:=[seq(0,j=1..k),op(H)]:

Q:=AdisiT(Q,[seq(0,j=1..k),h]):

58

end if:

K:=NegT(K):

R:=AdisiT(K,R):

r:=nops(R):

end do:

return([Q,R]);

end proc:

1.13 Algoritme QBagiT : Prosedur untuk menghitung hasil bagi

QBagiT:=proc(A::list,B::list)

local L::list:

L:=BagiT(A,B):

return(op(1,L));

end proc:

1.14 Algoritme QBagiT : Prosedur untuk menghitung sisa bagi

RBagiT:=proc(A::list,B::list)

local L::list:

L:=BagiT(A,B):

return(op(2,L));

end proc:

1.15 Algoritme InvT : Prosedur untuk menentukan invers vektor

InvT:=proc(T::list,m::integer)

local QA,QB,RA,RB,R,S,L,Tmp,H::list, i::integer:

S:=NegT(DatT[m]):

if T=[0] then return(false) end if:

if nops(T)=1 then return(T) end if:

RA:=[op(S),seq(0,j=1..(m-nops(S))),1]:

RB:=T:

QA:=[0]: QB:=[1]:

59

L:=BagiT(RA,RB):

RA:=RB:

RB:=op(2,L):

for i while RB<>[0] do

Tmp:=QA:

QA:=QB:

H:=KaliT(QB,op(1,L)):

R:=NegT(H):

QB:=AdisiT(Tmp,R):

L:=BagiT(RA,RB):

RA:=RB:

RB:=op(2,L):

end do:

H:=KVekT(QB,op(RA)):

return(H);

end proc:

1.16 Algoritme DivT : Prosedur untuk menghitung pembagian vector.

DivT:=proc(A::list,B::list,m::integer)

local iB::list:

iB:=InvT(B,m);

MultiT(A,iB,m);

end proc:

1.17 Algoritme ModI : Prosedur untuk menghitung a mod m dalam rentang negatif.

ModN:= proc(a::integer, n::posint)

local b, c::integer:

b := a mod n:

c := floor(n/2):

if b > c then

b := -(n-b) end if:

60

return(b):

end proc:

1.18 Algoritme ExpT : Prosedur untuk menghitung eksponensial vektor

ExpT:=proc(A::list,x::integer,m::integer)

local H,G,X::list, i,p,k,n::integer:

p:=3^m-1:

k:=ModN(x,p):

if k>=0 then

X:=convert(k,base,2);

G:=A: H:=[1]:

if op(1,X)=1 then

H:=G:

end if:

for i from 2 to nops(X) do

G:=MultiT(G,G,m):

if op(i,X)=1 then

H:=MultiT(H,G,m):

end if:

end do:

else

n:=-k:

X:=convert(n,base,2);

G:=InvT(A,m): H:=[1]:

if op(1,X)=1 then

H:=G:

end if:

for i from 2 to nops(X) do

G:=MultiT(G,G,m):

if op(i,X)=1 then

H:=MultiT(H,G,m):

end if:

61

end do:

end if:

return(H);

end proc:

1.19 Algoritme PangkatTM : Prosedur untuk menghitung Ax mod B

PangkatTM:=proc(A::list,x::integer,B::list)

local H,G,K,L,X::list, i::integer:

X:=convert(x,base,2);

G:=A: H:=[1]:

if op(1,X)=1 then

H:=G:

end if:

for i from 2 to nops(X) do

K:=KaliT(G,G):

G:=RBagiT(K,B):

if op(i,X)=1 then

L:=KaliT(H,G):

H:=RBagiT(L,B):

end if:

end do:

return(H);

end proc:

1.20 Algoritme GcdT : Prosedur untuk menghitung FPB dari A dan B

GcdT:=proc(A::list,B::list)

local RA,RB,S,T,L::list, i,a,b::integer:

a:=nops(A): b:=nops(B):

RA:=A: RB:=B:

if a<b then

RA:=B: RB:=A:

62

end if:

if RB=[0] then return(RA) end if;

L:=RBagiT(RA,RB):

RA:=RB:

RB:=L:

for i while RB<>[0] do

L:=RBagiT(RA,RB):

RA:=RB:

RB:=L:

end do:

return(RA);

end proc:

1.21 Algoritme TestIrrT : Prosedur pengecekan polinomial irreducible atau tidak

TestIrrT:=proc(A::list)

local U,H,S,W::list, i,m,a,h::integer:

a:=nops(A)-1: m:=floor(a/2):

W:=[0,1]:

for i from 1 to m do

W:=PangkatTM(W,3,A);

U:=AdisiT(W,[0,2]):

H:=GcdT(U,A):

h:=nops(H):

if h>1 then

return(false);

break;

end if:

end do:

return(true);

end proc:

1.22 Algoritme GenIrrT : Prosedur untuk membangkitkan vektor irreducible secaraacak berderajat m

63

GenIrrT:=proc(m::posint)

local X,Y,T::list, x,i::integer:

X:=AcakTerX(m-1); x:=nops(X);

Y:=[op(X),seq(0,j=1..(m-x)),1]:

T:=TestIrrT(Y);

for i while T=false do

X:=AcakTerX(m-1); x:=nops(X);

Y:=[op(X),seq(0,j=1..(m-x)),1]:

T:=TestIrrT(Y);

end do:

return(Y);

end proc:

1.23 Algoritme GenIrrT : Prosedur untuk mengetes apakah polinomial irreducibleadalah primitif

TestPrimT:=proc(A::list)

local H::list, F::anything, i,m,a,h,k::integer:

m:=nops(A)-1: h:=3^m-1:

F:=ifactor(h);

a:=nops(F);

for i from 1 to a do

k:=h/op(op(1,op(i,F))):

H:=PangkatTM([0,1],k,A):

if H=[1] then

return(false);

break;

end if:

end do:

return(true);

end proc:

1.24 Algoritme GenPrimT : Prosedur untuk membangkitkan vektor primitif secaraacak

64

GenPrimT:=proc(m::posint)

local X::list, T::symbol, i::integer:

X:=GenIrrT(m):

T:=TestPrimT(X):

for i while T=false do

X:=GenIrrT(m):

T:=TestPrimT(X):

end do:

return(X);

end proc:

1.25 Algoritme GenPrimSk : Prosedur untuk membangkitkan vektor primitif bersukudua

GenPrimSk:=proc(m::posint)

local X,Y,T,U::list, x,i::integer:

for i from 4 do

if (i mod 3)<>0 then

X:=UbahDesKeTer(i); x:=nops(X);

Y:=[op(X),seq(0,j=1..(m-x)),1]:

T:=TestIrrT(Y);

if T=true then

U:=TestPrimT(Y):

if U=true then

return(Y);

break;

end if;

end if;

end if;

end do:

end proc:

1.26 Algoritme GenPrimTn : Prosedur untuk membangkitkan vektor primitif bersukutiga

65

GenPrimTn:=proc(m::posint)

local X,Y,T,U::list, n,j,k,i::integer:

n:=floor((m+1)/2);

for i from 1 to 2 do

for j from 1 to 2 do

Y:=[i,j,seq(0,x=1..(m-2)),1]:

T:=TestIrrT(Y);

if T=true then

U:=TestPrimT(Y):

if U=true then

return(Y);

break;

end if;

end if;

for k from 1 to (n-2) do

Y:=[i,seq(0,x=1..k),j,seq(0,x=1..(m-2-k)),1]:

T:=TestIrrT(Y);

if T=true then

U:=TestPrimT(Y):

if U=true then

return(Y);

break;

end if;

end if;

end do:

end do:

end do:

end proc:

1.27 Algoritme GenPrimQn : Prosedur untuk membangkitkan vektor primitif bersukuempat

GenPrimQn:=proc(m::posint)

local X,Y,T,U::list, n,j,k,i,l::integer:

66

n:=floor((m+1)/2);

for i from 1 to 2 do

for j from 1 to 2 do

for k from 1 to 2 do

Y:=[i,j,k,seq(0,x=1..(m-3)),1]:

T:=TestIrrT(Y);

if T=true then

U:=TestPrimT(Y):

if U=true then

return(Y);

break;

end if;

end if;

for l from 1 to (n-3) do

Y:=[i,j,seq(0,x=1..l),k,seq(0,x=1..(m-3-l)),1]:

T:=TestIrrT(Y);

if T=true then

U:=TestPrimT(Y):

if U=true then

return(Y);

break;

end if;

end if;

end do:

for l from 1 to (n-3) do

Y:=[i,seq(0,x=1..l),j,k,seq(0,x=1..(m-3-l)),1]:

T:=TestIrrT(Y);

if T=true then

U:=TestPrimT(Y):

if U=true then

return(Y);

break;

end if;

67

end if;

end do:

end do:

end do:

end do:

end proc:

1.28 Algoritme PrimaRelAcak : Prosedur untuk Prima Relatif Acak

PrimaRelAcak:=proc(m::posint)

local AcIn::PrimaRelAcak, g,i,R,p::integer:

p:=3^(m-1):

AcIn := rand(1..p):

R:=AcIn():

for i while g<>1 do

R:=AcIn():

g:=gcd(R,p):

end do:

return(R):

end proc:

1.29 Algoritme PrimitifTerAcak : Prosedur untuk membangkitkan unsur primitif acak

PrimitifTerAcak := proc(m::posint)

local Q,H,R::list, p::integer:

H:=PrimaRelAcak(m):

R:=ExpT([0,1],H,m):

return(R):

end proc:

1.30 Algoritme KunciT : Prosedur untuk membangkitkan kunci

KunciT := proc(m::integer)

local KA,KB,KAlice,Alfa::list,AcIn,x,y::posint:

68

Alfa:=PrimitifTerAcak(m):

AcIn:=rand(3^m-1):

x:=AcIn():

KA:=ExpT(Alfa,x,m):

y:=AcIn():

KB:=ExpT(Alfa,y,m):

KAlice:=ExpT(KB,x,m):

return(KAlice):

end proc:

69

Lampiran II: Tabel Polinomial Primitif (3 )mGF yang disimpan dalam basis data

DatT[m] untuk 1 100m .

Tabel II.1 Polinomial Primitif (3 )mGF untuk 1 80m .

m Polinomial Primitif m Polinomial Primitif41 x^41 + 2x + 1

2 x^2 + 2x + 2 42 x^42 + x^5 + x^4 + x^3 + x^2 + x + 23 x^3 + 2x + 1 43 x^43 + x^3 + x + 14 x^4 + x + 2 44 x^44 + x^3 + 25 x^5 + 2x + 1 45 x^45 + 2x^3 + x^2 + 16 x^6 + x + 2 46 x^46 + x^4 + 2x^2 + x + 27 x^7 + 2x^2 + 1 47 x^47 + x^4 + x^3 + x^2 + 18 x^8 + x^3 + 2 48 x^48 + x^5 + 2x^4 + 2x^3 + 2x^2 +29 x^9 +2x^3 + x^2 + 1 49 x^49 + 2x^3 + x^2 + 1

10 x^10 + x^3 + x + 2 50 x^50 + 2x^4 + x^3 + 2x^2 + 2x + 211 x^11 + x^2 + 2x + 1 51 x^51 + 2x + 112 x^12 + 2x^4 + x^3 + 2x^2 + 2x + 2 52 x^52 + x^5 + 2x^4 + 2x + 213 x^13 + 2x + 1 53 x^53 + 2x^4 + 2x^3 + 2x^2 + 114 x^14 + x + 2 54 x^54 + x + 215 x^15 + x^2 + 2x + 1 55 x^55 + 2x^3 + 2x^2 + 2x + 116 x^16 + x^4 + x^3 + 2x + 2 56 x^56 + x^3 + 217 x^17 + 2x + 1 57 x^57 + x^5 + 2x^3 + 2x^2 + x + 118 x^18 + x^5 + 2x^2 + 2x + 2 58 x^58 + x^4 + 2x^2 + x + 219 x^19 + x^2 + 2x + 1 59 x^59 + x^3 + 2x^2 + 2x + 120 x^20 + x^5 + x + 2 60 x^60 + x^5 + x + 221 x^21 + x^3 + x + 1 61 x^61 + x^3 + 2x^2 + 2x + 122 x^22 + x^3 + 2x^2 + 2x + 2 62 x^62 + x^4 + 2x^2 + x + 223 x^23 + x^3 + x + 1 63 x^63 + x^5 + 2x^2 + 2x + 124 x^24 + 2x^4 + x^3 + 2x + 2 64 x^64 + x^3 + 225 x^25 + 2x^3 + 1 65 x^65 + x^5 + x^3 + 126 x^26 + x^3 + x + 2 66 x^66 + x^5 + 2x^2 + 2x + 227 x^27 + x^5 + x^4 + 2x^3 + 2x + 1 67 x^67 + x^2 + 2x + 128 x^28 + x^5 + x^4 + 2x^2 + 2 68 x^68 + x^5 + x^4 + 2x^3 + 2x^2 + x + 229 x^29 + x^4 + x^2 + 1 69 x^69 + 2x^5 + 2x^4 + x^3 + x^2 + 2x + 130 x^30 + x + 2 70 x^70 + x^5 + x^4 + 2x^3 + 231 x^31 + x^3 + x + 1 71 x^71 + x^4 + 2x^2 + 2x + 132 x^32 + x^4 + x^3 + 2x + 2 72 x^72 + x^6 + x^3 + x^2 + 2x + 233 x^33 + x^5 + 2x^2 + 1 73 x^73 + 2x + 134 x^34 + x^3 + x + 2 74 x^74 + 2x^4 + x^3 + 2x^2 + 2x + 235 x^35 + x^2 + 2x + 1 75 x^75 + 2x^5 + x^3 + 2x + 136 x^36 + x^5 + x^4 + 2x^3 + 2 76 x^76 + x^5 + x + 237 x^37 + x^3 + 2x^2 + 2x+1 77 x^77 + x^4 + x^3 + 2x^2 + x + 138 x^38 + x^3 + x^2 + 2x + 2 78 x^78 + x^5 + 2x^4 + 2x^3 + x^2 + 2x + 239 x^39 + x^5 + 2x^3 + 2x^2 + 1 79 x^79 + x^4 + 2x^3 + 140 x^40 + x + 2 80 x^80 + x^5 + 2x^4 + x^2 + 2

70

Tabel II.2 Polinomial Primitif (3 )mGF untuk 80 100m .

m Polinomial Primitif No Polinomial Primitif81 x^81 + x^6 + x^5 + 2x^3 + 2x + 1 91 x^91 + x^4 + x^3 + x^2 + 2x + 182 x^82 + x^5 + x^4 + 2x^2 + 2 92 x^92 + x^5 + x^2 + 2x + 283 x^83 + x^5 + 2x^2 + 2x + 1 93 x^93 + x^5 + x^4 + x + 184 x^84 + 2x^6 + x^5 + x^4 + x + 2 94 x^94 + x^5 + 2x^3 + 2x^2 + 285 x^85 + x^4 + x + 1 95 x^95 + x^3 + x + 186 x^86 + x^5 + x^3 + 2 96 x^96 + x^6 + 2x^4 + x^3 + x + 287 x^87 + 2x^5 + x^3 + 2x + 1 97 x^97 + 2x^3 + 2x^2 + 2x + 188 x^88 + x^5 + x^3 + 2x + 2 98 x^98 + x^4 + x^3 + 2x^2 + 289 x^89 + 2x^3 + x^2 + 1 99 x^99 + x^5 + 2x^3 + 2x^2 + x + 190 x^90 + 2x^6 + x^5 + 2x + 2 100 x^100 + x^5 + x^4 + 2x + 2