EKSPLORASI MASALAH LOGARITMA DISKRET PADA FINITE FIELD ( ) Y A N A

EKSPLORASI MASALAH LOGARITMA DISKRET PADA FINITE FIELD ( )

YANA

SEKOLAH PASCA SARJANA INSTITUT PERTANIAN BOGOR BOGOR 2009

PERNYATAAN MENGENAI TUGAS AKHIR DAN SUMBER INFORMASI Dengan ini saya menyatakan bahwa tesis dengan judul “Eksplorasi Masalah Logaritma Diskret pada Finite Field (2)” adalah karya saya dengan arahan dari komisi pembimbing dan belum diajukan dalam bentuk apa pun kepada perguruan tinggi mana pun. Sumber informasi yang berasal atau dikutip dari karya yang diterbitkan maupun tidak diterbitkan dari penulis lain telah disebutkan dalam teks dan dicantumkan dalam Daftar Pustaka di bagian akhir tesis ini. Bogor, Agustus 2009 Yana NRP G551070411

ABSTRACT YANA. The Exploration of Discrete Logarithm Problem over Finite Field Under direction of SUGI GURITMAN and NUR ALIATININGTYAS.

(2).

Discrete logarithm problem represents a problem which is defined as modular arithmetic. It is often used to generate a key pair on public key cryptography as security object. Given cyclic group G of order n, α generator of G, and β ∈ , then, in general, discrete logarithm problem is determined as the integer , 0 ≤ ≤ − ,1such that α ≡ β(mod ). In Menezes et al. (1997) the algorithm to solve the discrete logarithm problem in common cyclic group G are Exhaustive Search algorithm, Baby-Step Giant-Step, Pollard's rho, Pohlig Hellman and Index Calculus. Furthermore, these algorithms are explored to determine the solution of discrete logarithm problem on (2). The reconstructed algorithms are implemented using Maple 11 software. These implementation can be used to measure security level of cryptography algorithm, which is based on security aspects of discrete logarithm problem. Keywords : discrete logarithm problem, cyclic group, finite field

(2).

RINGKASAN YANA. Eksplorasi Masalah Logaritma Diskret Pada Finite Field Dibimbing oleh SUGI GURITMAN dan NUR ALIATININGTYAS.

(2).

(2 ) = ℤ [ ]/〈 ( 〉) adalah field berorder 2 dengan ( )adalah ∈ (2 ) dapat dinyatakan polinomial irredusibel atas ℤ berderajad . Setiap secara unik dalam bentuk = + + + ⋯+ , dimana ∗ (2 (2 ) )\{0} ∈ℤ ,0≤ ≤ − .1 = adalah grup di bawah operasi penjumlahan dan perkalian modulo 2. (2 )∗ berorder , generator (2)∗, Jika diberikan grup siklik ∗ ∈ (2) , dan ( ) adalah polinomial irredusibel atas ℤ . Logaritma diskret dengan basis adalah integer unik , 0 ≤ ≤ − ,1sedemikian sehingga ≡ (mod ( )), dan bagaimana menentukan disebut masalah logaritma diskret. Dalam Menezes et al. (1997) lima algoritme untuk menyelesaikan masalah logaritma diskret pada grup siklik umum adalah Algoritme Exhaustive Search, Baby-Step Giant-Step, Pollard’s rho, Pohlig Hellman dan Index Calculus. Kelima algoritme ini dieksplorasi untuk menentukan masalah logaritma diskret pada (2)∗ . Ide dasar Algoritme Exhaustive Search untuk menentukan logaritma diskret adalah Definisi Masalah Logaritma Diskret, yaitu dengan mencoba setiap kemungkinan nilai , 0 ≤ ≤ 2 − 1, sampai ditemukan yang benar. Baby-Step Giant-Step adalah merupakan time-memory trade-off dari Algoritme Exhaustive Search yakni situasi dimana memori komputer digunakan untuk mengurangi biaya dan waktu eksekusi program. Representasi polinomial adalah order (2)∗. akan disimpan di memori komputer sebanyak √ , maka representasi polinomial yang disimpan di memori Semakin besar komputer semakin banyak juga. Ide dasar algoritme ini adalah membagi dengan , =√ , hingga ditemukan salah satu suatu representasi polinomial representasi polinomial yang disimpan di memori komputer. Ide dasar Algoritme Pollard’s rho adalah menemukan cycle dalam barisan { , , , … , }. Untuk menemukan cycle dalam barisan { , , , … , } digunakan Algoritme Floyd’s Cycle-Finding dengan membandingkan elemen-elemen sampai sehingga pasangan = ditemukan. Selanjutnya Birthday Paradox digunakan untuk menjamin bahwa mulai adanya satu atau lebih bilangan yang sama dalam barisan bilangan sedikitnya setelah langkah ke-√ √2 ln 2 dengan peluang lebih dari setengah. Misalkan (2)∗ adalah grup siklik dibawah operasi perkalian berorder = 2 − 1, =∏ , adalah bilangan prima berbeda dan ≥ 1. Ide dari Algoritme Pohlig Hellman untuk menentukan masalah logaritma diskret ≡ log (mod ( )) adalah menemukan mod , dengan terlebih dahulu mod , untuk setiap , 1 ≤ ≤ , menggunakan Teorema Sisa menentukan Cina. Artinya komputasi dilakukan pada subgrup berorder prima berpangkat integer positif ( ).

Kekuatan Algoritme Index Calculus terletak pada faktorisasi polinomial. Faktorisasi polinomial dapat dilakukan dalam 4 tahap. Tahap pertama adalah faktorisasi bebas kuadrat, kedua faktorisasi bebas kuadrat berderajad , ketiga , dan terakhir faktorisasi lengkap faktorisasi berderajad ( ) = ( ) ( ) … ( ) . Ide dasar Algoritme Index Calculus adalah (2 )∗ sebagai faktor basis sedemikian sehingga dengan memilih subset dari elemen-elemen (2)∗ secara efisien dapat dinyatakan sebagai produk elemen-elemen . Kata kunci : masalah logaritma diskret, grup siklik, finite field

(2).

© Hak Cipta milik IPB, tahun 2009 Hak Cipta dilindungi Undang-Undang 1. Dilarang mengutip sebagian atau seluruh karya tulis ini tanpa mencantumkan atau menyebutkan sumber. a. Pengutipan hanya untuk kepentingan pendidikan, penelitian, penulisan karya ilmiah, penyusunan laporan, penulisan kritik, atau tinjauan suatu masalah b. Pengutipan tidak merugikan kepentingan yang wajar IPB 2. Dilarang mengumumkan dan memperbanyak sebagian atau seluruh Karya Tulis dalam bentuk apapun tanpa izin IPB.

EKSPLORASI MASALAH LOGARITMA DISKRET PADA FINITE FIELD ( )

YANA

Tesis sebagai salah satu syarat untuk memperoleh gelar Magister Sains pada Program Studi Matematika Terapan

SEKOLAH PASCA SARJANA INSTITUT PERTANIAN BOGOR BOGOR 2009

Penguji Luar Komisi pada Ujian Tesis: Drs. Prapto Tri Supriyo, M.Kom.

Judul Tesis Nama NRP

: Eksplorasi Masalah Logaritma Diskret pada Finite Field : Yana : G551070411

(2 )

Disetujui Komisi Pembimbing

Dr. Sugi Guritman Ketua

Dra. Nur Aliatiningtyas, M.Si. Anggota

Diketahui

Ketua Progam Studi Matematika Terapan

Dekan Sekolah Pascasarjana

Dr. Ir. Endar H. Nugrahani, M.S.

Prof. Dr. Ir. Khairil A. Notodiputro, M.S.

Tanggal Ujian : 13 Agustus 2009

Tanggal Lulus :

PRAKATA Puji dan syukur penulis panjatkan ke hadirat Allah SWT atas segala rahmat dan karuniaNya tugas akhir yang berjudul “Eksplorasi Masalah Logaritma Diskret pada Finite Field (2)” ini bisa terselesaikan sebagai salah satu syarat untuk menyelesaikan pendidikan pada Program Studi Matematika, Sekolah Pascasarjana Institut Pertanian Bogor. Terimakasih yang mendalam penulis sampaikan kepada Abah dan Mama atas segala doa dan kasih sayangnya. Terimakasih juga penulis sampaikan kepada Dr. Sugi Guritman dan Dra. Nur Aliatiningtyas, M.Si selaku pembimbing yang telah membantu dan mengarahkan penulis selama penyusunan tugas akhir ini, serta Drs. Prapto Tri Supriyo, M.Kom. selaku dosen penguji. Ucapan terima kasih juga penulis sampaikan kepada Departemen Agama Republik Indonesia yang telah memberikan beasiswa kepada penulis selama menempuh pendidikan di IPB. Terimakasih juga penulis sampaikan kepada Ai Tusi Fatimah, Salamia, Lathifaturrahmah dan semua pihak yang tidak dapat dituliskan namanya satu persatu atas segala bantuannya selama penelitian. Tentu saja dari awal hingga selesainya tulisan ini tidak terlepas dari dukungan, motivasi dan doa dari suami tercinta dan semua keluarga. Akhirnya penulis menyadari bahwa tugas akhir ini masih begitu banyak kekurangan. Dengan segala keterbatasan yang ada, semoga tugas akhir ini bermanfaat. Bogor, Agustus 2009 Yana

RIWAYAT HIDUP Penulis dilahirkan di Tambarangan, Banjarmasin pada tanggal 13 Juni 1977 sebagai anak pertama dari tiga bersaudara. Pada tahun 2001 penulis menyelesaikan pendidikan strata satu di Program Studi Pendidikan Matematika, FKIP UNLAM Banjarmasin, dan langsung bekerja sebagai tenaga pengajar pada Madrasah Tsanawiyah Negeri Binuang sampai sekarang. Pada tahun 2007 penulis diberi kesempatan melanjutkan studi di Program Studi Matematika, Sekolah Pascasarjana Institut Pertanian Bogor dengan beasiswa dari Departemen Agama Republik Indonesia.

DAFTAR ISI

Halaman DAFTAR ISI …………………………………………..…………….......

x

DAFTAR TABEL .....................................................................................

xii

DAFTAR ALGORITME ..........................................................................

xiv

DAFTAR LAMPIRAN .............................................................................

xv

BAB 1 PENDAHULUAN ....................................................................... 1.1 Latar Belakang ...................................................................... 1.2 Tujuan Penelitian ................................................................... 1.3 Manfaat Penelitian .................................................................

1 1 3 4

BAB 2 TINJAUAN PUSTAKA .............................................................. 2.1 Teori Bilangan ....................................................................... 2.2 Integer Modulo ................................................................... 2.3 Struktur Aljabar ..................................................................... 2.4 Masalah Logaritma Diskret ………………………...……… 2.5 Sistem Persamaan Linear ….................................................. 2.6 Algoritme Berlekamp’s Q-Matrix ………………...……….. 2.7 Kompleksitas Waktu Asimptotik …………………………...

5 5 6 8 15 16 17 17

BAB 3 HASIL DAN PEMBAHASAN .................................................... 3.1 Masalah Logaritma Diskret pada Finite Field (2 ) ...…. 3.1.1 Finite Field (2 ) ……………………..…………. 3.1.2 Masalah Logaritma Diskret pada (2 )∗ ……..….. 3.2 Solusi Masalah Logaritma Diskret pada (2 )∗ ……..…. 3.2.1 Solusi Masalah Logaritma Diskret pada GF(2 )∗ dengan Algoritme Exhaustive Search ……..………... 3.2.2 Solusi Masalah Logaritma Diskret pada GF(2 )∗ dengan Algoritme Baby-Step Giant-Step ………...…. 3.2.3 Solusi Masalah Logaritma Diskret pada GF(2 )∗ dengan Algoritme Baby-Step Giant-Step 2 ……...….. 3.2.4 Solusi Masalah Logaritma Diskret pada GF(2 )∗ dengan Algoritme Baby-Step Giant-Step 3 ……...….. 3.2.5 Solusi Masalah Logaritma Diskret pada GF(2 )∗ dengan Algoritme Naif Square …………...…………. 3.2.6 Solusi Masalah Logaritma Diskret pada GF(2 )∗ dengan Algoritme Pollard’s rho ………………..…... 3.2.7 Solusi Masalah Logaritma Diskret pada GF(2 )∗ dengan Algoritme Pohlig Hellman ……………...…... 3.2.8 Solusi Masalah Logaritma Diskret pada GF(2 )∗ dengan Algoritme Index Calculus ………...………… 3.2.8.1 Faktorisasi Polinomial ………………...…….

19 19 19 22 23 23 27 31 35 38 42 54 65 65

3.2.8.2 Solusi Masalah Logaritma Diskret pada (2 )∗ dengan Algoritme Index Calculus .. 3.3 Komputasi Masalah Logaritma Diskret pada (2 )∗ …....

BAB 4 KESIMPULAN DAN SARAN .................................................... 4.1 Kesimpulan ………………………………………...……..... 4.2 Saran ……………………………………………...………... DAFTAR PUSTAKA ...............................................................................

84 89 96 96 97

98 LAMPIRAN .............................................................................................. 100

DAFTAR TABEL Halaman 2.7.1 Oh-Besar .............................................................................................

18

(2 ) .....................................................................

21

+ 1 ........................................................................

3.1.1 Elemen-elemen

3.2.1 Representasi Polinomial ( =

+

+

=

+

+

3.2.2 Representasi Polinomial ( +

3.2.3 Hasil Perhitungan ( , : dengan

(mod ( )) untuk

(2 )∗ dengan

30

(2 )∗

+ 1 ……………………………..…

31

+

+

+

=

+

+

+

=

+

+

=

+

+

3.2.6 Hasil Perhitungan ( , dengan

25

=


(2 )∗ dengan

+ 1 ………………………………………..


(mod ( )) untuk

mod ( ) ), ≥ 0 untuk


(2 )∗

+ 1 ……………………………..…

34


+

(2 )∗

+ 1 ………………………………..

38

+

+ 1 ………………………………..

41

(2 )∗


3.2.7 Hasil Perhitungan Birthday Paradox …………………………….....

44

3.2.8 Beberapa Kemungkinan Pendefinisian Keanggotaan Himpunan ⊆

(2 )∗ , = 1,2,3 untuk Algoritme Pollard’s rho .................

46

=

+

+

(2 )∗ dengan

49

=

+

+

(2 )∗ dengan

50

=

+

+

(2 )∗ dengan

+ 1 …….

51

=

+

dan

=

(2 )∗ dengan

+ 1 ……………………………….

52

=

+

dan

(2 )∗ dengan

53

3.2.9 Hasil Perhitungan 3.2.10 Hasil Perhitungan 3.2.11 Hasil Perhitungan 3.2.12 Hasil Perhitungan 3.2.13 Hasil Perhitungan 3.2.14 Hasil Perhitungan

,

dan

, ,

,

dan

, ,

,

dan

, ,

,

, ,

,

, ,

,

,

, ,

,

=

= = =

= =

, , ,

,

, pada

,

, pada

,

, pada

,

, pada

,

, pada

…………………………………... =

=

,

+

,

+ 1 ……………………… +

+

+

+ 1 ………………………… , pada

(2 )∗ dengan

=

+

dan

3.2.15 Hasil Perhitungan ( )=

+

+

=

……………………………………………

( ), ℎ ( ), dan ( ), dengan

+ 1 …………………………………………...

53 69

( ): ( ( )) …………………………………...

78

3.2.17 Nilai Harapan Kompleksitas Waktu Algoritme …………………….

89

3.3.1 Waktu Komputasi dengan Algoritme Exhaustive Search …..……...

89

3.3.2 Waktu Komputasi dengan Algoritme Baby-Step Giant-Step ….…..

90

3.3.3 Waktu Komputasi dengan Algoritme Baby-Step Giant-Step 2 …….

91

3.3.4 Waktu Komputasi dengan Algoritme Baby-Step Giant-Step 3 …….

91

3.3.5 Waktu Komputasi dengan Algoritme Naif Square …………………

92

3.3.6 Waktu Komputasi dengan Algoritme Pollard’s rho ……………….

93

3.3.7 Waktu Komputasi dengan Algoritme Pohlig-Hellman ...…………..

94

3.3.8 Waktu Komputasi dengan Algoritme Index Calculus ……………...

94

3.3.9 Waktu Komputasi Logaritma Diskret

95

3.2.16 Hasil perhitungan

dengan Beberapa Algoritme

DAFTAR ALGORITME Halaman 2.6.1 Algoritme Berlekamp’s Q-Matrix .....................................................

17

3.2.1 Algoritme Exhaustive Search ...........................................................

24

3.2.2 Algoritme Baby-Step Giant-Step .....................................................

28

3.2.3 Algoritme Baby-Step Giant-Step 2………………………………....

33

3.2.4 Algoritme Baby-Step Giant-Step 3…………………………………

36

3.2.5 Algoritme Naif Square .................………………………………...

40

3.2.6 Algoritme Pollard’s rho ................………………………………...

47

3.2.7 Algoritme Pohlig Hellman .............………………………………..

57

3.2.8 Algoritme Faktorisasi Bebas Kuadrat 1 ..…………………….........

68

3.2.9 Algoritme Faktorisasi Bebas Kuadrat 2 ..........................................

70

3.2.10 Algoritme Faktorisasi Bebas Kuadrat 3 ……………………...…...

71

3.2.11 Algoritme Faktorisasi Bebas Kuadrat Berderajad

………………

72

3.2.12 Algoritme Sisa Bagi 1 ..........................................................……….

74

3.2.13 Algoritme Sisa Bagi 2………………………………………………

75

3.2.14 Algoritme Satu Faktor Derajad

……………...……….…………

77

3.2.15 Algoritme Faktorisasi Lengkap…..………………………………...

82

3.2.16 Algoritme Index Calculus…………………………………………..

86

DAFTAR LAMPIRAN Halaman 1 Program Aritmetika Finite Field 2 Program Faktorisasi Polinomial

(2 )........................................

101

(2 ).......................................... 105

2.1 Faktorisasi Bebas Kuadrat 1....................................................... 105 2.2 Faktorisasi Bebas Kuadrat 2…………………………………... 105 2.3 Faktorisasi Bebas Kuadrat 3…………………………………... 106 2.4 Faktorisasi Bebas Kuadrat Berderajad ……………………… 106 2.5 Sisa Bagi 1................…………………………………………... 106 2.6 Sisa Bagi 2.............…………………………………………….. 106 ..……………….…................................

107

2.8 Faktorisasi Lengkap ..................................................................

107

2.7 Satu Faktor Derajad

3 Program Solusi Masalah Logaritma Diskret pada

(2 )∗ …..…... 108

3.1 Exhaustive Search .........................................................……….

108

3.2 Penyimpanan Baby-Step......…………………………………...

108

3.3 Baby-Step Giant-Step ……………...………………………….

109

3.4 Baby-Step Giant-Step 2 ……………………………………….

109

3.5 Baby-Step Giant-Step 3………………………………………..

109

3.6 Naif Square…………………….………………………………. 110 3.7 Pollard’s rho…………………………………………………...

110

3.8 Pohlig Hellman………………………………………………… 111 3.9 Index Calculus…………………………………………………. 112

BAB I PENDAHULUAN 1.1

Latar Belakang Logaritma adalah suatu operasi matematika kebalikan dari eksponen atau

pemangkatan. Logaritma sering digunakan untuk memecahkan persamaan yang = ,

pangkatnya tidak diketahui. Dalam persamaan pengakaran,

dengan logaritma, dan

pada persamaan 2 = 8.

dapat dicari dengan

dengan pemangkatan. Contoh, berapakah

dapat dihitung atau dicari dengan menggunakan = 3.

, hasilnya adalah

tabel atau kalkulator yang sudah dilengkapi fitur

Bentuk persamaan 2 = 8 ini adalah suatu sistem aritmetik bilangan nyata (ℝ),

sistem aritmetik umum lainnya adalah grup siklik.

dengan operasi biner ∗ yang memenuhi sifat assosiatif,

Struktur aljabar

terdapat unsur identitas dan setiap unsurnya memiliki invers disebut grup. Suatu grup yang mempunyai generator disebut grup siklik. Generator ini berperan dalam membangkitkan unsur-unsur grup siklik siklik

,

berorder = ,

kasus

, maka

. Misalkan

=〈 〉 = {1,

,

,…,

disebut logaritma diskret. Jika diketahui

bagaimana menentukan

adalah generator grup =

,…,

}. Pada

dan , maka masalah

dikenal dengan istilah masalah logaritma diskret.

Masalah logaritma diskret merupakan masalah yang didefinisikan pada aritmetika modular, sering dijadikan dasar pembangkitan sepasang kunci pada kriptografi kunci publik sebagai tumpuan keamanan. Contohnya pada pertukaran kunci Diffie-Hellman dan enkripsi Elgamal. Logaritma umum pasti akan tuntas secara komputasi, tetapi untuk logaritma diskret khusus berorder besar menentukannya tidak akan layak hitung (sulit dihitung) walaupun menggunakan kalkulator yang canggih. Tidak layak hitung itulah yang menyebabkan masalah logaritma diskret layak digunakan sebagai tumpuan keamanan dalam kriptogafi. Masalah logaritma diskret sering diterapkan pada grup siklik ℤ ∗, Diberikan bilangan prima ,

generator dari ℤ ∗, dan

prima. ∈ ℤ ∗. Dalam

Menezes et al. (1997), definisi masalah logaritma diskret adalah menentukan , 0≤

≤

− 2sehingga

≡

(mod .)Berdasarkan definisi ini jika diberikan

(2)∗, maka untuk sembarang

generator dari

yang khas pada rentang 0 ≤

(2)∗ terdapat suatu

∈

≤ 2 − 2 sedemikian sehingga : (mod ( ))

≡

(2) = ℤ [ ]/〈 ( 〉)adalah field dibawah operasi penjumlahan dan perkalian

dalam modulo

( )berorder 2 , dengan

(2) ∗ adalah field

( )polinomial irredusibel atas ℤ .

(2) tanpa elemen {0} membentuk grup dibawah

operasi perkalian berorder 2 − 1 (Menezes et al. 1997). Elemen-elemen grup multiplikatif

adalah 1,

,

(2)∗ dengan generator

,…,

=

,…,

dalam bentuk representasi grup siklik

.

Menentukan masalah logaritma diskret menjadi sulit apabila digunakan (2)∗ dengan order besar. Karena itu diperlukan suatu teknik tertentu

grup

untuk menyelesaikannya. Beberapa teknik yang dapat digunakan untuk menentukan masalah logaritma diskret ini adalah Algoritme Exhaustive Search,

Baby-Step Giant-Step, Pollard’s rho, Pohlig Hellman, dan Index Calculus. Dalam Menezes et al. (1997) kelima algoritme tersebut dikenakan pada grup siklik umum. sedangkan pada tulisan ini dikenakan pada sistem aritmatik grup multiplikatif

(2)∗.

Ide dasar Algoritme Exhaustive Search untuk menentukan logaritma diskret

adalah Definisi Masalah Logaritma Diskret, yaitu dengan mencoba

setiap kemungkinan nilai , 0 ≤

≤ 2 − 1, sampai ditemukan

Algoritme ini tidak efisien digunakan untuk grup multiplikatif besar.

yang benar. (2)∗ berorder

Baby-Step Giant-Step adalah merupakan time-memory trade-off dari Algoritme Exhaustive Search yakni situasi dimana memori komputer digunakan untuk mengurangi biaya dan waktu eksekusi program. Representasi polinomial akan disimpan di memori komputer sebanyak √ ,

Semakin besar

(2)∗.

adalah order

maka representasi polinomial yang disimpan di memori

komputer semakin banyak juga. Ide dasar algoritme ini adalah membagi suatu representasi polinomial

,

dengan

=√ , hingga ditemukan salah satu

representasi polinomial yang disimpan di memori komputer.

Ide dasar Algoritme Pollard’s rho adalah menemukan cycle dalam barisan { ,

,

,…,

}. Untuk menemukan cycle dalam barisan { ,

,

,…,

}

2

digunakan Algoritme Floyd’s Cycle-Finding dengan membandingkan elemensampai

elemen

=

sehingga pasangan

ditemukan. Selanjutnya

Birthday Paradox digunakan untuk menjamin bahwa mulai adanya satu atau lebih bilangan yang sama dalam barisan bilangan sedikitnya setelah langkah ke√ √2 ln 2 dengan peluang lebih dari setengah. Misalkan

= 2 − 1,

=∏

(2)∗ adalah grup siklik dibawah operasi perkalian berorder ,

adalah bilangan prima berbeda dan

≥ 1. Ide dari

Algoritme Pohlig Hellman untuk menentukan masalah logaritma diskret ≡ log

menentukan

(mod ( )) adalah menemukan mod

,untuk setiap , 1 ≤

mod , dengan terlebih dahulu

≤ , menggunakan Teorema Sisa

Cina. Artinya komputasi dilakukan pada subgrup berorder prima berpangkat integer positif (

).

Kekuatan Algoritme Index Calculus terletak pada faktorisasi polinomial, idenya adalah dengan memilih subset sedemikian sehingga elemen-elemen sebagai produk elemen-elemen .

dari

(2)∗ sebagai faktor basis

(2)∗ secara efisien dapat dinyatakan

Algoritme Exhaustive Search, Baby-Step Giant-Step, Pollard’s rho, Pohlig Hellman, dan Index Calculus dieksplorasi untuk menentukan masalah logaritma diskret pada grup multiplikatif sofware Maple 11. 1.2

(2 )∗ dan diimplementasikan dengan bantuan

Tujuan Penelitian Tujuan penelitian ini adalah : (2).

1.

Mengkaji secara teoritik masalah logaritma diskret pada finite field

2.

Merekonstruksi algoritme-algoritme yang berhubungan dengan masalah logaritma diskret pada finite field

3.

(2).

Mengimplementasikan algoritme hasil rekonstruksi dengan bantuan software Maple 11.

3

1.3

Manfaat Penelitian Manfaat dari penelitian ini adalah algoritme hasil rekonstruksi bisa

digunakan untuk mengukur tingkat keamanan dari algoritme kriptografi yang aspek keamanannya bertumpu pada masalah logaritma diskret.

4

BAB II TINJAUAN PUSTAKA Pada bab ini dituliskan beberapa aspek teoritis berupa definisi, teorema dan sifat-sifat yang berhubungan dengan teori bilangan, integer modulo , aljabar abstrak, masalah logaritma diskret, sistem persamaan linear, dan kompleksitas waktu asimptotik sebagai landasan teori untuk penulisan tugas akhir ini. 2.1

Teori Bilangan

Definisi 2.1.1 Misalkan integer

,

dan

adalah integer dengan

menghasilkan integer +, dimana 0 ≤

pembagian dinotasikan

(hasil pembagian) dan

| dan

2.

dan , dinotasikan

adalah pembagi bersama dari jika

| dan

| , maka

dan

mod dan hasil

= gcd ( , , jika ) :

Teorema 2.1.5 (Algoritme Euclidean) Diberikan integer

,

algoritme pembagian, dapat dibentuk barisan persamaan berikut : =

= =

+

+

+

,0 <

<

,0 <

<

,0 < ⋮

+ ,0 < =

dan ,

disebut pembagi bersama terbesar

| (Menezes et al. 1997).

=

oleh

(sisa pembagian) sehingga

dikatakan sebagai pembagi bersama dari

Definisi 2.1.4 Suatu integer non-negatif 1.

| )jika terdapat

≥ 1, maka pembagian

≤ . Sisa pembagian dinotasikan

| (Menezes et al. 1997).

(gcd) dari integer

(notasi

div (Menezes et al. 1997).

Definisi 2.1.3 Suatu integer jika

membagi

= .

sedemikian sehingga

Definisi 2.1.2 Jika =

integer.

<

<

> .0Berdasarkan

= gcd ( , ,) yang merupakan sisa terakhir tak nol dari proses

dengan

dari ( , ) =

dan

pembagian. Nilai dari

sebagai kombinasi linear dari

menuliskan setiap

Definisi 2.1.6 Integer

dan

+

dapat diperoleh dengan

dan

(Lestari 2007).

dikatakan prima relatif atau koprima jika

gcd( , ) = 1 (Lestari 2007).

≥ 1, didefinisikan ∅( ) adalah

Definisi 2.1.7 (Fungsi-∅ Euler) Untuk banyaknya integer pada selang [1,

] yang prima relatif dengan

disebut fungsi-∅ Euler (Menezes et al. 1997).

. Fungsi ∅

Teorema 2.1.8 (Sifat-sifat fungsi-∅ Euler) prima, maka ∅( ) =

− 1.

1.

Jika

2.

Fungsi-∅ Euler bersifat multiplikatif. Artinya, jika gcd( ) = ∅( )∅( )

∅(

3.

Jika

∅( ) =

=

1−

…

adalah

1−

faktorisasi

⋯ 1−

prima

sebagai produk dari kuasa prima yang khas: bilangan

prima

yang

dari

,

maka

(Menezes et al. 1997).

Fakta 2.1.9 (Teorema Dasar Aritmetika) Setiap integer adalah

, ) = 1 maka

berbeda

=

dan

≥ 2dapat difaktorkan …

adalah

, dimana

integer

positif

(Menezes et al. 1997). 2.2

Integer Modulo

Definisi 2.2.1 (Kongruensi) modulo , ditulis

≡

dan

adalah integer.

(mod , jika )

dikatakan kongruen dengan

membagi habis (

disebut modulus kongruensi (Menezes et al. 1997).

Teorema 2.2.2 (Syarat-syarat Kekongruenan) Untuk semua hal-hal di bawah ini adalah benar. 1)

≡

(mod jika ) dan hanya jika

dan

− .)Selanjutnya , ,

, ,

∈ ℤ,

mempunyai sisa yang sama jika

dibagi dengan . 2) (refleksif)

≡

(mod

) 6

≡

3) (simetri) Jika

≡

4) (transitif) Jika

≡ (mod

5) Jika

≡

dan

(mod maka )

≡

(mod dan )

(mod

) dan

≡

≡ (mod

(mod . )

(mod , maka ) ), maka

)(Guritman et al. 2004).

ekuivalensi) integer {0,1,2, … ,

⇔

=

+

⇔

≡

,

(mod ) ≡ (mod

,

modulo

)

≡ (mod

sedemikian sehingga

(mod , maka )

={ ,

,…,

}

terdapat

)(Lestari 2007).

) Sistem residu tereduksi

, dimana gcd( , ) = 1,

adalah himpunan integer

Selanjutnya setiap

≡

jika untuk setiap integer

Definisi 2.2.5 (Sistem Residu Tereduksi Modulo modulo

)

(Guritman et al. 2004).

. Selanjutnya himpunan

dinamakan sistem residu lengkap modulo satu dan hanya satu

(mod

∈ℤ ,

Definisi 2.2.4 (Sistem Residu Lengkap Modulo ) Jika disebut residu dari

≡ +

− 1} yang dikenai operasi penjumlahan dan

perkalian diperlakukan dalam modulo . Untuk =

(mod . )

, dinotasikan ℤ , adalah himpunan (kelas

Definisi 2.2.3 Integer modulo

+

+

≡

≢

≠.

, jika

yang prima relatif dengan , kongruen dengan suatu

pada

himpunan tersebut (Lestari 2007). Fakta 2.2.6 (Invers) Misalkan

∈ ℤ.

memiliki invers jika dan hanya jika

gcd( , ) = 1 (Menezes et al. 1997).

Definisi 2.2.7 (Invers Multiplikatif) Misalkan modulo

adalah suatu integer

∈ ℤ sehingga

∈ ℤ , Invers multiplikatif dari

≡ 1 (mod . Faktanya ) tidak

semua anggota ℤ mempunyai invers ( belum tentu ada). Dalam hal bersangkutan ada, maka

dinotasikan

=

disebut invertibel dan

invers modulo

disebut invers dari

,

(Guritman et al. 1997).

Definisi 2.2.8 (Pembagian) Misalkan adalah perkalian

yang

dengan

modulo

,

∈ ℤ. Pembagian

oleh

, yang terdefinisi jika

modulo mempunyai


7

Definisi 2.2.9 Grup multiplikatif ℤ adalah ℤ bilangan prima, maka ℤ

∗

= { |1 ≤

≤

∗

={

∈ ℤ | gcd( , ) = 1}. Jika

− 1}(Menezes et al. 1997).

= gcd ( , . Persamaan )

Teorema 2.2.10 (Solusi Persamaan kongruen) Misal ≡

kongruen

(mod mempunyai ) solusi

/ (Menezes et al. 1997).

,

Teorema 2.2.11 (Teorema Sisa Cina) Jika ,

prima relatif satu sama lain, kongruensi

,…,

≡ (mod ≡ (mod ⋮ ≡ (mod

mempunyai solusi unik modulo ,

=

,…,

=

mod

) )

)

… … (∗) …


(i) (Teorema Euler) Jika (ii) Jika maka

dari sistem kongruensi Teorema

=∑

≥ 2adalah integer. ∈ ℤ ∗ , maka

∅(

)

≡ 1(mod

(mod

Teorema 2.2.14 Misalkan

), untuk semua integer

≡

(mod

Jika

3.

Untuk setiap integer ,

2.3

(mod (∅ )),

≡

prima,

− ,1) maka

2.

dan


(Teorema Fermat) Jika gcd( , ) = 1, maka

1.

).

adalah produk bilangan prima berbeda, dan jika ≡

= ⁄

mod , dimana


Teorema 2.2.13 Misalkan

merupakan integer yang

adalah sembarang integer, maka sistem

Algoritme 2.2.12 (Algoritme Gauss’s) Solusi 2.2.11 dapat dihitung sebagai

membagi ,

− 1; solusi ini semua kongruen

solusi antara 0 dan

dalam hal ini terdapat tepat modulo

jika dan hanya jika

≡

≡

(mod

(mod

≡ 1 (mod

).

), untuk semua integer .

()Menezes et al. 1997).

Struktur Aljabar

Definisi 2.3.1 Operasi biner ∗ pada suatu himpunan × ke , yang membawa setiap ( , ) ∈

× ke

adalah suatu fungsi dari ∗

∈ yang unik. Jadi 8

( , )→

∗ . Karena

∗ juga berada dalam

bawah operasi ∗ (Aliatiningtyas 2002).

memenuhi aksioma-aksioma berikut ini, 2. 3.

operasi ∗ bersifat assosiatif ( ada

unsur

∗

=

untuk setiap

identitas

∗

= ,∀

∈ .

∗ )∗

∈ ,

∈ ada unsur

(Aliatiningtyas 2002).

∈,

=

untuk

∈

∗

∗(

∗ ), ∀ ,

,

pada

sehingga

∗

∈.

sehingga

=

∗

berlaku =

disebut grup komutatif jika operasi ∗ bersifat komutatif

Definisi 2.3.3 Grup yaitu ∀ ,

tertutup di

dengan operasi biner ∗ disebut grup jika

Definisi 2.3.2 (Grup) Struktur aljabar

1.

maka dikatakan

∗

=

∗(Aliatiningtyas 2002).

Definisi 2.3.4 (Grup Hingga dan Order) Suatu grup

dikatakan berhingga jika

banyaknya unsur berhingga. Banyaknya unsur dari grup hingga dinamakan order dari , dinotasikan ℴ(

)(Aliatiningtyas 2002).

Definisi 2.3.5 (Order dari Unsur Grup) Misalkan (notasi ℴ( ))adalah integer positif

grup, dan

= . Jika tidak ada

minimal sehingga

bilangan yang demikian, maka dikatakan order dari

∈ . Order

tak hingga atau nol

(Aliatiningtyas 2002). Toerema 2.3.6 Berikut ini 3 sifat dasar yang berkaitan dengan pengertian order. 1.

Misalkan

2.

=

,

Misalkan

grup, , ,…,

grup,

∈ dan ℴ( ) = , maka ada tepat

3.

yaitu

yang semuanya berbeda.

∈ . Jika ℴ( )tak hingga, maka semua kuasa dari

berbeda. Artinya, jika ≠

kuasa dari

dan

adalah dua integer yang berbeda, maka

.

Misalkan

adalah unsur dari grup

hanya jika sehingga

adalah kelipatan dari =

dan ℴ( ) = . Maka ( kelipatan

=

jika dan

artinya ada integer

) (Aliatiningtyas 2002; Guritman 2004).

9

Definisi 2.3.7 (Subgrup) Misalkan dari

jika

⊆ . Maka

grup dan

grup dibawah operasi biner yang sama dengan operasi biner pada . ⊴ ) (Aliatiningtyas 2002).

(Notasi :

Definisi 2.3.8 (Grup Siklik) Suatu grup ∈

hanya jika ada unsur =〈 〉 =

(

berorder , maka

∈ sehingga ℴ( ) =

dikatakan siklik jika dan

disebut generator) sedemikian sehingga

∈ ℤ}(Guritman 2004).

Teorema 2.3.9 Jika grup ada

adalah siklik jika dan hanya jika

(Guritman 2004).

Teorema 2.3.10 (Teorema Lagrange’s) Jika subgrup

disebut subgrup

, maka order dari

grup hingga dan

membagi order dari

adalah

(Menezes et al. 1997;

Aliatiningtyas 2002). Definisi 2.3.11 (Ring) Struktur aljabar 〈

, +,∙〉 dengan operasi + disebut operasi

penjumlahan dan operasi ∙ disebut operasi perkalian, disebut ring jika memenuhi

aksioma-aksioma berikut ini. 1.

〈 , +〉 grup komutatif.

2.

Operasi perkalian bersifat assosiatif.

3.

Hukum

distributif

kiri

berlaku

:

Hukum distributif kanan berlaku : ∀ ,

,

∀ ,

,

∈

∈( ,+ )

(,

=

+ )=

+ .

+.

Unsur identitas terhadap + dinotasikan dengan 0 dan disebut unsur nol. Selanjutnya, 1.

Jika operasi perkalian bersifat komutatif, ∀ ,

∈,

ring komutatif.

2.

disebut

Jika ada unsur identitas dibawah operasi perkalian (unsur ini disebut unsur kesatuan, ∃1 ∈ ,

dinotasikan

1

dan


Definisi 2.3.12 Misalkan

ring. Himpunan bagian

jika

∙1 = 1∙

dengan

= maka

dari

= maka

disingkat

unkes)

∀

disebut ring dengan unsur kesatuan

merupakan ring dibawah operasi dalam

dari ring

∈ ,

disebut subring


10

Definisi 2.3.13 (Ideal) Misal

ring,

disebut ideal jika memenuhi : a.

,

∈

∈ dan

b.

⟹(

−

∈

⟹

) .∈

∈dan

⊆ ,

∈ (Aliatiningtyas 2002).

Teorema 2.3.14 (Ideal Utama) Misalkan 1 dan 〈 〉={

ring komutatif dengan unsur kesatuan

∈ . Suatu himpunan dilambangkan 〈 〉, yang didefinisikan sebagai |

dibangun oleh

ideal. Ideal yang demikian disebut ideal utama yang ∈ merupakan } (Rosdiana 2009).

Definisi 2.3.15 Misalkan adalah

tidak kosong. Himpunan bagian

+

ring,

ideal dari

, maka koset-koset aditif dari

∈ . Definisikan

dengan

/

penjumlahan dan perkalian didefinisikan : ( Teorema 2.3.16 〈

/

(Aliatiningtyas 2002). Definisi 2.3.17 Fungsi ∈ R, berlaku

(

+ )+( + )(

+ )=(

+ )=

={

+ )+ +

+

|

∈. Operasi }


〉 merupakan ring dan disebut ring faktor dari , +,∙

oleh

dari ring R ke ring R’ disebut homomorfisma jika ∀a,b (a + b) = (a) + (b) (ab) = (a) (b)

Kernel

={x∈R|

(x) = 0’}, 0’ unsur nol dari

.’ Jika ada homomorfisma

yang bijektif dari R ke R’, maka dikatakan R isomorfik dengan R’, dinotasikan : R ≃ R’ (Aliatiningtyas 2002).

Teorema 2.3.18 Misalkan θ: R → R’ adalah homomorfisma ring. Maka 1. θ(R) subring dari R’ 2. Ker θ adalah ideal dari R 3. Jika N ideal dari R, maka θ(N) juga ideal dari R’ (Aliatiningtyas 2002). Definisi 2.3.19 (Polinomial) Jika parameter

atas

ring komutatif, maka polinomial dengan

diekspresikan dalam bentuk : ( )=

+ ⋯+

+

+ 11

∈

dimana terbesar

≥ 0.

dan

disebut koefisien dari

≠ 0 disebut derajad

pada

≠ 0, maka

( a)dalah 0, maka

( . ) Jika

( )=

disebut

(polinomial

( )mempunyai derajad 0. Jika semua koefisien

( )disebut polinomial nol dan derajadnya dinotasikan −∞.

( ) dikatakan

Polinomial

( .) Integer

( , )dinotasikan deg ( )dan

koefisien utama (leading coeffisien) dari konstan) dan

dalam

monik

jika

koefisien

utamanya

1


Definisi 2.3.20 ℤ [x] adalah himpunan semua polinomial dalam peubah x dengan

koefisien dalam ring ℤ merupakan sebuah ring di bawah operasi penjumlahan

dan perkalian polinomial (Fraleigh 2000).

Definisi 2.3.21 (Polinomial Irredusibel) Misal berderajad paling kecil 1.

( ) ∈ ℤ[ ]adalah polinomial

( )dikatakan irredusibel atas ℤ jika f(x) tidak dapat

dinyatakan sebagai produk dari dua polinomial berderajad lebih kecil dari f(x) dalam

ℤ [ ].

Dan

dikatakan

redusibel

jika

faktorisasinya

ada

(Menezes et al. 1997). Definisi 2.3.22 Misal polinomial tak-nol

( ), ℎ( ) ∈ ℤ [ ]. Maka

dari

( ) dan ℎ( ), dinotasikan gcd ( ( ), ℎ( )), adalah polinomial monik

berderajad terbesar dalam ℤ [ ]yang membagi 1997).

( )dan ℎ( )(Menezes et al.

Teorema 2.3.23 (Teorema Faktor) Jika ℤ adalah ring komutatif dengan unsur

kesatuan dan

( ) ∈ ℤ[ ] berderajad ≥ 1, maka ( ) = 0 jika dan hanya jika

− adalah faktor dari

( ()Michaels 2000).

Definisi 2.3.24 (Field) Suatu ring yang komutatif, ada unkes dan setiap unsur tak nolnya

mempunyai

invers

(multiplikatif)

lapangan

disebut

(field)

(Aliatiningtyas 2002). Definisi 2.3.25 (Subfield) Jika field operasi penjumlahan dan perkalian di subfield dari , dan

memuat field

(sedemikian sehingga

sama dengan di

disebut perluasan field dari

), maka

disebut

(Pretzel 1992).

12

Definisi 2.3.26 (Finite Field) Suatu field

dikatakan berhingga (finite field) jika

himpunannya memiliki banyak elemen yang berhingga. Order banyaknya anggota

adalah


Teorema 2.3.27 Eksistensi dan kekhasan finite field. 1. 2.

Jika F adalah finite field maka F terdiri dari

unsur dengan p prima dan

≥ 1.

Untuk setiap prima berorder pm, ada finite field yang khas berorder pm. Field ini dinotasikan dengan GF(pm) (Menezes et al. 1997).

Teorema 2.3.28 Misal field berorder

bilangan prima. Himpunan integer modulo

dinotasikan dengan

Teorema 2.3.29 Unsur tak-nol

( atau ) ℤ (Rosdiana 2009).

( ) membentuk sebuah grup di bawah

operasi perkalian disebut grup perkalian dari ( ) ∗ (Menezes et al. 1997).

Teorema 2.3.30

= , untuk setiap

( ), dinotasikan dengan

( )∗ adalah grup siklik yang berorder ∈

Teorema 2.3.31 Finite field dan setiap elemen (Saeki 1997).

( )

( ) adalah perluasan field ℤ berderajad −

adalah akar polinomial

tak-konstan di ℤ [ .] Maka ada perluasan field sedemikian sehingga ( ) = 0 (Fraleigh 2000). adalah perluasan field ℤ .

( ) = 0 untuk beberapa polinomial tak-nol

atas ℤ , maka

− 1 dan berlaku

( ) (Menezes et al. 1997).

Teorema 2.3.32 Misalkan ℤ adalah field dan misalkan

Definisi 2.3.33

berbentuk

atas

dari ℤ

dan ada

∈

∈ disebut algebraic atas ℤ jika

( ) ∈ ℤ[ ]. Jika

tidak algebraic

( ) ∈ ℤ[ ]adalah polinomial irredusibel berderajad

Maka ℤ [ ]/〈 ( )〉 adalah finite field dengan order

perkalian polinomial dilakukan dalam modulo

ℤ

( )adalah polinomial

transcendental atas ℤ (Fraleigh 2000).

Teorema 2.3.34 Misal

,

.

. Penjumlahan dan

( ()Menezes et al. 1997). 13

( ) ∈ ℤ[ ]berderajad

Definisi 2.3.35 Suatu polinomial irredusibel

( )∗ (Menezes et al. 1997).

adalah generator dari

polinomial primitif jika

disebut

Definisi 2.3.36 Misal E perluasan field dari field ℤ dan c ∈ E algebraic atas ℤ .

Polinomial irreducible untuk c atas ℤ dari polinomial monik ( ) dinotasikan

dengan irr(c, ℤ ) dan derajad dari polinomial irreducible untuk c atas ℤ dinotasikan dengan deg(c, ℤ ) (Rosdiana 2009). = ℤ ( ) dengan

Teorema 2.3.37 Misal deg

,ℤ = ,

unik dalam bentuk

≥ 1. Setiap unsur =

2009). Teorema

2.3.38

berderajad

dan

+

dari

+ ⋯+

Diberikan ( ) = 0,

(

∈

algebraic atas ℤ , dan

= ℤ ( )dapat dinyatakan secara

∈ ℤ (Rosdiana

, dimana

polinomial

( )∈ℤ [ ]

irredusibel

) ≅ ℤ [ ]/〈 ( 〉) ≅ ℤ ( ) ≅ {

+

⋯+

+ |

grup,

field. Pada V didefinisikan aturan penjumlahan dan aturan perkalian

skalar.

disebut ruang vektor atas

∈ℤ

untuk semua }(Michaels 2000).

Definisi 2.3.39 (Ruang Vektor) Misal

1.

∈

Untuk setiap

jika memenuhi aksioma berikut.

dan setiap

tertutup terhadap perkalian :

di bawah operasi penjumlahan abelian

⃗ ∈

⃗ =⃗.

∈ dan setiap ⃗,⃗ ∈ ,

terdapat tunggal ⃗ ∈ ⃗ = ⃗+

2.

Untuk setiap

3.

Untuk setiap

4.

Untuk setiap

5.

Untuk setiap ⃗ ∈ , 1 ⃗ = ;⃗1 unsur identitas di 〈

, ,

∈ dan setiap ⃗ ∈ , (

+) ⃗ =

∈ dan setiap ⃗ ∈ , ( ) ⃗ = ( )⃗.

⃗ +⃗.

⃗ +.

sehingga

⃗

,∙〉 (Rosdiana 2009).

Definisi 2.3.40 Misalkan V adalah ruang vektor atas skalar

, dan misalkan

A = {v1, v2, ..., vn} adalah himpunan yang terdiri atas n vektor dalam V. A disebut bebas linear jika (∑ni ci vi = 0) ⇒ (∀i ∈ I = {1,2,…,n} ci = 0).

Ingkarannya, A disebut terpaut linear jika (∑ni ci vi = 0) ∧

∃j ∈ I = {1,2,…,n} cj ≠ 0

(Guritman 2005).

14

Definisi 2.3.41 Misalkan V adalah ruang vektor atas

={ ,

, dan

,…,

}

adalah himpunan berhingga vektor-vektor di dalam V. Untuk menyatakan bahwa V adalah ruang yang direntang oleh vektor-vektor pada himpunan B dituliskan =〈 〉. Artinya ∀

∈ ,

=∑

,

adalah integer.

Definisi 2.3.42 Misalkan V adalah ruang vektor atas , dan B adalah himpunan berhingga vektor-vektor di dalam V. Dikatakan B adalah basis untuk V jika B bebas linear dan V=〈B〉 (Guritman 2005). perluasan field dari field ℤ dan

Teorema 2.3.43 Misal ℤ . Jika deg basis {1, 2.4

, ℤ = , maka ℤ ( )ruang vektor atas ℤ berdimensi- dengan } (Rosdiana 2009).

, ,…,

Masalah Logaritma Diskret

Definisi 2.4.1 (Logaritma Diskret) Misalkan ∈ . Logaritma diskret

generator , dan adalah

integer

unik

0≤

,

(Menezes et al. 1997). Teorema 2.4.2 Misalkan Misal log (

∈ algebraic atas

≤

log

.

dengan basis , dinotasikan log

− ,1 sedemikian

generator grup siklik

adalah sebuah integer. Maka log (

)=

grup siklik berorder

) =(log

mod (Menezes et al. 1997).

=

hingga

berorder

, dan

,

0≤

≤

− 2sehingga

∈.

+ log )mod , dan

Definisi 2.4.3 (Masalah Logaritma Diskret) Diberikan bilangan prima generator dari ℤ ∗, dan

,

,

∈ ℤ ∗ . Masalah logaritma diskret adalah menentukan , ≡

(mod

()Menezes et al. 1997).

Definisi 2.4.4 (Masalah Logaritma Diskret diperumum) Diberikan grup siklik berorder

,

generator

menentukan , 0 ≤

≤

− ,1sehingga

Lemma 2.4.5 Jika order dari

tidak kongruen modulo

, dan

modulo

(Lestari 2007).

∈ . Masalah logaritma diskret adalah =


adalah , maka 1,

, ,…,

saling

15

generator dari ℤ ∗, maka untuk setiap

Teorema 2.4.6 Misalkan ≡

sehingga

(mod

()Lestari 2007). ∈

Teorema 2.4.7 Setiap unsur

( ),

(Rosdiana 2009). Lemma 2.4.8 Andaikan → . Dipilih

∈

menggunakan iterasi ≠

untuk

dan ada

dibangkitkan oleh

=

=

prima, memenuhi

=

ekivalen dengan akar dari persamaan

:

≤ ∅( ) − 1 sedemikian

yang khas pada rentang 0 ≤

terdapat integer

∈ ℤ∗

−

sehingga

=∏

∈

atau

(

−

adalah himpunan hingga dan diketahui ada fungsi untuk membangkitkan barisan =

( ) untuk

≥ 0. Ada

> 0 sehingga

=

,

Lemma 2.4.9 Andaikan bahwa 1 ≤

,

,

,

,

, …, dengan

∈ sehingga ,

. Jika barisan =

menggunakan iterasi

maka hasilnya akan sama dengan barisan

( ( )) untuk

, … (Safaat 2007).

≤ , dan bilangan-bilangan

,

,

=

,…

≥0

,…,

bebas dipilih dari himpunan {1, 2, …, }. Peluang bahwa setiap bilangan 1−

berbeda adalah 2.5

1−

… 1−

(Safaat 2007).

Sistem Persamaan Linear

Definisi 2.5.1 Suatu persamaan linear dalam

peubah (variabel) adalah

persamaan dengan bentuk dimana

,

, …,

dan

+

+ ⋯+

=

adalah bilangan-bilangan real dan

adalah peubah. Dengan demikian maka suatu sistem linear dari dalam

,

, …, persamaan

peubah adalah satu sistem berbentuk : +

+ dimana

dan

)

+

+⋯+ +⋯+ ⋮

+ ⋯+

=

= =

semuanya adalah bilangan-bilangan real (Leon 1998).

16

Definisi 2.5.2 Suatu sistem persamaan linear dikatakan homogen jika konstantakonstanta di ruas kanan semuanya nol. Sistem-sistem homogen selalu konsisten (Leon 1998). Teorema 2.5.3 Sistem persamaan linear homogen >

taktrivial jika 2.6

(Leon 1998).

× memiliki penyelesaian

Algoritme Berlekamp’s Q-matrix

Algoritme 2.6.1 Algoritme Berlekamp’s Q-Matrix Input : Polinomial monik bebas kuadrat Output : Faktorisasi 1.

Untuk

2.

∑

Bentuk matriks

3.

Tentukan basis

setiap

,

,

∈

5.

← { ( )}.

Untuk 1 ≤

dalam

( d) alam polinomial irredusibel monik.

,

matriks identitas 4.

( b) erderajad

0≤ .

×

,…,

≤

− ,1 hitung

polinomial

untuk ruang null pada matriks (

× . Banyaknya faktor irredusibel pada

[ ]. mod ( ) = − ), dengan

( a)dalah .

≤ , lakukan langkah berikut :

5.1 Untuk setiap polinomial ℎ( ) ∈ , degℎ( ) > 1, lakukan langkah berikut Hitung gcd (ℎ( ),

6.

), untuk setiap

∈

, dan ganti ℎ( )pada

dengan semua polinomial hasil perhitungan gcd yang berderajad ≥ 1.

Hasilnya adalah polinomial-polinomial F yang berupa faktor-faktor irredusibel

2.7

( )−

( ()Menezes et al. 1997).

Kompleksitas Waktu Asimptotik Algoritme aritmetik yang dihasilkan dalam penelitian ini akan dianalisis

dari segi fungsi kompleksitas waktu (time-complexity function), yaitu sebagai fungsi untuk mengukur banyaknya operasi dalam suatu algoritme yang mempunyai variabel input . Yang dimaksud dengan banyaknya operasi adalah banyaknya operasi dasar (jumlah, kurang, kali dan bagi) ditambahkan dengan assignment dan perbandingan (ekspresi logika) (Guritman 2004). Hal ini perlu

17

untuk mengetahui kinerja algoritme. Kinerja algoritme akan tampak untuk besar, bukan pada

kecil.

Langkah pertama dalam pengukuran kinerja algoritme adalah membuat makna sebanding. Gagasannya adalah dengan menghilangkan faktor koefisien di ( .) Sebagai contoh, andaikan bahwa kompleksitas waktu

dalam ekspresi

terburuk dari sebuah algoritme adalah pertumbuhan dibandingkan 2

( )sebanding dengan 2

( )=2

, suku 6

+6

. Suku-suku yang tidak mendominasi perhitungan pada rumus

mengabaikan koefisien 2), ditulis ( ) = ( )=

berorder paling besar ( )≤

Teorema

( )), untuk

2.7.2

polinom derajad

besar,

+ 1 menjadi tidak berarti

( )dapat diabaikan, sehingga kompleksitas waktu

Definisi 2.7.1

+ 1. Untuk

( )adalah

( ).

( ( )) (dibaca ” ( )adalah

( ))bila terdapat konstanta C dan

Bila

≥

(dengan

( ( ))” artinya

( )

sedemikian sehingga

(Munir 2001).

( )=

maka ( ) =

+

( ) (Munir 2001).

Setelah mendefinisikan fungsi

+ ⋯+

+

adalah

( )untuk suatu algoritme, kemudian

dengan Tabel Oh-Besar (Menezes et al. 1997) kita tentukan order dari

sebagai

ukuran efisiensi algoritme yang bersangkutan. Dalam tabel berikut diberikan beberapa bentuk Oh-Besar yang sering muncul dalam aplikasi analisis algoritme (Guritman 2004). Urutan batasan lebih baik disusun dari atas ke bawah. Tabel 2.7.1 Oh-Besar Bentuk Oh-Besar

Nama

O(1) O(log2 n) O(n) O(n log2 n) O(n2) O(n3) m O(n ), m = 0, 1, 2, ... O(cn), c > 1 O(n!)

konstan logaritmik linear n log2 n kuadratik kubik polinomial eksponensial faktorial 18

19

BAB III HASIL DAN PEMBAHASAN Pada bab ini akan dijelaskan hal-hal yang berhubungan dengan masalah (2 ) dan bagaimana mengeksplorasinya dengan

logaritma diskret pada

menggunakan algoritme Exhaustive Search, Baby-Step Giant-Step, Pollard’s rho, Pohlig-Hellman, dan Index Calculus.

3.1

MASALAH LOGARITMA DISKRET PADA FINITE FIELD ( )

3.1.1 FINITE FIELD

( )

Galois Field adalah nama populer untuk field dengan jumlah elemen terbatas (finite). Disebut Galois Field, sebagai penghargaan terhadap Evariste Galois yang menemukan hubungan antara grup dan persamaan polinomial. Galois ( ), berorder

Field dinotasikan

, dengan

= 1, maka menurut Teorema 2.3.28

Jika

prima dan

integer positif.

( (atau ) bisa juga dinotasikan ℤ )

adalah integer modulo p berbentuk field berorder . Setiap operasi aritmetikanya dilakukan dalam modulo

(.)

agar hasilnya tetap berada dalam daerah (2 ).

Selanjutnya pembahasan akan difokuskan pada

(2) adalah perluasan field

Berdasarkan Teorema 2.3.31

ℤ .

Berdasarkan Definisi 2.3.20 ℤ [x] adalah himpunan semua polinomial dalam

peubah x dengan koefisien dalam ℤ merupakan sebuah ring di bawah operasi penjumlahan dan perkalian polinomial. Misalkan

ℤ [ ], maka berdasarkan Teorema 2.3.32 ada ( ) = 0. Jika ada

seperti ini, maka

( p) olinomial tak konstan atas

∈

(2) sedemikian sehingga

disebut algebraic atas ℤ (Definisi

2.3.33). Selanjutnya berdasarkan Teorema 2.3.43, jika deg( , ℤ ) = ℤ ( ) merupakan {

,

,

,….,

ℤ

berderajad

ruang

,

vektor

}.

ℤ adalah field. Misalkan

atas

ℤ

berdimensi-

dengan

, maka

basis

( ) ∈ ℤ[ ]adalah polinomial irredusibel atas

, maka menurut Teorema 2.3.14 〈 ( 〉) adalah suatu ideal,

dengan 〈 ( 〉)= { ( ) ( )| ( ) ∈[ℤ]}. Selanjutnya, berdasarkan Teorema

2.3.34 ℤ [ ]/〈 ( 〉)adalah finite field berorder 2 , dengan operasi penjumlahan ( .)

dan perkalian polinomial dilakukan dalam modulo

Dari uraian di atas dan berdasarkan Teorema 2.3.37 dan Teorema 2.3.38, maka

∈ ℤ ( ) dapat

setiap

=

+

+

dinyatakan

+ ⋯+

+

∈ℤ , 0≤

+

+⋯+

dalam

bentuk

≤

− ,1dan

|

∈ℤ

+ 1 adalah polinomial irredusibel berderajad 4 atas ℤ , dan

( )=0 ⟺

+

+1=0 ⟺

(2 ) = ℤ [ ]/〈 ( 〉) ={

unik

( ))

Contoh 1 (Finite Field ( )=

secara

, dimana

(2 ) ≅ ℤ [ ]/〈 ( )〉 ≅ ℤ ( ) ≅{

untuk semua }.

dan ( ) = 0,


jika diberikan polinomial irredusibel

,

= {0,1,

1+

,

, ,

,

+ ,

,

,

,1 +

+

,

,

+

=

,

,

+ 1, maka

,

+ ,

,1 +

+

, +

,

,1 + +

,

,

,

+ ,1 +

,1 +

,

+

,

}

+ ,

, 1+

}

Dari uraian di atas, ada beberapa cara yang dapat dilakukan untuk merepresentasikan

(2),

elemen-elemen

diantaranya

adalah

dengan

representasi grup siklik, representasi polinomial, representasi vektor dan representasi himpunan. 1) Representasi grup siklik : 0, (2)∗ , dimana

0

(2 )∗ =

1

,

, ...,

, dengan

(2 ) − {0}.

:

2) Representasi polinomial dalam peubah , dimana

∈ℤ ,0≤

3) Representasi vektor : [ ,

,

4) Representasi himpunan : { ,

≤

− .1

, ...], dengan ,

∈ℤ

, ...}, dengan

Cara merepresentasikan elemen-elemen

adalah generator

+

+

+⋯+

≥ 0.

(2 ) dengan representasi himpunan

mengacu pada tesis Rosdiana 2009. Representasi himpunan selanjutnya diperlukan pada saat komputasi untuk menentukan masalah logaritma diskret. Pada contoh 1 di atas cara merepresentasikan elemen-elemen

(2) adalah 20

dengan representasi grup siklik dan representasi polinomial. Tabel 3.1.1 berikut memperlihatkan elemen-elemen ()

Tabel 3.1.1 Elemen-elemen

(2) dalam beberapa representasi.

Representasi

Representasi

Representasi

Representasi

Himpunan

Vektor

Grup Siklik

Polinomial

1

{}

[0,0,0,0]

0

0

2

{0}

[1,0,0,0]

1

1

3

{1}

[0,1,0,0]

1

1

4

{2}

[0,0,1,0]

2

2

5

{3}

[0,0,0,1]

3

3

6

{0,1}

[1,1,0,0]

4

7

{1,2}

[0,1,1,0]

5

8

{2,3}

[0,0,1,1]

6

1+

9

{0,1,3}

[1,1,0,1]

7

10

{0,2}

[1,0,1,0]

8

11

{1,3}

[0,1,0,1]

9

12

{0,1,2}

[1,1,1,0]

10

13

{1,2,3}

[0,1,1,1]

11

14

{0,1,2,3}

[1,1,1,1]

12

15

{0,2,3}

[1,0,1,1]

13

16

{0,3}

[1,0,0,1]

14

No

+

+

1+

1+ +

1+ 1+

+

1+

+

1+

2 3

+

3

+

2

2

3

3

+ +

+

3 3

3

(2) dilakukan terhadap polinom yang tidak

Setiap operasi aritmetika

dapat direduksi lagi (irredusibel) dalam ℤ . Secara umum dapat dituliskan sebagai ( )adalah polinomial irredusibel atas ℤ berderajad

berikut. Misalkan

operasi penjumlahan dan perkalian dalam berikut : 1.

(2) dapat didefinisikan sebagai

Penjumlahan Jika

=

∈

+

dengan 2.

, maka

Perkalian

+

+ ⋯+

(2 ). Maka ≡

+

+

, = , dimana

(mod 2).

=

+

= +

+

+

+ ⋯+ + ⋯+

21

=

Jika

+

+

∈

dengan

+ ⋯+

(2). Maka

.

=∑

=

,

= , dimana s=

(mod 2), 0 ≤

+

≤

+

+ − .1

+ ⋯+

+

+⋯+

(2) ini dihitung dengan

Penjumlahan dan perkalian dalam

menggunakan algoritme standar untuk integer dan aritmetika polinomial. Unsur identitas penjumlahannya adalah polinomial 0, dan unsur identitas perkaliannya adalah polinomial 1. Pengurangan adalah invers dari penjumlahan; jika ∈

(2) maka invers penjumlahan dari

+

adalah solusi unik untuk persamaan

(dinotasikan (− ))pada = 0dalam ∈

pembagian adalah invers dari perkalian; jika dari .

) pada

(dinotasikan = 1pada

(2)

(2). Selanjutnya,

(2) maka invers perkalian

(2 ) adalah solusi unik untuk persamaan

(2). Invers perkalian dalam

(2 ) dapat dihitung secara

efisien dengan menggunakan Algoritme Euclidean yang Diperluas. Dalam pembahasan selanjutnya akan dibahas

(2) tanpa elemen {0},

(2)∗ , membentuk grup di bawah operasi perkalian

dinotasikan dengan (Definisi 2.3.29).

( )∗

3.1.2 MASALAH LOGARITMA DISKRET PADA

(2 )∗ adalah grup siklik yang berorder

Berdasarkan Teorema 2.3.30,

(2 )∗ merupakan grup siklik maka terdapat suatu

= 2 − 1. Karena

(2)∗ yang disebut elemen primitif. Jika

generator yang membangun diberikan

(2 )∗ dan diketahui order dari

elemen primitif dari

adalah , maka ℴ( ) =

(Teorema 2.3.9), sehingga : (2)∗ = 〈 〉 = { ,

dan berdasarkan Teorema 2.3.6

,

,

,…,

,

,…,

(2)∗

}

semuanya berbeda.

Berdasarkan Definisi 2.4.1 dan Definisi 2.4.4, jika diberikan grup siklik (2)∗ berorder

,

generator

(2)∗,

polinomial irredusibel atas ℤ . Logaritma diskret unik , 0 ≤

≤

− ,1sedemikian sehingga : ≡

(mod ( ))

∈

(2)∗ , dan

dengan basis

( ) adalah

adalah integer (1)

22

dan bagaimana menentukan rentang 0 ≤ ≡

≤

disebut masalah logaritma diskret. Nilai

pada

− 1 yang merupakan solusi masalah logaritma diskret

(mod ( )) dijamin ada (Teorema 2.4.6).

Menentukan masalah logaritma diskret menjadi sulit apabila order grup

multiplikatif

(2)∗ besar. Karena itu diperlukan suatu teknik tertentu untuk

menyelesaikannya. Beberapa teknik yang dapat digunakan untuk menentukan

masalah logaritma diskret ini adalah Algoritme Exhaustive Search, Baby-Step Giant-Step, Pollard’s rho, Pohlig Hellman, dan Index Calculus. Dalam Menezes et el. (1997) kelima algoritme tersebut dikenakan pada grup siklik G umum, sedangkan pada tulisan ini dikenakan pada sistem aritmatik grup multiplikatif (2)∗ . ( )∗

3.2 SOLUSI MASALAH LOGARITME DISKRET PADA

Untuk menentukan masalah logaritma diskret diatas ada beberapa algoritme yang bisa digunakan, diantaranya adalah Algoritme Exhaustive Search, Baby-Step Giant-Step, Pollard’s rho, Pohlig-Hellman dan Index Calculus. Algoritme untuk menentukan masalah logaritma diskret dalam Menezes et al. (1997) dijelaskan secara umum dalam grup siklik berhingga generator ℤ

∗

berorder

dengan

, dan untuk pendekatan yang lebih konkrit dipilih grup multiplikatif

berorder

− 1dimana operasi grupnya adalah operasi perkalian modulo .

Pada tulisan ini algoritme-algoritme tersebut dieksplorasi untuk menentukan masalah logaritma diskret pada

(2)∗ .

3.2.1 Solusi Masalah Logaritma Diskret pada Exhaustive Search

( )∗ dengan Algoritme

Ide dasar Algoritme Exhaustive Search adalah Definisi Masalah Logaritma Diskret (Definisi 2.4.4).Misalkan algebraic atas ℤ , maka

( )adalah polinomial irredusibel atas ℤ dan

(2)∗ = 〈 〉 = {1,

Menentukan masalah logaritma diskret

pada

, ,… ,

=

(2 )∗ sehingga

,…,

=

}.

dengan

Algoritme Exhaustive Search adalah dengan mencoba semua kemungkinan nilai ,0≤

≤ 2 − 2, sampai ditemukan

yang benar, artinya jika

dipangkatkan

23

akan sama dengan

( )dinotasikan

dalam mod

≡

(mod ( )). Atau

dengan bahasa sederhana untuk menentukan masalah logaritma diskret , kalikan dengan

sampai ditemukan . Banyaknya langkah dalam proses perkalian ini

adalah , 0 ≤

≤ 2 − 2.

. .

=

.

=

=

.

⋮

.

Selama proses perkalian jika ditemukan

=

=

=

≥ , maka

direduksi ke mod

(2)

( )

dan dalam proses reduksi berlaku aturan penjumlahan dan perkalian dalam (2). Selanjutnya dari (1) dan (2) diperoleh : =

=

log Jadi

= log =

( )). ≡ mod (

=

Berikut Algoritme Exhaustive Search yang dieksplorasi dari Definisi Masalah Logaritma Diskret secara umum (Definisi 2.4.4) Algoritme 3.2.1 Algoritme Exhaustive Search untuk menentukan masalah logaritma diskret pada

Input :

(2)∗

∈

(2)∗ , dan

Output : logaritma diskret

2)

Untuk setiap , 0 ≤

3)

Solusi dari

1)

(2)∗ berorder

generator grup multiplikatif

( p) olinomial irredusibel atas ℤ berderajad ≡ log

≤

(mod ( )).

− ,1hitung nilai

Setelah langkah ke- dimana ≡

= 2 − 1,

≡

.

(mod ( )).

(mod ( )), maka proses berhenti.

(mod ( )) adalah

≡ mod (

).

24

Dalam Menezes et al. (1997) nilai harapan kompleksitas waktu Algoritme Exhaustive

Search

(2 ).

adalah

Algoritme

Exhaustive

Search

ini

diimplementasikan dengan bantuan sofware Maple 11, dapat dilihat pada Lampiran 3.1 Contoh 2 (Menentukan masalah logaritma diskret pada grup multiplikatif (2)∗ dengan Algoritme Exhaustive Search)

Diketahui :

(2)∗ ,

adalah generator grup multiplikatif =

( )=

≡ log

Tentukan Solusi :

+

+

+

(2 )∗ , dan

+1 ∈

+ 1.

(mod ( )).

(2)∗ dibangun oleh suatu polinomial

Grup multiplikatif

irredusibel atas ℤ . Diketahui

adalah generator grup multiplikatif

(2)∗ adalah perkalian dalam modulo

Perkalian dari elemen-elemen sehingga +

sebab 1 ≡ −1 dalam ℤ .

Grup multiplikatif

kemungkinan nilai , 0 ≤ +

+

+ 1 ≡ 0 mod ( ) ≡−

(2)∗ berorder

−1 ≡

= 2 − 1 = 127, artinya ada 127

≤ 126, yang memenuhi

+ 1(mod ( )).

nilai yang benar yang memenuhi

≡

Tabel 3.2.1 Representasi Polinomial (

0 1

+

+

( ,)

+ 1(mod( )),

Kita akan coba untuk setiap kemungkinan nilai , 0 ≤

=

(2)∗ .

( ) ≡ 0(mod ( ))

≡

Dengan Algoritme Exhaustive Search, akan dicari nilai ≡

( )berderajad 7

+1

(mod ( )).

(mod

(mod ( )).

sedemikian sehingga

≤ 126, sampai ditemukan

( ))untuk

(2)∗ dengan

mod ( ) 1

25

mod ( )

2 3 4 5 6 7

+1

8

+

9

+

10

+

11

+

12

+

13

+

14 15

+

17

+

18

+

19

+

20 21

Dengan

+1

+

16

Pada saat

+1

+

+

+1

+

+

+1

= 21, diperoleh kongruensi

demikian

diperoleh

solusi

≡

dari

≡ (mod ) ≡ 21 (mod 127).

3

+

2

+

≡ log

+1≡

(mod ( )).

(mod ( ))

adalah

Karena Algoritme Exhaustive Search ini metodenya yaitu dengan mencoba

semua kemungkinan solusi yang ada, maka solusi yang tepat secara pasti akan ditemukan. Namun kelemahannya adalah kompleksitas waktu yang besar sehingga tidak efisien digunakan untuk menyelesaikan masalah logaritma diskret dalam

(2)∗ berorder besar. Oleh karena itu diperlukan metode lain agar

penyelesaian masalah logaritma diskret pada kasus

yang relatif besar.

(2 )∗ menjadi lebih efisien untuk

26


3.2.2 Solusi Masalah Logaritma Diskret pada Baby-Step Giant-Step

Algoritme Baby-Step Giant-Step pertama kali dipublikasikan oleh Shanks pada tahun 1971. Algoritme ini merupakan time-memory trade-off dari Algoritme Exhaustive Search yakni situasi dimana memori komputer digunakan untuk mengurangi biaya dan waktu eksekusi program (Menezes et al. 1997). (2 )∗ yang

Berikut analisis Algoritme Baby-Step Giant-Step untuk dieksplorasi dari Algoritme Baby-Step Giant-Step untuk grup siklik

(2 )∗ , dengan order

adalah sebuah generator grup siklik

Misalkan (2)∗ adalah ,

(2)∗ dan

∈

( )polinomial irredusibel berderajad

atas ℤ . Masalah logaritma diskret adalah menentukan

sedemikian

≡ log

sehingga

umum.

(mod

( )) .

, 0≤

Untuk

≤

− ,1

menentukan

(mod ( )), dengan Algoritme Baby-Step Giant-Step ada dua fase

≡ log

yang harus dilewati yaitu fase baby-step dan fase giant-step. Ide dasarnya adalah membagi {1,

dengan

, ,…,

=√

,

}.

, sampai ditemukan

dalam himpunan

=√

Langkah pertama menentukan nilai

dimaksudkan untuk

menentukan batas minimal banyaknya representasi polinomial

yang akan

disimpan dalam memori komputer. Langkah ( , (mod

kedua

( ),) 0 ≤

polinomial sebanyak

{

,

,

,…,

adalah <

membentuk

tabel

dengan

pasangan

− ,1dimaksudkan untuk menentukan representasi

yang akan disimpan di memori komputer, yakni

}. Untuk membentuk tabel pasangan ( , (mod

( ))dapat

digunakan Algoritme Exhaustive Search. Selanjutnya representasi polinomial– polinomial

disimpan dalam memori komputer. Penyimpanan representasi

polinomial–polinomial

ini disebut fase baby-step.

Langkah ketiga Algoritme Baby-Step Giant-Step adalah menentukan nilai dan

sedemikian sehingga

adalah dengan membagi ditemukan

≡

(mod

( ),) untuk suatu

dengan representasi polinomial

yang merupakan salah satu anggota {

,

,

,…,

≥ 1. Caranya

sampai

}. Banyak 27

langkah dalam proses pembagian ini adalah . Dalam proses pembagian ini (2 ).

berlaku aturan penjumlahan dan perkalian polinomial dalam ∶

∶ (

Untuk menentukan nilai

(

dan

)

∶

=

:

=

= ⋮

)

∶

(

=

=

=

(1)

dengan cara membagi

sama artinya dengan mengalikan

polinomial

)

dengan representasi

dengan polinomial

. Kalau

cara kedua ini yang digunakan maka langkah pertama adalah menentukan dengan menggunakan Algoritme Euclidean yang Diperluas. Selanjutnya kalikan dengan representasi polinomial menghitung nilai

sampai diperoleh

ini disebut fase giant-step.

=

. Proses

Jika sudah ditemukan nilai dan , maka selanjutnya dapat ditentukan nilai logaritma diskret . Berdasarkan Definisi Logaritma Diskret : mod ( )

≡ log

Sehingga dari (1) dan (2) diperoleh :

⇔

mod ( )

≡

(2)

=

=

log Jadi solusi dari Algoritme 3.2.2

= −

mod ( ) adalah

≡

= log =

=

=

+

+

≡ log

mod ( ) .

Algoritme Baby-Step Giant-Step untuk menentukan masalah logaritma diskret pada Input :

(2 )∗

generator grup siklik ∈

(2)∗ , dan


(2)∗

berorder

= 2 − 1, dan


(mod ( )).

.

28

=√

1)

Menetapkan nilai

2)

Bentuk tabel dengan pasangan ( ,

3)

Hitung

, kemudian tetapkan nilai

mod ( ) ), dimana 0 ≤

Bentuk tabel dengan pasangan ( , nilai dari

4)

Solusi dari

=

.

(mod ( )) adalah

≡

=

.

mod( ) ), ≡

≤

− .1

≥ 0, sampai diperoleh

+ mod (

).

Dalam Menezes et al. (1997) nilai harapan kompleksitas waktu Algoritme (√2 ). Implementasinya dengan bantuan sofware

Baby-Step Giant-Step adalah

Maple 11 dapat dilihat pada Lampiran 3.3.

Contoh 3 (Menentukan masalah logaritma diskret pada grup multiplikatif (2)∗ dengan Baby-Step Giant-Step)

Diketahui :

=

( )=

+

≡ log

Tentukan

Penyelesaian : 1.

(2)∗ ,


Order dari

+

+

+

+ 1.

+1∈

(2 )∗ , dan

(mod ( )).

(2)∗ adalah

= 2 − 1 = 127

= √127 = 12. Artinya banyaknya representasi polinomial

Jadi

akan disimpan di memori komputer minimal adalah 12, 0 ≤ 2.

{

,

,

( )=

,…, +

}

+ 1 polinomial irredusibel atas ℤ , dengan

(2)∗ sehingga :

( ) ≡ 0 mod ( )

⟹

⟹

+

≡

+1≡0 +1

yang

≤ 11, yakni generator

mod ( )

mod ( )

29

Tabel 3.2.2 Representasi Polinomial ( =

+

+

+

+1

(mod

(2)∗ dengan

( ))untuk

Representasi polinomial mod ( )

0

1

1 2 3 4 5 6 +1

7 8

+

9

+

10

+

11

+

≥ 7, maka polinomial

Pada Tabel 3.2.2 ini terlihat jika 3.

mod

( .)

Menentukan

nilai

(mod ( )).

≡

= 0,1,2, … yang

,

Agar

mudah

mod ( ). Untuk menentukan

direduksi ke

memenuhi

tentukan

kongruensi

terlebih

dahulu

gunakan Algoritme Euclidean

Diperluas :

+1 +

0

+

+1

+1

+1

1

+1 mod ( ) =

+1

+

+1

Jadi

+

+

0

+

1

+

+

+1

+ 1. 30

,

Tabel 3.2.3 Hasil Perhitungan =

dengan

+

+

:

+

mod ( ) ,

Representasi Polinomial ≡ : +

0 1

+

2 3 Pada saat 4.

+

+

Jadi solusi

mod ( ) +

+

+1

+1

+

+

+

= 3, diperoleh nilai = log

+ 1.

(2 )∗

≥ 0untuk

mod ( )

=

=

=

+

+

, dengan

= 3.12 + 11 = 47

= 11.

Tiga algoritme berikut (Algoritme Baby-Step Giant-Step 2, Algoritme Baby-Step Giant-Step 3, Algoritme Naif Square) juga dieksplorasi dari Algoritme Baby-Step Giant-Step untuk grup siklik

umum. ( )∗ dengan Algoritme

3.2.3 Solusi Masalah Logaritma Diskret pada Baby-Step Giant-Step 2 Misalkan

(2 )∗ , dengan order

adalah sebuah generator grup siklik

(2)∗ adalah ,

∈

(2)∗ dan



sedemikian ≡ log

sehingga

≡ log

(mod

( )) .

, 0≤

Untuk

≤

− ,1

menentukan

(mod ( )), dengan Algoritme Baby-Step Giant-Step 2 juga ada dua

fase yang harus dilewati yaitu fase baby-step dan fase giant-step. Ide dasarnya dengan

adalah membagi {1,

, ,…,

, sampai ditemukan

}.


=√

dalam himpunan

dimaksudkan untuk

menentukan batas minimal banyaknya representasi polinomial disimpan dalam memori komputer. Sebenarnya boleh kurang atau lebih dari √

yang akan

tidak harus sama dengan √ ,

tergantung dari kapasitas memori komputer

yang digunakan, tetapi pada tulisan ini untuk komputasi diambil nilai

=√ . 31

Langkah ( , (mod

sebanyak

kedua

( ),) 0 ≤

adalah <

membentuk

tabel

dengan

pasangan

− ,1 dimaksudkan untuk menentukan polinomial

yang akan disimpan di memori komputer, yakni {

Untuk membentuk tabel pasangan ( , (mod

,

,

,…,

}.

( ))dapat digunakan Algoritme

Exhaustive Search. Selanjutnya representasi polinomial–polinomial

dalam memori komputer. Penyimpanan polinomial–polinomial

disimpan

ini disebut fase

baby-step. Langkah ketiga Algoritme Baby-Step Giant-Step adalah menentukan nilai ≡

dan sedemikian sehingga adalah dengan membagi

( ),) untuk suatu

(mod


yang merupakan salah satu anggota {

,

,

≥ 1. Caranya

sampai ditemukan

,…,

}. Banyak langkah

dalam proses pembagian ini adalah . Dalam proses pembagian ini berlaku aturan (2).

penjumlahan dan perkalian polinomial dalam ∶

∶ (

Proses menghitung nilai

(

)

=

:

=

= ⋮

∶

)

(

=

∶

=

=

)

(1)


Jika sudah ditemukan nilai dan , maka selanjutnya dapat ditentukan nilai logaritma diskret . Berdasarkan Definisi Logaritma Diskret : ≡ log

mod ( )


⇔

≡

mod ( )

(2)

=

=

log Jadi solusi dari

≡

= −

mod ( ) adalah

= log =

=

=

+

+

≡ log

mod ( ) . 32

Algoritme 3.2.3 Algoritme Baby-Step Giant-Step 2 untuk menentukan masalah logaritma diskret (2 )∗

pada Input :

∗

∈

(2) , dan

=√

Menetapkan nilai

2)

Bentuk tabel dengan pasangan ( ,

, kemudian tetapkan nilai

mod ( ) ), dimana 0 ≤

Bentuk tabel dengan pasangan ( , nilai dari

4)

Solusi dari

=

.

(mod ( )) adalah

≡

.

(mod ( ))

≡ log

1)

Hitung

= 2 − 1,

berorder

( p) olinomial irredusibel atas ℤ berderajad


3)

(2)∗


=

.

mod( ) ), ≡

≤

− .1

≥ 0, sampai diperoleh

+ mod (

).


Baby-Step Giant-Step adalah


Contoh 4 (Menentukan masalah logaritma diskret pada grup multiplikatif (2)∗ dengan Baby-Step Giant-Step 2)

Diketahui :

adalah generator grup multiplikatif =

( )=

+

+

+

+ 1.

Penyelesaian :

(2)∗ adalah

1) Order dari

+1∈

(2 )∗ , dan

(mod ( )).

≡ log

Tentukan

+

(2)∗ ,

= 2 − 1 = 127

= √127 = 12. Artinya banyaknya representasi polinomial

Jadi

akan disimpan di memori komputer minimal adalah 12, 0 ≤ {

,

,

2) ( ) =

,…, +

}

+ 1 polinomial irredusibel atas ℤ , dengan

(2)∗ sehingga :

( ) ≡ 0 mod ( )

⟹

+

+1≡0

≤

yang − ,1yakni generator

mod ( ) 33

⟹

≡

mod ( )

+1

Representasi polinomial yang akan disimpan di memori komputer dapat dilihat pada Tabel 3.2.2 hal 30. 3) Menentukan

nilai

= 0,1,2, …

,

yang

(mod ( )). Agar mudah menentukan

≡

memenuhi

kongruensi

terlebih dahulu tentukan

(mod ( )) dengan menggunakan Algoritme Euclidean yang Diperluas : +

+

≡

Jadi

Tabel 3.2.4

+

+

+1 +

+ =

+

+

+

+

dengan

=

+

+1

1

:

+

(mod ( )).

+

mod ( ) ),

Representasi Polinomial ≡ : +

0 2

+

3 4

+

≥ 0untuk

+

+

(2)∗

mod ( ) +

+

+

+

+

5 6

4) Jadi solusi

+ 1.

+

1

+1

α +α +α +α

1

Pada saat

+

+

0

+

Hasil Perhitungan ( ,

0

+1

+

+1

= 6, diperoleh nilai

= log

+

mod ( )

=

=

+

=

, dengan

= 5.

= 6.7 + 5 =.47

34


3.2.4 Solusi Masalah Logaritma Diskret pada Baby-Step Giant-Step 3 Misalkan

(2)∗ adalah

dengan order irredusibel

berderajad

atas

, 0≤

menentukan

(2)∗,

adalah sebuah generator grup multiplikatif

≤

ℤ .

Masalah

(2)∗ dan

( ) polinomial

logaritma

− ,1 sedemikian sehingga

diskret

≡ log

adalah

(mod

( )) .

(mod ( )) seperti halnya pada Algoritme

≡ log

Untuk menentukan

∈

,

Baby-Step Giant-Step dan Algoritme Baby-Step Giant-Step 2, Algoritme BabyStep Giant-Step 3 juga harus melewati fase baby-step dan fase giant-step. Ide dengan

dasarnya adalah membagi 0≤

<

, 0≤

≤

sampai ditemukan

− ,1 integer positif, 0 ≤

salah satu anggota himpunan {1,

, ,…,


< , dengan

}.

,…,

= 2, 0 ≤

<

= 2,

;

adalah

, dimaksudkan

untuk menentukan batas minimal banyaknya representasi polinomial 0≤

≤

− .1yang akan disimpan di memori komputer.

( ,

mod ( ) ), ∀ , dimana 0 ≤

Langkah

kedua

representasi polinomial {

,

,

,…,

adalah

membentuk ≤

tabel

dengan

,

pasangan

− ,1dimaksudkan untuk menentukan


}. Sama seperti pada algoritme Baby-Step Giant-Step, untuk

membentuk tabel pasangan ( , (mod

( ))) juga dapat digunakan Algoritme

Exhaustive Search. Fase ini disebut fase baby-step.

Langkah ketiga Algoritme Baby-Step Giant-Step 3 adalah menentukan nilai , 0≤ {

,

dan < ,

sedemikian sehingga ≥ 0. Caranya adalah membagi

sampai ditemukan ,

,…,

, dimana

≡

(mod

( ),) untuk suatu


merupakan salah satu anggota

}. Dalam proses pembagian ini berlaku aturan penjumlahan (2 ). Banyak langkah dalam proses

dan perkalian polinomial dalam pembagian ini adalah .

∶

:

=

= 35

(

=

)

=

⋮

∶

(


∶ )

∶

(

=

=

)

(1)


Jika sudah ditemukan nilai ,

dan , maka selanjutnya dapat ditentukan

nilai logaritma diskret . Berdasarkan Definisi Logaritma Diskret : mod ( )

≡ log

⇔


mod ( )

≡

(2)

=

=

log Jadi

solusi

mod ( ) .

log

−

= log =

=

+

+

mod ( )

≡

dari

=

+

=

adalah

+

+

Algoritme 3.2.4

Algoritme Baby-Step Giant-Step 3 untuk menentukan masalah logaritma diskret (2 )∗

pada Input :

(2)∗ berorder

generator grup multiplikatif (2)∗ , dan

∈

Output : logaritma diskret 1)

Tetapkan nilai

2)

Bentuk

3)

0≤

4)

untuk suatu 0 ≤

tabel ≤

− .1

Mencari nilai , Solusi dari

≡


= 2, 0 ≤

dengan

<

dan

.

(mod ( )).

pasangan

.

( ,

mod ( ) ),

dan , sedemikian sehingga <

= 2 − 1,

≥ 0.

(mod ( )) adalah

≡

+

∀ ,

≡

(mod

+ mod(

).

dimana ( )) ,

36

≡

Nilai harapan kompleksitas waktu Algoritme Baby-Step Giant-Step 2 (√2 ) (Menezes et al. 1997). Implementasinya dengan bantuan sofware

adalah


dengan Baby-Step Giant-Step 3) =

( )=

+

Penyelesaian : +

+

+

+

(2 )∗ , dan

+1∈

+ 1.

(mod ( )).

≡ log

Tentukan ( )=

(2)∗ ,


Diketahui :

(2 )∗

=

Contoh 5 (Menentukan masalah logaritma diskret pada grup siklik

+ 1irredusibel atas ℤ . Ambil

=√

= √2− 1 = 12. Jadi

banyaknya representasi polinomial yang akan disimpan di memori komputer =12 yaitu {

sebanyak

,

,…,

( )=0 ⟹

+

},

generator, maka

+1=0 ⟹

=

+1

Representasi polinomial yang akan disimpan di memori komputer dapat dilihat pada Tabel 3.2.2 hal 30. dan , yang memenuhi kongruensi

Selanjutnya menentukan nilai

(mod ( )). Agar mudah menentukan

(mod ( )). Ambil

menentukan

+

Jadi

+

dan

≡

terlebih dahulu tentukan

= 3, Sehingga diperoleh

= 2 = 8. Untuk

gunakan Algoritme Euclidean yang Diperluas :

+

+

+

mod ( ) =

+

=

+1

+

+

1

+

Selanjutnya tentukan terlebih dahulu

+

0

0

+1

+

≡

+ +1 (

+

1

+

) (mod ( )), untuk

+

+1 ≥ 0.

37

Tabel 3.2.5

Hasil Perhitungan ( , =

dengan (

0

) ≡ : +

+

+

+

+

+

= (

3

+

+

+

=

4 5

Pada saat ) ≡

Sehingga :

⟹

+

+

+

+

+

+1

=

(

+1=

mod ( ) ), + 1.

(

=

+1 +

+

+ 1)

= 5, diperoleh kongruensi : +1≡

≡

+

≡

(mod ( ));

+ mod(

(2)∗

≥ 0 untuk

(mod ( ))

1 2

(

=

+

:

)

+ 1)

+

+ 1)

= 8,

= 7, dan

= 0.

≡ 5 × 8 + 7 + 0 (mod 127) ≡ 47 (mod 127)

Pada contoh ini banyaknya proses pembagian hingga ditemukan

ada 6

langkah. Langkah ini lebih banyak jika dibandingkan dengan banyaknya langkah pada contoh 4 yang menggunakan Algoritme Baby-Step Giant-Step. Dari contoh ini terlihat bahwa jika representasi polinomial yang disimpan di memori komputer besar, maka proses pembagian sampai diperoleh representasi polinomial

,

∈ {0,1,2,3, … }, akan lebih cepat (banyaknya langkah lebih sedikit), begitu juga

sebaliknya.

3.2.5 Solusi Masalah Logaritma Diskret pada Naif Square Misalkan (2)∗ adalah ,

( )∗ dengan Algoritme (2 )∗ , dengan order

adalah sebuah generator grup siklik ∈

(2)∗ dan



sedemikian ≡ log

sehingga

≡ log

(mod

( .))

, 0≤

Untuk

≤

− ,1

menentukan

(mod ( )) seperti halnya pada Algoritme Baby-Step Giant-Step,

Algoritme Baby-Step Giant-Step 2 dan Algoritme Baby-Step Giant-Step 3, Algoritme Naif Square juga harus melewati fase baby-step dan fase giant-step. Ide

38

dasarnya adalah mengalikan dalam himpunan 1,

dengan

, ,…,

sampai ditemukan

√

,…,

.

menentukan batas minimal banyaknya representasi polinomial yang akan disimpan di memori komputer. kedua

adalah

representasi polinomial {

membentuk

mod ( ) ), ∀ , dimana 0 ≤

( ,

,

,

,…,

≤

<√

= √ , dimaksudkan untuk


Langkah

, 0≤

tabel

,0≤

dengan

≤

− .1

pasangan

− ,1dimaksudkan untuk menentukan


}. Sama seperti pada Algoritme Baby-Step Giant-Step,

Algoritme Baby-Step Giant-Step 2 dan Baby-Step Giant-Step 3 untuk membentuk tabel pasangan ( , (mod

( ))) pada Algoritme Naif Square juga dapat

digunakan Algoritme Exhaustive Search. Fase ini disebut fase baby-step.

Langkah ketiga Algoritme Naif Square adalah menentukan nilai sedemikian sehingga dengan mengalikan anggota {

,

,

≡

( ),) untuk suatu

(mod

dengan ,…,

sampai ditemukan

≥ 1. Caranya adalah

yang merupakan salah satu

}. Dalam proses perkalian ini berlaku aturan

(2). Banyak langkah dalam

penjumlahan dan perkalian polinomial dalam proses perkalian ini adalah . =

= =

⋮

=


=

=

(1)


Jika sudah ditemukan nilai , maka selanjutnya dapat ditentukan nilai logaritma diskret . Berdasarkan Definisi Logaritma Diskret : ≡ log

mod ( )

Sehingga dari (1) dan (2) diperoleh : (

⇔

≡

mod ( )

(2)

=

) = 39

(

Menentukan

)

=(

)

=

mod ( ) adalah

≡

Jadi solusi dari

=(

)

×

=

×

mod ( ) .

≡ log

(mod ) caranya dengan menggunakan Algoritme Euclidean yang

Diperluas. Algoritme 3.2.5 Algoritme Naif Square untuk menentukan masalah logaritma diskret pada (2 )∗

Input :

generator grup multiplikatif (2)∗ , dan

∈

Bentuk

2)

0≤

tabel ≤

≡ log

dengan

(mod ( ))

pasangan

− .1

Mencari nilai , sedemikian sehingga ≥ 1.

3)

Menentukan

4)

Solusi dari

= 2 − 1,

( p) olinomial irredusibel atas ℤ berderajad


(2)∗ berorder ( ,

≡

mod ( ) ), (mod

.

dimana

( ),) untuk suatu

(mod ). (mod ( )) adalah

≡

≡

×

(mod

).

Dalam Menezes et al. 1997 nilai harapan kompleksitas waktu Algoritme Naif Square adalah

(√2 ). Implementasinya dengan bantuan sofware Maple 11

dapat dilihat pada Lampiran 3.6.

Contoh 6 (Menentukan masalah logaritma diskret pada grup siklik dengan Naif Square) generator grup multiplikatif

Diketahui :

=

Tentukan

( )=

≡ log

Penyelesaian :

+

+

+

+

+ 1.

+1∈

(2)∗ ,

=

(2 )∗

(2 )∗ , dan

(mod ( )).

40

(2)∗ adalah

Order dari dan

= 2 − 1 = 127. Diketahui

+

+ 1,

(2)∗ berlaku aturan penjumlahan dan perkalian

generator. Karena pada

dalam mod

( )=

( ,)maka ( ) = 0 ⟹

+

+1=0 ⟹

=

+ 1.

Representasi polinomial yang akan disimpan di memori komputer dapat dilihat pada Tabel 3.2.2 hal 30, dengan ( ,

(mod

Selanjutnya menentukan .

mod ( ) ),

Tabel 3.2.6 Hasil Perhitungan ( , =

+

+

+

+

1 2 3 5

+

6 7 +

11 Jadi

≡

Sehingga :

=

+

+

+

+1 +

+

+1 +1

+1

+1

+

+

+

+

+1

+

+ +

+

+

= 9 × 11

(mod 127)

+1

+1

mod ( ) diperoleh pada saat ×

(2)∗ dengan

+1

+

+

10

≥ 0untuk

(mod ( ))

+

4

9

+ 1.

mod ( ) ).

Representasi polinomial ≡

8

( ))= ( ,

= 9 dan

= 11.

(mod 127)

= 9 × 104 (mod 127) = 47.

Pada algoritme ini, banyaknya langkah perhitungan yang diperlukan untuk memperoleh

relatif besar jika dibandingkan dengan banyaknya langkah pada

Algoritme Baby-Step Giant-Step, Baby-Step Giant-Step 2 dan Baby-Step GiantStep 3. Kelebihannya adalah Naif Square tidak serumit Baby-Step Giant-Step, 41

Baby-Step Giant-Step 2 dan Baby-Step Giant-Step 3, karena hanya memerlukan invers integer tidak memerlukan invers himpunan. Kelemahan Algoritme Baby-Step Giant-Step, Baby-Step Giant-Step 2, Baby-Step Giant-Step 3 dan Naif Square adalah memerlukan banyak memori ketika grup berorder besar. Metode Pollard’s rho menyederhanakannya dengan algoritme probabilistik dengan perkiraan kompleksitas waktu yang sama tetapi memerlukan memori penyimpanan yang lebih sedikit. 3.2.6 Solusi Masalah Logaritma Diskret pada Pollard’s rho


Algoritme Pollard’s rho adalah algoritme untuk memecahkan masalah logaritma diskret dan masalah faktorisasi integer, ditemukan oleh John Pollard pada tahun 1975. Efektif digunakan untuk pemfaktoran bilangan komposit dengan faktor kecil. Algoritme ini didasarkan pada Algoritme Floyd’s Cycle-Finding dan pada pengamatan bahwa (seperti pada Birthday Paradox Problem) dua bilangan dan

adalah kongruen modulo

√ √2 ln 2.

dengan peluang 0,5 setelah langkah ke

Agar lebih mudah untuk memahami Algoritme Pollard’s rho, terlebih

dahulu akan kita kaji tentang Algoritme Floyd’s Cycle-Finding dan Birthday Paradox. Floyd’s Cycle-Finding Algoritme Floyd’s Cycle-Finding ditemukan oleh Robert W. Floyd pada tahun 1967. Algoritme Floyd’s Cycle-Finding digunakan untuk menemukan cycle dalam barisan { , sampai

,

,…,

sehingga pasangan

} dengan membandingkan elemen-elemen =

ditemukan.

Lemma 2.4.8 menjelaskan hubungan antara Algoritme Floyd’s CycleFinding dengan Algoritme Pollard’s rho. Lemma tersebut menunjukkan bahwa dalam barisan bilangan yang dibangkitkan oleh sebuah fungsi yang memetakan sebuah himpunan hingga ke himpunan hingga menjamin adanya satu atau lebih bilangan yang sama. Dalam barisan bilangan yang dibangkitkan tersebut terjadi pengulangan modulo.

42

Floyd’s Cycle Finding digunakan untuk menemukan ≡

sedemikian sehingga Birthday Paradox

(mod

dan

).

Diasumsikan bahwa dalam 1 tahun terdiri dari 365 hari. Berapa banyak orang yang harus ada sehingga peluang 2 orang memiliki hari ulang tahun yang sama adalah

? Pertanyaan tersebut menjadi dasar dari Birthday Paradox.

Kunci untuk memahami permasalahan ini adalah dengan berpikir bahwa peluang tidak ada 2 orang yang memiliki ulang tahun yang sama adalah peluang bahwa orang ke-1 akan memiliki ulang tahun yang berbeda dengan orang ke-2 dan akan berbeda dengan orang ke-3 dan seterusnya. Semakin banyak orang yang dilibatkan, maka peluang tidak adanya 2 orang dengan tanggal ulang tahun yang sama akan semakin kecil. Untuk menghitung peluang ini, kita abaikan variasi tahun kabisat, terdapat orang kembar, dan asumsi bahwa 365 tanggal akan memiliki kemungkinan yang sama. Misalkan banyaknya hari dalam satu tahun adalah akan dihitung peluang ulang tahun yang sama.

( ∗) yaitu peluang

= 365hari. Pertama

orang tidak akan memiliki tanggal

1 2 −1 ( ∗)= 1 1 − 1− … 1− 365 365 365 365.364.363 … (365 − + 1) = 365 365! = (365 − )! 365

Orang ke-2 memiliki tanggal ulang tahun yang berbeda dengan orang ke-1 dengan peluang kejadian

, orang ke-3 harus memiliki tanggal ulang tahun yang

berbeda dengan 2 orang pertama dengan peluang kejadian

, dan seterusnya.

Peluang setidaknya 2 orang dari kelompok tersebut memiliki tanggal ulang tahun yang sama adalah komplemen dari peluang tanggal ulang tahun semua orang akan berbeda, yaitu : ( )=1−

365! (365 − )! 365 43

Misalkan

( , adalah ) peluang bahwa dari banyaknya

orang akan

menghasilkan sedikitnya 2 tanggal hari ulang tahun yang sama. Dapat dilihat bahwa 365 = 0 365 365 364 364 (365, 2) = 1 − . =1− 365 365 365 ( − 1) ( − 1) ( , 2) = 1 − . =1− (365, 1) = 1 −

( , 3) = 1 − .

( , )=1− .

( )=1−

(

(

− 1) ( .

− 1) ( …

( ∗)= 1 −

− 2) ( = 1− −

+ 1)

− 1) ( .

− 2)

365! (365 − )! 365

Dengan menggunakan rumus di atas ternyata nilai

( a)kan melebihi 50% ketika

= 23, perhitungannya dapat dilihat di tabel berikut :

Tabel 3.2.7 Hasil Perhitungan Birthday Paradox ( )

10

0.1169

20

0.4114

23

0.5073

30

0.7063

40

0.8912

50

0.9704

60

0.9941

70

0.9992

80

0.9999

90

0.9999

100

1.0000

150

1.0000

44

Jadi dalam teori probabilitas, birthday paradox menyatakan bahwa dari suatu kelompok dengan anggota 23 orang yang dipilih secara acak, maka peluang setidaknya ada 2 orang yang memiliki tanggal ulang tahun yang sama adalah lebih dari 50%. Semakin besar

semakin meningkat tajam peluang yang diperolehnya.

Pada percobaan orang yang ke-100 saja peluangnya sudah mencapai 1. Padahal secara umum peluang percobaan untuk menghasilkan sedikitnya 2 tanggal hari ulang tahun yang sama dijamin akan bernilai satu ketika banyaknya percobaan tersebut sama atau lebih besar dari input yang ada. Dalam kasus ini besarnya input adalah 365. Karena peluang ini lebih besar dari yang diperkirakan oleh sebagian besar orang maka disebut sebagai paradox. Hal inilah yang menjadi motivasi dari Birthday Paradox. Dari uraian di atas dapat disimpulkan bahwa Birthday Paradox digunakan untuk menjamin bahwa mulai adanya satu atau lebih bilangan yang sama dalam barisan bilangan sedikitnya setelah langkah ke-√ √2 ln 2 dengan peluang lebih

dari setengah.

(2)∗ yang dieksplorasi

Berikut analisis Algoritme Pollard’s rho untuk dari Algoritme Pollard’s rho untuk grup siklik Misalkan berorder

= 2 − 1,

umum.

(2)∗ adalah grup multiplikatif dibawah operasi perkalian

irredusibel berderajad menentukan

masalah

menemukan

=

generator

(2 )∗ ,

(2)∗ , dan

∈

( )polinomial

atas ℤ . Ide dari Algoritme Pollard’s rho untuk

logaritma

diskret

pada barisan { } untuk

(mod ( ))

≡ log

≥ 0.

Langkah pertama adalah mempartisi grup multiplikatif 3 partisi (subset) yang kira-kira berukuran sama, Berikut contoh pendefinisian keanggotaan himpunan

,

(2)∗ =

(2)∗ menjadi ∪

∪

.

= 1,2,3. Misal

adalah himpunan semua polinomial derajadnya kelipatan 3 sisa 1, himpunan semua polinomial derajadnya kelipatan 3 sisa 2,

adalah

adalah

adalah himpunan

semua polinomial derajadnya kelipatan 3 sisa 0. Pendefinisian keanggotaan yang tepat penting untuk menghindari ketidakmerataan pendistribusian anggota (2)∗ ke dalam subset-subsetnya. Karena jika pendistribusiannya tidak merata

akan mengakibat hasil komputasi logaritma diskret yang diperoleh salah, atau bahkan yang lebih parah tidak akan ditemukan

=

pada barisan { }. Selain 45

contoh tersebut masih ada 5 kemungkinan kombinasi pendefinisian yang bisa digunakan. Lebih jelas bisa dilihat di tabel berikut : Tabel 3.2.8 Beberapa Kemungkinan Pendefinisian Keanggotaan Himpunan (2)∗ ,

⊆

Sisa dari derajad polinomial kelipatan tiga untuk

No 1

1

2

0

2

1

0

2

3

2

1

0

4

2

0

1

5

0

1

2

6

0

2

1

Selanjutnya

berdasarkan ,

bangkitkan barisan (dengan

= 1,2,3untuk Algoritme Pollard’s rho

:

(2)∗ →

Algoritme

Floyd’s

Cycle-Finding,

kita

, … secara acak dengan iterasi menggunakan fungsi (2)∗ sampai ditemukan

=

. Karena

(2)∗

berhingga, maka barisan { } akhirnya menjadi periodik membentuk siklus, yakni

ada index terkecil untuk semua

sehingga

≥

=

untuk beberapa

≥ 1, kemudian

+ (seperti pada gambar berikut) (Hankerson 2004).

=

disebut tail length dan disebut cycle length dari barisan. Kita definisikan fungsi sebagai berikut :

:

(2)∗ × ℤ × ℤ →

(2)∗ × ℤ × ℤ

46

dengan

( ,

integer.

( , )= ( (

Selanjutnya, setiap tripel ( ,

, , + 1) jika ∈ ,2 ,2 ) jika ∈ , + 1, ) jika ∈

, ) harus memenuhi bentuk

Bandingkan tripel (

, )= ,

≥ 1sedemikian sehingga = log

Diketahui

,

(0, 0, 0) , (

jika jika

=0 ≥1

=

. Jika sudah ditemukan

=

(

)

Jika gcd(

−

+

(

−

, ) = 1, maka (

=

=(

Algoritme 3.2.6

−

(

=

=

+

)=

sebagai berikut :

solusi

, maka :

(∗)

, maka persamaan (∗) menjadi

berorder , maka dari (∗∗)

Karena

, ) sampai ditemukan suatu nilai

=

=

, artinya

)

,

) dan ( ,

. Dimulai

= 0,(0, 0, 0), maka

dengan mendefinisikan tripel awal, yakni untuk ( ,

=

−

(∗∗)

(mod

(mod )

−

)(

)

)

) mempunyai invers, sehingga diperoleh ) (mod

−

)

Algoritme Pollard’s rho untuk menentukan masalah logaritma diskret pada

Input :

(2 )∗

= 2 − 1,

berderajad

.

∈

= ≡ log


Bagi grup multiplikatif dan

2)

(2)∗ ,


.

Bentuk barisan

,

,

(2 )∗ ,

≥ 1,

(2)∗ berorder

( )polinomial irredusibel atas ℤ

(mod ( ))

(2 )∗ menjadi 3 partisi himpunan yaitu

, …, barisan

dengan iterasi menggunakan fungsi

,

,

, …, dan barisan

yang didefinisikan :

,

, ,

,…

47

3)

4)

( ,

= 0, definisikan

Untuk

( ,

, )=

atau (

=

, , + 1) jika ,2 ,2 ) jika , + 1, ) jika

= 1,

Bandingkan nilai dari ( ,

diperoleh 5)

( , )= ( (

)

= 0,

(0, 0, 0) ( ,

,

=(

)

, ) dan (

,

jika jika

) ,

=0 ≥1

) sedemikian sehingga

.

Kemudian dengan aturan perkalian dan aturan logaritma dengan basis persamaan di atas menjadi

6)

= 0.

∈ ∈ ∈

(

Jika

r log log

=(

) log

−

=

β=( =

(

−

− −

−

(mod

) (mod

)(mod

= log

=

)(mod )

)

=(

)

).

maka

,

sehingga diperoleh persamaan

sehingga

menjadi didapatkan

)dan solusi logaritma diskret adalah : (

)(mod

−

)


Pollard’s rho ini adalah


Contoh 7 (Menentukan masalah logaritma diskret pada grup multiplikatif (2)∗ dengan Pollard’s rho)

Diketahui :

=

Tentukan

(2)∗ ,


( )=

≡ log

Penyelesaian :

+

+

+

(2)∗ , dan

∈

+1

(mod ( )).

(2)∗ dipartisi menjadi 3 himpunan yaitu

,

, dan

;

= himpunan semua polinomial derajadnya kelipatan tiga sisa 1.

= himpunan semua polinomial derajadnya kelipatan tiga sisa 2. = himpunan semua polinomial derajadnya kelipatan tiga sisa 0.

Misalkan ambil Didefinisikan :

= 1, sehingga

= .

48

= ( )≝

. (mod ( )), (mod ( )), . (mod ( )) ,

jika ∈ jika ∈ jika ∈

,

= 2

mod , + 1 mod


,

+ 1 mod , = 2 mod , , =

yang memenuhi persamaan Nilai-nilai untuk pada tabel berikut.

,

, ,

,

, ,

dan

, ,

1

0

1

1

+ +1

1

2

2

2

+1

2

3

+ +1

2

4

3

4

+

3

5

+

4

5

4

6

+

5

6

5

7

6

7

+ +1

6

8

6

9

+

6

10

7

10

7

11


+

1 2 3

+

+

+

4 5 6 7 8

+

+

+1

+

+

9

+

+

10 11 12 13 14 15 16 17 18

+

+

+

+

+

+ +1

+

= .


,

,

untuk

=

= 0 dapat dilihat (2)∗ dengan

, pada

+ +

+1

1

1

2

2

+1

2

4

3

5

4

6

5

7

+ +1

6

8

6

10

+

7

11

8

12

8

14

8

16

+

9

17

9

19

+1

10

20

+ +1

10

22

10

24

+

+

11

25

+

+ +

+

+

+

+

+ +

+

+

+

+

+ +

+1

+1

+ +

≥0

≥ 0.

, dimana

= 1,

, dengan

,

+1

49

Diperoleh : =

=

=(

−

=

(

= 17

+

+

+ 1,

) (mod 31) = (11 − 25) mod 31 = 17,

mod 31 = 11, −

Contoh 8

(mod

Diketahui :


Jadi

= log

) mod 31 = 1(11)(11 − 7) mod 31 = 13.

=

+

+

Penyelesaian :

(2)∗ , dan

(2)∗ , ( ) =

∈

(mod ( )).

≡ log

Tentukan

( )= ) 13.

+

+ 1.

Cara penyelesaiannya sama seperti pada Contoh 7, tetapi dengan mengambil = 5, sehingga

=

=


+1

2 3

=

=( − = 29

=

(

+

+

+

+1

+

,

+

dan

1

0

2

0

2

1

+1

1

=

+

+ 1.

+ 1,

, ,

=

,

+

+ 1.

+1

+

+

+1

2

0

3

1

3

3

mod 31 = 15,

= log

−

) mod 31 = 5(15)(3 − 2) mod 31 = 13.

Contoh 9

Diketahui :

generator grup multiplikatif =

Tentukan

=

+

(2)∗ dengan

, pada

) mod 31= (1 − 3) mod 31= 29, (mod

Jadi

,

( )=

≡ log

( )) = 13 .

+

+

+

∈

+ 1.

(2)∗ ,

(2)∗ , dan

(mod ( )).

50

Penyelesaian : Cara penyelesaiannya sama seperti pada Contoh 7 dan 8, tetapi dengan = 15, sehingga

mengambil

= ,

Tabel 3.2.11 Hasil Perhitungan = +

1 2

+

+

3 +

4 5

+ +

+

+1 +

+

+1

+1

+ +

6 7

=

=

=( − = 20

=

4

dan

1

0

1

1

1

2

1

3

2

3

2

4

3

4

=

,

+

,

, pada

=

+

+

+ +

+

+ 1.

+

(2)∗ dengan +

+ 1.

1

1

1

3

2

4

+ +1

3

5

3

7

+ +1

5

7

10

15

+

+

+

+1

+

,

mod 31 = 14,

(

) mod 31 = 15(14)(10 − 3) mod 31 = 13.

−

Diketahui :


( )=

≡ log

Penyelesaian :

+

+

∈

+ 1.

(2 )∗ , dan

(2)∗ ,

(mod ( )).

Sama seperti pada Contoh 7 dan

, ,

+

) mod 31= (4 − 15) mod 31= 20,

Contoh 10

Tentukan

=

;

(2)∗ dipartisi menjadi 3 himpunan yaitu

,

,

= himpunan semua polinomial derajadnya kelipatan tiga sisa 1.

= himpunan semua polinomial derajadnya kelipatan tiga sisa 2. = himpunan semua polinomial derajadnya kelipatan tiga sisa 0.

Misalkan ambil

= 4, sehingga

=

=

+ 1.

51

Didefinisikan : . , , . ,

= ( )≝

,

= 2

dan

pada tabel berikut.

, ,

,


i 1 +

2 3

+

+1

+1

,

=(

)

, ,

dan

=

=

1

0

1

1

2

1

,

untuk


,

=

+1

+1

= 0 dapat dilihat (2)∗ dengan

, pada

+ 1.

+

≥0

≥ 0.

, dimana

= 1,

, dengan

,

,

jika x ∈ S jika x ∈ S jika x ∈ S

+ 1 mod , mod , ,

yang memenuhi persamaan ,

∈ ∈ ∈

mod n, + 1 mod n,

= 2

Nilai-nilai untuk

jika jika jika

1

1

4

2

5

3

Diperoleh : =

=

=

−

= 13

=

(

, (mod 15) = 1 − 3 (mod 15) = 13,

(mod 15) = 7, −

)mod 15 = 4(7)(5 − 2)mod 15 = 9.

Contoh 11

(mod

Diketahui :


Jadi

= log

=

Tentukan

( )=

≡ log

Penyelesaian :

( ))= 9.

+

+

∈

(2 )∗ , dan

(2)∗ ,

+ 1.

(mod ( )).

52

= 7, sehingga

Misalkan ambil

,


i

+

+ +1

1

0

2

0

3

0

+1

4

0

5

0

+ +1

10

0

3 +

4 5 6

=

=

Karena

−

=

=

dan

1

+1

2

+

+

+

=

, ,

=

,

=

+

+ ,

+

(2)∗ dengan

, pada + 1.

+1

+1

2

0

4

0

+

+1

10

0

10

0

+

+1 +1

10

0

+1

10

0

+ +

+ 1,

+ 1.

(mod 15) = 0 − 0 (mod 15) = 0,

= 0, maka

tidak mempunyai invers modulo. Sehingga dalam kasus ini

tidak bisa ditentukan

yang benar.

Contoh 12 Diketahui : Tentukan

(2)∗ ,


≡ log

+

(2 )∗ , dan ( ) =

∈

(mod ( )).

Penyelesaian :

+

+ 1.

Cara penyelesaiannya sama seperti pada Contoh 11 dan 12. Misalkan ambil = 1, sehingga

= .

dan

,

1

0

1

1


i

+

1 2

=

=

=

−

+ +1

+

+ 1,

, ,

= .

,

,

+

+1

+

+1

, pada

(2)∗ dengan

1

1

4

4

(mod 15) = 1 − 4 (mod 15) = 12. 53

Karena gcd (12,15) ≠ 1, maka

tidak mempunyai invers modulo. Sehingga

dalam kasus ini tidak bisa ditentukan

yang benar.

Dari Contoh 10, 11 dan 12, terlihat bahwa penentuan

( adalah pangkat

dari generator ) akan sangat berpengaruh pada keberhasilan untuk menentukan logaritma diskret pengambilan

yang benar. Tetapi jika kita lihat Contoh 7, 8, dan 9, yang berbeda tidak mempengaruhi keberhasilan dalam

menentukan logaritma diskret . Ini sebenarnya berhubungan dengan order grup (2 )∗ ;

siklik

(2 )∗ berorder prima, maka walaupun

= 2 − 1. Jika

berbeda tetap akan diperoleh hasil yang tepat, dan sebaliknya jika

dengan

(2)∗ berorder komposit maka memilih

harus berhati-hati agar ditemukan

yang benar. Berikut beberapa kemungkinan yang dapat terjadi akibat dari ketidaktepatan pemilihan generator pada grup = 0. Jika

1)

= 0, maka

tidak mempunyai invers modulo. Sehingga tidak

bisa ditentukan logaritma diskret 2) gcd ( ,

(2)∗ berorder komposit.

yang benar.

) ≠ ;1 adalah order grup

(2 )∗. Jika gcd ( ,

) ≠ ,1maka

tidak mempunyai invers modulo. Sehingga tidak bisa ditentukan logaritma diskret

yang benar atau logaritma diskret

yang diperoleh tidak tepat.

Selain pemilihan pangkat generator ( ), hal penting yang juga harus diperhatikan dalam Algoritme Pollard’s rho ini adalah cara mempartisi grup siklik

(2 )∗ menjadi 3 himpunan bagian. Pembagian grup harus seacak

mungkin, agar pendistribusian anggota tidak menumpuk pada satu himpunan bagian, karena akan berpengaruh untuk keberhasilan penentuan logaritma diskret yang tepat. Perhatikan bahwa himpunan bagian ini tidak harus subgrup dari grup multiplikatif

(2 )∗ .

3.2.7 Solusi Masalah Logaritma Diskret pada Pohlig-Hellman


Algoritme Pohlig-Hellman adalah sebuah algoritme yang digunakan untuk mengkomputasi logaritma diskret dalam sebuah kelompok multiplikatif yang pangkatnya bukan merupakan bilangan prima yang aman. Algoritme ini didasari oleh Teorema Sisa Cina.

54

Berikut analisis Algoritme Pohlig-Hellman untuk dieksplorasi dari Algoritme Pohlig-Hellman untuk grup siklik

umum.

(2)∗ adalah grup siklik dibawah operasi perkalian berorder

Misalkan = 2 − 1.

(2)∗ yang

generator

irredusibel berderajad

atas ℤ .

(2 )∗,

(2)∗ , dan

∈

Berdasarkan Teorema Dasar Aritmetika,

( ) polinomial

dapat difaktorkan atas kuasa

prima :

dimana

=

adalah bilangan prima berbeda dan

(1)

≥ 1.

Ide dari Algoritme Pohlig Hellman untuk menentukan masalah logaritma ≡ log

diskret

dahulu menentukan

(mod ( )) adalah menemukan mod

, untuk setiap , 1 ≤

mod , dengan terlebih

≤ , menggunakan Teorema

Sisa Cina. Artinya komputasi dilakukan pada subgrup berorder prima berpangkat ).

integer positif (

Perhatikan masalah logaritma diskret pada grup mod ( ) .

≡

(2 ) berikut :

adalah solusi dari masalah tersebut, sehingga menurut Definisi Masalah Logaritma Diskret y dinyatakan dalam modulo , dinotasikan y mod . Karena

mod

=

mod

(2)

adalah bilangan prima berbeda, maka berdasarkan Teorema Sisa Cina

diperoleh sistem kongruensi berikut : untuk setiap , 1 ≤

≤ .

=

mod

Selanjutnya untuk menentukan nilai

nilai

=

. Misal

dimana 0 ≤

≤

dan − 1.

(3) , maka terlebih dahulu ditentukan

= , maka (3) menjadi : =

dapat diekspresikan dalam q-

mod

(4)

yang direpresentasikan sebagai :

55

dimana 0 ≤

=

≤

Perhatikan

=

+

− 1, untuk 0 ≤ persamaan

≤

(4),

(5)

− .1

juga

dapat

diekspresikan

sebagai

, untuk beberapa integer . Sehingga diperoleh : =

Selanjutnya menghitung

. Nilai

+

diperoleh dari :

mod ( )

=

(6)

dengan menggunakan Algoritme Exhaustive Search atau Baby-Step Giant-Step. Bukti persamaan (6) : ≡

= (

⟺

=

=

=

=

=

mod ( )

mod ( )

)

⋯

.

.(

.1

)

⋯

⋯

mod ( )

= 1, maka diperoleh

=

. Jika

langkah selanjutnya adalah menentukan dengan menggunakan persamaan (5). Cara untuk menentukan Tetapkan

untuk 1 ≤

= ≤

dan definisikan =

(mod ( ))

⋯

Adalah mudah untuk menghitung Jika

(mod ( ))

(mod ( ))

(mod ( ))

dengan menggunakan persamaan (6). > 1, setelah nilai

, ,…,

, ,…,

diketahui, maka

dan kemudian hitung

sama seperti menentukan

⋯

− .1 Kemudian untuk menghitung

perumuman persamaan (6) berikut :

∎

, ,…,

.

gunakan

56

Bukti persamaan (7) : =

⋯

=

⋯ ⋯

mod ( )

⋯

=

(

=

(1)

=

Perhatikan bahwa

,

Oleh karena itu,

mod ( )

⋯

mod ( )

=

mod ( )

⋯

)

, ,

mod ( ) dapat dihitung dari

,…,

dengan menggunakan (6) dan (8). Setelah

semua

(mod

), 1 ≤

Gauss diperoleh Algoritme 3.2.7

≡ log

(mod ( ))

(mod ( )

⋯

.

⋯

mod ( )

⋯

.

=

≡

mod ( )

⋯

=

(7)

mod ( )

⋯

= =

mod ( )

=

nilai

=

,

, dengan

diketahui :

∎

(8)

dapat dihitung secara bergantian

diketahui,

maka

diperoleh

kongruensi

≤ . Selanjutnya dengan menggunakan Algoritme (mod ( )).

Algoritme Pohlig Hellman untuk menentukan masalah logaritma diskret pada

Input :

(2 )∗

generator grup siklik dan

(2)∗ berorder

( p) olinomial irredusibel berderajad

= 2 − 1,

atas ℤ .

∈

(2)∗ ), 57

≡ log

Output : logaritma diskret 1.

Cari faktorisasi prima dari

2.

1≤

Untuk

≤ .

=

+

setiap

≤ ,

+ ⋯+

terlebih dahulu tentukan koefisien berikut: 2.1

Masukkan nilai

2.2

Menentukan

2.3

Definisikan

2.4

Untuk

4.

,

0≤

Untuk setiap , 1 ≤

≤ , hitung

dengan

≤

− ,1

≤

Ambil

) dimana 1 ≤

sebagai hasil.

maka

− .1

hitung

nilai

sedemikian

= . Selanjutnya definisikan =

;

+

Gunakan Algoritme Gauss untuk menghitung integer ≡ (mod

≥ 1,

dengan langkah-langkah

(mod ( )), untuk 0 ≤

(mod ( ))

≡

nilai

( )) . Kemudian tentukan nilai

.

3.

, ,…,

= . Sehingga diperoleh

sehingga

, dimana

. Untuk menentukan nilai

= .

= .

(mod

…

tentukan

dan

setiap

=

2.5

=

=

=

, yaitu

1≤

,

+

(mod ( ))

≤ dan 0 ≤

≤

+

+ ⋯+ sehingga

− 1.

Dalam Menezes et al. (1997) nilai harapan kompleksitas waktu Algoritme (∑

Pohlig Hellman adalah

(log 2 +

). Implementasinya dengan

bantuan sofware Maple 11 dapat dilihat pada Lampiran 3.8.

Contoh 13 (Menentukan masalah logaritma diskret pada grup multiplikatif (2 )∗ dengan Pohlig-Hellman)

Diketahui :


Tentukan

( )=

= log

+

+

+

+

(mod ( )).

+

+

+1∈

+ 1.

(2 )∗ ,

(2 )∗ , dan

58

Penyelesaian : (2 )∗ berorder , dengan

Grup

Selanjutnya akan ditentukan ≡ (mod 7) dan =

dahulu

Definisikan 

+

=

= 3, dan

≡

0≤

≤

=0



≡ (mod 9),

dimana

≡ (mod 5),

≡ (mod 13). Sebelumnya harus ditentukan terlebih

=

= 1,

Untuk

+

= 2 − 1 = 4095 = 3 . 5.7.13

+

+⋯+ +

+

;1≤

≤ 4.

+ 1.

=2

(mod ( )).

− 1 = 1.

≡ 1 (mod ( )).

≡

=

≡ 1 (mod ( )).

⇒

Dengan menggunakan Algoritme Exhaustive Search diperoleh : =

= 0 , dan

=1



≡

≡

=

+

⇒

≡

≡

+

( )) ≡ .

(mod

+

+

+

(mod

+

+

=

=1

+

( ).)

(mod

( ).)


Jadi :

dan 

Untuk

=2

+

≡ 3(mod 9)

= 5, dan

≡

0≤ 

≤

=0 ≡

= 0 + 1.3 = 3

=1

(mod

( )) .

− 1 = 0, berarti ≡

+

+

(i)

= 0. +

+

+

+

(mod

( )) . 59

=

⇒

≡

+

(mod

+

+

+

( )) .

+

+


Jadi :

=1

dan 

= 7, dan

≡

0≤

≡

≤

=

=1

≡ 1(mod 5)

=3

Untuk

=

=1

(mod

(ii)

( )) .

− 1 = 0, berarti

≡

+

+

(mod

⇒

+

( ).)

≡

+

+

= 0. +

+

(mod

+ +

+ +

( ))

+ +

+ +

+ +

+


Jadi :

=6

dan 

= 13, dan

≡

0≤

≡

≤

=

=6

≡ 6(mod 7)

=4

Untuk

=

=1

(mod

≡

(iii)

( )) .

− 1 = 0, berarti +

⇒

+

≡

+

+

= 0. +

+

(mod

+

+

( )) .

(mod

( )) .

Dengan menggunakan Algoritme Exhaustive Search diperoleh : Jadi :

=

dan

=7

≡ 7(mod 13)

=

=7 (iv)

60

Dari (i), (ii), (iii) dan (iv) diperoleh sistem kongruensi: ≡ 3(mod 9) ≡ 1(mod 5) ≡ 6(mod 7)

≡ 7(mod 13)

Selanjutnya menyelesaikan sistem kongruensi di atas dengan menggunakan Teorema Sisa Cina dan Algoritme Gauss. = 3,



= 9,



=



= 1,

= 6,

= 5,

= 455,

=

= 7,

= 7.

= 13

= 819,

 455

≡ 1(mod 9), maka

=2

585

≡ 1(mod 7), maka

=2

819

≡ 1(mod 5), maka

≡ 1(mod 13), maka

315

≡



+

=

= 585,

=

= 315.

=4 =9

+

+

(mod 4095)

≡ 3.2.455 + 1.4.819 + 6.2.585 + 7.9.315 (mod 4095) ≡ 111 (mod 4095) = log

Jadi

( ))= 111.

(mod

Contoh 14 (Menentukan masalah logaritma diskret pada grup siklik (2)∗ dengan Pohlig Hellman)

=

Diketahui :


( )=

= log

Tentukan

Penyelesaian : Grup

+

+

+

= 2 − 1 = 262143 = 3 . 7.19.73

berorder , dengan

≡ (mod 19) dan =

Definisikan 

Untuk

+

=

= 1,

+ 1.

(2)∗, dan

(mod ( )).

Selanjutnya akan ditentukan dahulu

∈

(2 )∗ ,

+

=

dimana

≡ (mod 27),

≡ (mod 7),

≡ (mod 73). Sebelumnya harus ditentukan terlebih +

+⋯+

+ .

;1≤

≤ 4.

61

= 3, dan

≡

0≤

≤

=0



=3

(mod ( )).

− 1 = 2.

≡ 1 (mod ( )).

≡

=

⇒

Diperoleh =1



≡

≡

=

⇒

≡ 1 (mod ( )).

=

= 0 , dan

+

+

≡

=2 ≡

≡ 1 (mod

=

⇒

Diperoleh Jadi : dan 

Untuk

=

=2

+

0≤ 

≤

=0 ≡

=

=1

(mod

= 1, dan ( ).)

= 0.

( )) .

− 1 = 0, berarti ≡

⇒

+

≡ 1 (mod

+

+

≡

+

+

+

+

( )) ≡ .

(mod

+

+ 1 (mod ( )). +

≡ 3(mod 27)

= 7, dan

≡

=

+

+

=

Jadi diperoleh 

+

+

≡

+

≡

+

≡

+ +

+ +

+ +

+ 1 (mod ( )).

(mod

+

.

+ +

( ))

( ))

= 0 + 1.3 + 0. 3 = 3

(i)

= 0.

+

+

+

+

+

+

(mod

+

+

( )) .

(mod

( )) . 62

Diperoleh =

Jadi : dan 

=2

= 19, dan

≡

0≤

≡

≤

=

(mod

≡

=

dan

=4

Untuk

+

0≤

≡

≤

=

=

≡

dan

+

≡

+

= 11.

+

+

( )) .

+

+

+

+

+

+

+ 1 (mod

+ +

( ))

+ +

+

= 11

≡ 11(mod 19) =1

(iii)

( )) .

− 1 = 0, berarti +

+

+

⇒ =

= 0.

+ 1 (mod

(mod

Diperoleh Jadi :

( )) . +

+

= 73, dan

≡

(ii)

− 1 = 0, berarti

Diperoleh



=1

⇒

Jadi :

= 2.

≡ 2(mod 7)

=3

Untuk

=

=

≡

(mod

= 30.

+

+

= 0.

+

( )) . +

+

+

+

+ +

+ +

(mod

= 30

≡ 30(mod 73)

+ +

( )) .

+ +

+ +

+ +

(iv)

Dari (i), (ii), (iii) dan (iv) diperoleh sistem kongruensi: ≡ 3(mod 27) ≡ 2(mod 7)

63

≡ 11(mod 19) ≡ 30(mod 73)

Selanjutnya menyelesaikan sistem kongruensi di atas dengan menggunakan Teorema Sisa Cina dan Algoritme Gauss. = 3,



= 27,



=



= 7,

= 11,

= 9709,

 9709

=

= 19,

= 30.

= 73

= 37449,

≡ 1(mod 27), maka

37449

= 22

≡ 1(mod 7), maka

13797



= 2,

+

=

= 3591.

= 13

≡ 1(mod 73), maka

≡

= 13797,

=6

≡ 1(mod 19), maka

9709

=

= 47

+

+

(mod 262143)

≡ 3.22.9709 + 2.6.37449 + 11.13.13797 + 30.47.3591 (mod 262143) ≡ 30 (mod 262143) = log

Jadi

( ))= 30.

(mod

Contoh 15 (Menentukan masalah logaritma diskret pada grup multiplikatif (2)∗ dengan Pohlig Hellman)

Diketahui :


+

Penyelesaian : Grup

(2)∗ berorder , dengan

Selanjutnya akan ditentukan ditentukan terlebih dahulu Definisikan 

Untuk

=

= 1,

= 7, dan

≡

= 0:

≡

(2 )∗ , dan ( ) =

+1∈

(mod ( )).

= log

Tentukan

=

+

=

(2)∗ ,

+

+ 1.

=2 −1=7

dimana +

+ 1.

+

≡ (mod 7). Sebelumnya harus + ⋯+

.

=1

(mod ( )). ≡

(mod ( )).

64

=

⇒

≡

=

= 5.

(mod ( )).

Dengan menggunakan Algoritme Exhaustive Search atau Baby-Step Giant-Step diperoleh : Sehingga ≡ log

=

= 5, dan

mod ( )

= 5.

≡ 5(mod 7).

Pada Contoh 15, grup multiplikatif

untuk menentukan logaritma diskret

(2)∗ berorder prima, sehingga

hanya memerlukan nilai dari

diperoleh dengan mencoba semua kemungkinan nilai

. Nilai

yang ada; 0 ≤

≤ 6,

sampai ditemukan

yang benar. Pelacakan lengkap seperti ini masih efektif

dilakukan karena

(2)∗ berorder kecil. Jika

untuk menentukan logaritma diskret

(2 )∗ berorder prima besar,

dengan Algoritme Pohlig Hellman tidak

begitu efektif, karena ordernya tidak bisa difaktorkan menjadi faktor prima yang (2)∗ tidak bisa difaktorkan menjadi faktor prima,

smooth. Dalam hal order

maka menentukan logaritma diskret

bisa langsung menggunakan Algoritme

Exhaustive Search, Baby-Step Giant-Step atau Pollard’s rho. ( )∗ dengan Algoritme

3.2.8 Solusi Masalah Logaritma Diskret pada Index Calculus Misalkan menentukan

adalah generator grup siklik

= log

berorder , dan

∈ . Untuk

dengan Algoritme Index Calculus umum diantaranya

adalah menentukan faktorisasi dari suatu generator

berpangkat

dengan

≥ 1.

Masalah pemfaktoran ini menjadi bagian penting dalam Algoritme Index

Calculus. Karena itu agar lebih mudah memahami Algoritme Index Calculus pada (2)∗ , terlebih dahulu akan kita pelajari tentang faktorisasi polinomial

( ) ∈ ℤ[ ].

3.2.8.1 Faktorisasi Polinomial Diberikan polinomial bagaimana memfaktorkan

( ) ∈ ℤ[ ]. Masalah faktorisasi polinomial adalah

( ,)sehingga ( ) =

( )

( ) … ( ) , untuk 65

setiap

( )adalah polinomial irredusibel atas ℤ [ ]dan setiap

≥ 1, 1 ≤

≤

(Menezes et al. 1997). Pada tulisan ini faktorisasi polinomial dibatasi pada polinomial-polinomial atas ℤ [ ] dan solusi faktorisasi polinomial akan

dikerjakan dalam beberapa tahap. Tahap pertama adalah faktorisasi bebas kuadrat, kedua faktorisasi bebas kuadrat berderajad

, ketiga faktorisasi berderajad

terakhir faktorisasi lengkap ( ) =

( ) … ( ).

1.

Faktorisasi Bebas Kuadrat

Definisi 3.2.8.1 Misalkan

( )

( ) ∈ ℤ[ ]. Maka

( )bebas kuadrat jika tidak ada

pengulangan faktor, yakni tidak terdapat polinomial ( ) membagi

sedemikian sehingga adalah ( ) = ∏

dan gcd ( ( ), ( )) = 1, untuk

( )berderajad ≥ 1

( . )Faktorisasi bebas kuadrat dari

( ), dimana setiap

dan

( )

( )adalah polinomial bebas kuadrat

≠ . (Menezes et al. 1997)

( ) ∈ ℤ[ ] adalah merupakan

Perhatikan bahwa setiap polinomial

polinomial monik. Definisi yang berhubungan dengan polinomial monik dapat

dilihat pada Definisi 2.3.19. Bagian faktorisasi bebas kuadrat ini menunjukkan bagaimana masalah memfaktorkan polinomial

( )direduksi ke masalah

pemfaktoran satu atau lebih polinomial monik bebas kuadrat. Ide dasarnya sama dengan ide Algoritme Barlekamp’s Q-Matrix. Misalkan

( )=∏

( ) adalah polinomial monik atas ℤ [ ]

berderajad , mempunyai faktor irredusibel berbeda Berlekamp’s Q-Matrix untuk memfaktorkan Himpunan polinomial :

( ), 1 ≤

≤ . Algoritme

( )didasarkan pada fakta berikut.

ℬ = { ( ) ∈ ℤ[ ]/〈 ( )〉| ( ) ≡ ( ) mod ( ) }

adalah ruang vektor berdimensi

atas ℤ . Karena ℬ adalah ruang vektor maka ℬ

memiliki basis, sebut saja basisnya adalah ℱ = { ( ),

setiap faktor berbeda sedemikian sehingga ( ) − . Faktor

gcd ( ( ),

( )−

Matrix menentukan

( ) dan

( ) dari

( ) membagi

( ) dan

( )ada

( ) − , tetapi

( ), … ,

( )}. Untuk

( ) ∈ ℱ dan

∈ℤ

( ) tidak membagi

( ) dapat dipisah dengan menghitung

)(Menezes et al. 1997). Pada Algoritme Berlekamp’s Q( )−

yaitu dengan menggunakan atau melibatkan

66

matriks identitas, sedangkan pada tulisan ini digunakan pelacakan probabilistik (metode trial and error). Selanjutnya, Algoritme Berlekamp’s Q-Matrix dapat dilihat di Landasan Teori Algoritme 2.6.1. Misalkan

( ) ∈ ℤ[ ], dengan

atas ℤ , dan misalkan

berderajad

( m ) embagi ( ( )) −

Misalkan ( ) =

+

( )= (

+

( ( )) = ( dengan

( )∈ ℤ [ ],

≥ 1, sedemikian sehingga

( ), dan 2 adalah karakteristik dari ℤ [ ].

+

+ ⋯+

+

+

( )adalah polinomial irredusibel monik , maka

) mod

+⋯+

+

+⋯+

Polinomial ( ( )) −

( ) mempunyai

)

( d) an ( )

mod

= 2 akar (Teorema 2.4.7),

( )= 0, 1. Berdasarkan fakta yang digunakan Algoritme Berlekamp’

Q-Matrix hal 66 dan berdasarkan Teorema 2.4.7 ( ( )) − ( ( )) −

( )=

( )( ( )− 1)

( m ) embagi ( ( )) −

pada ℤ [ ]. Karena

( ) = gcd( ( ), ( ( ) ) − ( ) ) = gcd

( )menjadi :

( ), diperoleh

( ), ( ) ( ( ) − 1)

= gcd( ( ), ( ) ) gcd

Ditulis,

( ), ( ( ) − 1)

( ) = gcd ( ( ), ( ) ). ( ) = gcd

( ), ( ( ) − 1) .

Algoritme faktorisasi bebas kuadrat dirancang untuk mendapatkan salah

satu

( ), dimana

= 1, 2. Berikut Algoritme Faktorisasi Bebas Kuadrat.

Algoritme Faktorisasi Bebas Kuadrat

Algoritme Faktorisasi Bebas Kuadrat adalah algoritme untuk menentukan faktorisasi bebas kuadrat dari polinomial monik bebas kuadrat dengan mengambil atau mengekstrak satu faktor saja.

( )atas ℤ

Algoritme Faktorisasi Bebas Kuadrat dilakukan dalam 3 tahap. Tahap pertama adalah menguji apakah polinomial input

( )merupakan polinomial

monik bebas kuadrat atau bukan (Algoritme 3.2.8), dengan cara menginput Jika ( )=

( ) adalah ( ) mod

polinomial

bebas

kuadrat

maka

akan

= 1.

ditemukan

( .) 67

Algoritme 3.2.8 Algoritme Faktorisasi Bebas Kuadrat 1 Input

: polinomial monik ( ) = gcd (

Output :

1. 2. 3.

( ),

( )←

( ) ←(

( ),

, dimana ( ))

) mod

( )

( )+

2) ℎ ( ) ←

( ).

( ) ← ℎ( )mod

( )

( )= ( )

( ) ← gcd ( ( ), ( ))

= 1.

( ) adalah salah satu anggota

mod ( )

( )←

3)

dan integer ,

( ), … , ( ) sedemikian sehingga ( ) =

Untuk dari 1 sampai diperoleh ( ) = 1)

4.


( ) ( )… ( )

( ), lakukan :

( )

Algoritme 3.2.8 diimplementasikan dengan bantuan software Maple 11, dapat dilihat pada Lampiran 2.1. Contoh 16 Diketahui : ( ) =

Tentukan apakah Penyelesaian :

+

+

+ 1 ∈ ℤ [ ], dengan

= 1.

( a)dalah polinomial monik bebas kuadrat.

Misalkan : ( )=

( )=(

mod ( ) =

) mod ( ) =

Selanjutnya dilakukan penjumlahan dan perkalian diperoleh ( ) =

Berikut perhitungan ℎ ( )mod

( .)

( )= . ( )=

( )+

( )dan

( ), ℎ ( ) =

( )sampai

( ) , dan

( )=

68

Tabel

3.2.15

Hasil

Perhitungan

( )=

+

( )

1

+

2

+

3 5

+ 1.

+

+1

+

+1 ( )=

+

terus berlangsung sehingga tidak akan ditemukan ( )=

Akibatnya

+

+

( ),

dan ( )

+

( ) nilainya sama dengan

Pada saat

ℎ ( ),

ℎ( )

+1

+1

4

+

( ),

+

+1

+

+1

+

+1

dengan

+ 1. Pengulangan akan ( ) mod

( )=

( .)

+ 1 bukan merupakan polinomial monik bebas

kuadrat, sehingga untuk memfaktorkan membutuhkan algoritme lain (bisa digunakan Algoritme 3.2.14). Contoh 17 Diketahui dengan

( )=

:

+

= 1. Tentukan apakah

Penyelesaian :

+

+

+

Selanjutnya dilakukan penjumlahan dan perkalian Berikut 

perhitungan

( )=

ℎ ( )= 



( )= .

( ) = ℎ ( )mod .

( )=

.

ℎ ( )=

.

( )=

( )=

( )=

+

+ 1 ∈ ℤ [ ],

( ) dan

( ) sampai

ℎ( )=

( ),

( a)dalah polinomial monik bebas kuadrat.

( ) = ( ) mod ( ) =

diperoleh ( ) =

+

mod ( ) =

( )=

Misalkan :

+

( .)

( )=

( )+

( ),

dan

+ . +

+

+

+

. + . 69

ℎ ( )= 





.

( )=

+

+

ℎ ( )=

+

+

( )=

+

+

( )=

+

+

ℎ ( )=

+

+

( )=

+

+

( )=

+

+

ℎ ( )=

+

+

( ) = 0.

( )= .

Pada saat

maka gcd ( ( )=

+

+

+

+

+

+

+

+

+

+

+

+

+

+

+

+

+

+

+

+

+

+

+

( ) nilainya sama dengan

+

+

+

+

+ 1.

+

+

+

( ,)maka

+

+ 1.

+

+

+

+ 1.

+ .

+

+

+

+

+ 1.

.

+ 1.

.

( ) = . Selanjutnya karena

( ), ( )) ditetapkan sama dengan

( ) mod

+

( ) = 0,

( .)Dan karena ditemukan

( )adalah merupakan polinomial monik bebas

kuadrat. Sehingga selanjutnya untuk mengekstrak 1 faktor bebas kuadrat dari polinomial

( d) apat menggunakan Algoritme 3.2.9 berikut.

Algoritme 3.2.9 berikut adalah algoritme untuk menentukan faktorisasi ( ) ∈ ℤ[ ]dengan hanya

bebas kuadrat dari polinomial monik bebas kuadrat mengambil satu faktor saja. Algoritme 3.2.9 Algoritme Faktorisasi Bebas Kuadrat 2 Input : polinomial monik bebas kuadrat Output :

( ) = gcd ( ( ),

{ ( ), 1. 2. 3.

( )=

( )← ( )

( ) ∈ ℤ[ ]berderajad .

( )) , dimana

( ), … , ( ), … , ( )} ( ) ( )… ( )…

( )adalah salah satu anggota sedemikian

( )

( ) ←gunakan Algoritme 3.2.8 dengan input

= 1dan ( ) =

Untuk dari 3 dengan langkah 2 selama t( ) ≠ 1 atau ( ) ≠ ( ) ← gunakan Algoritme 3.2.8 dengan input

Hasilnya adalah

( .)

sehingga

( )

( ,)lakukan:

= dan ( ) =

( .)

70

Algoritme 3.2.9 diimplementasikan dengan bantuan software Maple 11, dapat dilihat pada Lampiran 2.2. Contoh 18 Diketahui ( ) =

+

+

+

+

( .)

Tentukan faktorisasi bebas kuadrat dari Penyelesaian :  

( )= ( )=

+

Selanjutnya tentukan

+

= 3, diperoleh ( ) =

Ambil hasil ( ) = Algoritme 3.2.10

+

+

+ +

+ 1 ∈ ℤ[ ] +

+ 1.

+

( .)Ulangi langkah ini dengan input +

= 5, diperoleh ( ) = 1.

dan

+

+

( )menggunakan Algoritme 3.2.8 dengan input

= 1, diperoleh ( ) =

dan

+

+

+

+

+

( )

( )dan

+ 1. Ulangi dengan input

( )

+ 1.

Algoritme Faktorisasi Bebas Kuadrat 3 Deskripsi

: Menentukan faktorisasi bebas kuadrat dari polinomial monik bebas kuadrat

( d) engan hanya mengambil satu faktor saja.

Input

: polinomial monik

Output

: ( ) = gcd ( ( ), { ( ),

1. 2.

( )=

( ) ∈ ℤ[ ]berderajad ( )) , dimana

( ), … , ( ), … , ( )} ( ) ( )… ( )…

dan integer positif .

( )adalah salah satu anggota sedemikian

sehingga

( )

( ) ←gunakan Algoritme 3.2.9 dengan input ( ).

Untuk dari 1 selama deg ( ( )) ≠

lakukan :


Hasinya adalah

( .)

( .)

Algoritme 3.2.10 diimplementasikan dengan bantuan software Maple 11, dapat dilihat pada Lampiran 2.3. Contoh 19 Diketahui = 7.

( )=

+

+

+

+

+

+

+

+ 1 ∈ ℤ [ ,] dan

71

( .)

Tentukan faktorisasi bebas kuadrat dari Penyelesaian : 

( )=

+

+

( )) .

dengan input 

+

+ 1 (perhitungan menggunakan Algoritme 3.2.9

Selanjutnya karena deg ( ) ( a)dalah ( ) =

Jadi ( ) =

+

Contoh 20 Diketahui = 4.

+

( )=

+

+

+

+

=

+ 1. +

+

+

+

dengan input 

Selanjutnya

+

( )) .

karena

+

+

+

+ 1 ∈ ℤ [ ,] dan

+ 1 (perhitungan menggunakan Algoritme 3.2.9

deg ( )

sebelumnya dengan input karena

+

( .)

Penyelesaian : ( )=

+ 1.

+

Tentukan faktorisasi bebas kuadrat dari 

= 7maka satu faktor bebas kuadrat dari

≠

( )=

= 4 maka

+

+

ulangi

+

lagi

+ 1 dan

prosedur = 4. Dan

( )ternyata adalah polinomial irredusibel berderajad 7, maka

walaupun proses perhitungan menggunakan Algoritme 3.2.9 terus diulang ( )yang berderajad sama

tidak akan pernah ditemukan suatu faktor dari

dengan 4. Jadi perhitungan untuk mengambil atau mengekstrak satu faktor bebas kuadrat berderajad 2.

= 4dari polinomial

( g) agal.

Faktorisasi Bebas Kuadrat Berderajad Algoritme Faktorisasi Bebas Kuadrat Berderajad

mengambil semua faktor bebas kuadrat berderajad

adalah algoritme untuk dengan menggunakan

Algoritme Faktorisasi Bebas Kuadrat. Algoritme 3.2.11 Algoritme Faktorisasi Bebas Kuadrat Berderajad Input : polinomial monik bebas kuadrat positif .


dan integer

72

Output : ( ) =

( ) ( )…

( )

← deg ( ( )) dibagi dengan .

1.

( )←

(.)

( )

< lakukan :

2. Untuk dari 1 selama

( ) ←gunakan Algoritme 3.2.10 dengan input ( ) ←hasil bagi

3. Hasil = ( ) =

( )dan ( ).

( )=

( ) ( )…

( )dan .

( )

( )

Algoritme 3.2.11 diimplementasikan dengan bantuan software Maple 11,

dapat dilihat pada Lampiran 2.4. Contoh 21 Diketahui : ( )=

+

+

Tentukan : faktorisasi bebas kuadrat berderajad

dari

= 7.

+

+

+

+

+

+

+

+

+

+1

+

Penyelesaian : =

Set 1.

( )

( )=

Tentukan input ( )=

2.

Tentukan ( )=

Tentukan input ( )=

( .)

( ). Untuk menentukan

+

( )

( )

=

= 7. Diperoleh :

+ 1.

+

+

+


( )dan

( )=

+

+

( .)

= 4.

( )dan

( )=

input

3.

=

+

+

( )

( )

=

+

= 7. Diperoleh : +

+

+ 1. +

+


( )dan +

+

= 7. Diperoleh : +

( )gunakan Algoritme 3.2.10 dengan +

+

+

+

+ 1.

+

+

+

+

+ 1.

( )gunakan Algoritme 3.2.10 dengan

( )gunakan Algoritme 3.2.10 dengan

+ 1.

73

Jadi :

( )=

( )=

=(

(

( )

( )

=

+

( ) ( ) ( ) +

+

+ 1)( +

+

+ ( ).

+

+

+ 1)

+

+ 1.

+

+ 1)(

Algoritme Faktorisasi Faktor Berderajad ( ) ( )…

faktor berderajad , misal

+

+

+

+ 1)

ini akan mengekstrak semua

( ) dan suatu faktor

( )yang

( ) merupakan suatu polinomial monik bebas

tidak berderajad

, tetapi

kuadrat. Jika

( )bukan merupakan polinomial monik bebas kuadrat maka

pemfaktoran gagal, seperti pada kasus atau Contoh 20. 3.

Faktorisasi Berderajad Algoritme Faktorisasi Berderajad

adalah algoritme untuk menentukan

beserta pengulangan atau pangkatnya dengan

satu faktor berderajad

memanfaatkan hasil Algoritme 3.2.12 dan sifat gcd himpunan. Input pada algoritme ini tidak harus polinomial monik bebas kuadrat. Berikut 2 algoritme pendukung sebelum masuk ke Algoritme Faktorisasi Berderajad

, yakni

Algoritme 3.2.12 dan Algoritme 3.2.13. Algoritme 3.2.12 Algoritme Sisa Bagi 1 Input : polinomial Output : sisa bagi 1.

2.

Set

( ) ∈ ℤ[ ]dan integer oleh

←deg( ( )) ←⌈log

( .)

⌉.

Jika 2 < , maka ambil hasil

.

Jika 2 > , maka lakukan langkah berikut : ( )←

( )←

Ambil hasil

mod

( )

( ) mod ( .)

( )

74

Algoritme 3.2.12 dimaksudkan untuk menentukan sisa pembagian

oleh

( , )diimplementasikan dengan bantuan software Maple 11, dapat dilihat pada

Lampiran 2.5.

Contoh 22 Sisa Bagi 1 untuk kasus deg( ( ))> 2 Diketahui ( ) =

Tentukan

mod

Penyelesaian :

+

+

( .)

+

+ 1, dan

Karena deg( ( ))= 16 > 4 = 2 , maka

( a)dalah

mod

Contoh 23 Sisa Bagi 1 untuk kasus deg( ( ))< 2 Diketahui ( ) =

Tentukan

+

mod ( ).

+

+

+ 1, dan

= 2. .

= 4.

Penyelesaian :

Karena deg( ( ))= 8 < 16 = 2 , maka langkah pertama adalah menentukan , = deg ( )

( )=

= 8. Kemudian hitung

mod ( ) =

( )=

( )

mod ( ) =

mod ( ) =

Jadi sisa baginya adalah

=⌈log

.

+

⌉ = 3.

+

+ 1.

.

Algoritme 3.2.13 Algoritme Sisa Bagi 2 Input : polinomial Output : sisa bagi 1) Set 2) Jika :

( ) ∈ ℤ[ ]dan integer

( )← sisa bagi

+ 1 oleh

( .)

oleh ( ( ))(perhitungan gunakan Algoritme 3.2.12)

2.1 Suku pertama polinomial  Jika suku pertama ℎ( ) ← ( ) +

( ) ← ℎ( ): .

( a)dalah 1, maka lakukan langkah berikut.

( a)dalah 1, maka lakukan langkah berikut. ( .)

( ) ← ( ) + 1.

Ambil hasil : ( .)

75

 Jika suku pertama

( )tidak sama dengan 1, maka lakukan langkah

berikut. ( ) ← ( ): .

( ) ← ( ) + 1.

a.

Ambil hasil ( .)

( )tidak sama dengan 1, maka lakukan

Suku pertama polinomial langkah berikut.  Jika suku pertama

( )sama dengan suku pertama

lakukan langkah berikut. ℎ( ) ← ( ) +

( ,) maka

( .)

( ) ← ℎ( ): .

( ) ← ( ) + 1.

Ambil hasil : ( .)

 Jika suku pertama

( )tidak sama dengan suku pertama

lakukan langkah berikut.

( ,)maka

( ) ← ( ): .

( ) ← ( ) + 1.

Ambil hasil ( .)

Algoritme 3.2.13 dimaksudkan untuk menentukan sisa pembagian + 1 oleh

( , ) diimplementasikan dengan bantuan software Maple 11,

dapat dilihat pada Lampiran 2.6. Contoh 24 Sisa Bagi 2 Diketahui ( ) =

Tentukan sisa bagi Penyelesaian :

+

+

+ 1 oleh

Berdasarkan Contoh 22, ( ) =

Karena suku pertama polinomial

dengan 1, maka : ( ) = ( ):

+

( .)

mod ( ) =

= 2. .

( a)dalah 1 dan suku pertama

= :

( ) = ( )+1 =

+ 1, dan

( t)idak sama

= .

+ 1.

76

Jadi sisa bagi

( a)dalah

+1 oleh

Algoritme 3.2.14

+ 1.

Algoritme Satu Faktor Derajad ( ) ∈ ℤ[ ]dan integer positif .

Input :

Output : satu faktor berderajad

beserta pangkatnya.

( )← gunakan Algoritme 3.2.13 dengan input polinomial

1.

positif .

2.

( ) ← gcd

( ), ( ) .

Jika

( ) = 1, maka hasilnya adalah

a) b) i.

( .)

( ) ≠ ,1maka lakukan langkah berikut : Jika deg

1) Set

( )

= , maka lakukan langkah berikut :

( )=

( .)

2) Untuk dari 1 selama gcd (

( ), ( )) =

3) Ambil hasil ( ) =

( )

( )←

ii.

( )dan integer

( )

Jika deg

1)

( )dibagi dengan ( )

( .)

( ,)lakukan :

≠ , maka lakukan langkah berikut :

( ) ←gunakan Algoritme 3.2.11 dengan input ←banyaknya faktor polinomial

( ) ← hasil bagi ( ) dengan

2) Untuk dari 1 sampai

lakukan

( .)

( d) an .

( )

( ) ←faktor ke- polinomial ( )

( ) ← hasil bagi( ) dengan

ℎ( ) ←sisa bagi ( d) engan ← 1.

( .)

( .)

Untuk selama ℎ( ) = 0 lakukan : ( ) ← hasil bagi( ) dengan

ℎ( ) ←sisa bagi ( d) engan Hasil : ( )

←

+ .1

( .)

( .)

( .)

77

Algoritme 3.2.14 dimaksudkan untuk memfaktorkan polinomial yang tidak bebas kuadrat, diimplementasikan dengan bantuan software Maple 11, dapat dilihat pada Lampiran 2.7. Contoh 25 Faktorisasi satu faktor berderajad . Diketahui : ( )= = 1.

+

+

+

+

+

+

+

+

+

+

+

+

+

+

+

+

+1

+

+

Tentukan : faktorisasi satu faktor derajad . Penyelesaian : ( )dan

Menggunakan Algoritme 3.2.13 dengan input yakni

( )=

( ) = gcd

Karena deg 

Set



Untuk

+ 1.

( ), ( )

( )

( )=

=

=

( .)

( ,)

+ .1

= ,1maka : ( ), ( )

dari 1 selama gcd

selama sisa bagi

diperoleh nilai

=

dengan kata lain ( atau )

( )dengan ( ( )) sama dengan nol, lakukan langkah

( )dengan ( ( )) . Hasilnya dapat dilihat pada tabel

berikut : bagi

perhitungan berikut.

Tabel 3.2.16 Hasil Perhitungan

( ): ( ( ))

( ): ( ( ))

1 2 3 4 5 6

+

+

+ +

+

+ +

+

+ +

hasil bagi ( ( ))

+ +

+

+

+

+ +

+ +

+

+

+

+

+

+

+

+

+

+

+

+

sisa bagi +

+

+

+

+1

+1

+

+

+ +

+1 +

+1

+1

0 0 0 0 0 1

78

Dari

tabel

terlihat

bahwa

pada

= 6,

saat

sisa

bagi

( ): ( ( )) ≠ 0, maka proses pembagian berhenti pada langkah ke-5 ( = 5)

dan hasil pemfaktoran ( )=

( )

( a)dalah :

( )=(

+ 1) (

+

Contoh 26 Faktorisasi satu faktor berderajad . Diketahui : ( ) =

+

+

+

+

+ 1, dan

+

+ 1)

= 2.

Tentukan : faktorisasi satu faktor derajad .

Penyelesaian : ( )dan

Menggunakan Algoritme 3.2.13 dengan input ( )=

yakni

( ) = gcd

Karena deg



Set



Untuk

+ 1.

( ), ( )

( )

=

=

( )=

+

= ,2maka :

( .)

+ 1. ( ), ( )

dari 1 selama gcd

=



selama sisa bagi berikut : bagi

( ,)

diperoleh nilai


perhitungan berikut. Tabel

( ): ( ( ))

1 2

+

+

3

+

4 5

Dari

+

tabel

terlihat

hasil bagi ( ( )) +

+

+

+

+

+

+

+

+

+

bahwa

+

+

+

+

+

+1 +

+1

pada

sisa bagi +

+

0

+1

0 0

+1

0

saat

= 5,

sisa

+

+ 1)

+1

bagi



( )

( a)dalah : ( )=(

+

+ 1) (

+

+

79

Contoh 27 Faktorisasi satu faktor berderajad . Diketahui : ( ) =

+

+

+

+ 1, dan

= 4.



Menggunakan Algoritme 3.2.13 dengan input ( )=

yakni

( ) = gcd Set



Untuk

( ), ( )

( )

Karena deg 

+ 1.

=

=

( )=

+

= ,4maka :

( .)

+

( ,)

+ 1.

( ), ( )

dari 1 selama gcd

=



selama sisa bagi berikut : bagi

+

diperoleh nilai


perhitungan berikut. Tabel

( ): ( ( ))

1

+

2 Dari

3

tabel

hasil bagi ( ( )) +

+

+

1 0

terlihat

sisa bagi 0

+1

0

bahwa

pada

1

= 3,

saat

sisa

bagi



( )

( a)dalah :

( )=(

+

+

+

+ 1) (1) = (

+

Contoh 28 Faktorisasi satu faktor berderajad .

+

+

+ 1)

Diketahui : ( )= dan

+

= 7.

+

+

+

+

+

+

+

+

+

+

+

+

+

+


80


Menggunakan Algoritme 3.2.12 dengan input yakni

( )=

( ) = gcd

Karena deg 

+

( ), ( )

( )

+

+

=

+ .1

+

+

+

+

= 1 ≠ 7 = , maka :

( )=

( ,)yakni :

+ 1.

=banyaknya faktor ( ) = .1

( ) = hasil bagi =

+

( d) engan

+

+

+

+

+

+

( )

+

+

+

+

( ) = faktor ke-1 polinomial ( ) =

( ) = hasil bagi ( ) dengan ( ). =

+

+

+

+

+

+

+

+

+ 1. ( )dan

Dengan menggunakan Algoritme 3.2.11 dengan input

diperoleh nilai



+

( ,)

diperoleh nilai

+

+

+

+

+

+

= 7,

+

+1

+

+

+

ℎ( ) = sisa bagi ( d) engan ( ) = 0. = 1.

( ) = hasil bagi ( ) dengan ( ). =

+

+

+

+

+1

+

+

+

+

+

+

ℎ( ) = sisa bagi ( d) engan ( ) = 1. 

= 2.

Hasil = =(

4.

( ) ( ) + 1) (

+

+

+

+

+

Faktorisasi Lengkap ( ) =

+

+

( )

+

+

+

+

( ) …

)

+

+

+

( ).

Algoritme faktorisasi lengkap adalah algoritme untuk memfaktorkan

polinomial

( ) ∈ ℤ[ ]sehingga ( ) =

( )

( ) … ( ) , untuk setiap

81

( ) adalah polinomial irredusibel atas ℤ [ ] dan setiap

≥ 1, 1 ≤

≤.

Algoritme ini adalah kombinasi dari Algoritme 3.2.11, 3.2.12, 3.2.13 dan 3.2.14. Algoritme 3.2.15 Algoritme Faktorisasi Lengkap Input : polinomial Output : ( ) = 1.

Jika

2.

Jika

( ) ∈ ℤ[ ]

( )

( )

( i)rredusibel, maka hasilnya

( )

( r)edusibel, maka lakukan langkah berikut :

a) Jika polinomial ( .)

b) Jika polinomial langkah berikut. Set i)

( ) … ( )

( )hanya mempunyai 1 suku, maka hasilnya adalah ( )mempunyai lebih dari 1 suku, maka lakukan

( ) ←suku terkecil polinomial

Jika

1) Set

( ,)

> 0, maka :

( ) ←hasil bagi polinomial

2) Untuk dari 1 sampai diperoleh

( d) engan

( ) .

( ) = 1 lakukan :


Set Set Jika

( ) ← gcd ( ( ),

Set

( ) ≠ 1, maka :

( )).

( )dan .

( ) ← gunakan Algoritme 3.2.14 dengan input dan .

Set ( ) ←

Set ii)

Jika

( )

( )dibagi faktor terakhir polinomial ( )

( ) ←faktor terakhir polinomial ( ).

= 0, maka lakukan langkah berikut :

Untuk dari 1 sampai diperoleh

( ) = 1 lakukan


Set Set Jika

( ) ← gcd ( ( ), ( )).

Set

( ) ≠ 1, maka :

( )dan .

( ) ← gunakan Algoritme 3.2.14 dengan input dan .

Set ( ) ←

( )

( )dibagi faktor terakhir polinomial ( ) 82

( ) ←faktor terakhir polinomial ( ).

Set Ambil hasil ( ) =

( )

( )

( ) … ( ) .

Algoritme 3.2.15 diimplementasikan dengan bantuan software Maple 11, dapat dilihat pada Lampiran 2.8. Contoh 29 Faktorisasi Lengkap Diketahui : ( )=

+

+

+

+

+

+

+

+

+

+

+

+

( .)

Tentukan : faktorisasi lengkap dari Penyelesaian :

+

+

+

+

+

( ) adalah polinomial irredusibel berderajad 22. ( )adalah

Karena suku terkecil polinomial pertama memfaktorkan ( )= Set

(

( )=

+

+ +

+

+

+

+

+

( )=

( ) = gcd

( ) =(



( )=

( )=

+

+

+

+

+

+

+

+

+

+

+

( ),

+ 1) (

+ 1) .

+

+

+

( )=1:

+

+ +

+

+

+ +

+

+

+

+

+

+

+ 1) +1

( )

=

+

+

+ .1

+

+

+

+ 1).

+ 1.

+ 1. (Perhitungan menggunakan Algoritme 3.2.12 dengan input

( ) dan 2)

( ) = gcd

( )=(

+

( )=

+

( ) =(

> 0, maka langkah


( ) dan 1) ( )=(

+

+

Untuk dari 1 sampai diperoleh 

( ) = ,

+

( a)dalah dengan membaginya dengan , diperoleh :

+

+

+

( ), +

( )

+ 1) (

+

+ 1) . +

+

=

+

+

+ 1.

+

+ 1).

+ 1. 83



( )=


( ) dan 3)

( ) = gcd

( ),

( )

= 1.

( ) = 1, maka proses selanjutnya kembali lagi mencari

Karena

atau dengan kata lain diperoleh : ( ) = 1(

+

+

( ) = 1, dan ( )=



( )=

( )=

( ) = gcd

( )=(

( ) =(

+

( ) = 1. =

( ),

( )

= (

+

+

( ) .

= ( 3.2.8.2

+

+ 1).

+

+

+ 1.


( ) dan 4)

Jadi ( ) =

+

( )

+

( )

( )

+ 1) (

+ 1) (

+

+

+

=

+ 1) (1).

+

+ 1.

+ 1) .

+

( )

( )

+ 1) (1)( + 1) (

+

+

( )

+

+

+

+

+

+ 1)

+

+ 1)

Solusi Masalah Logaritma Diskret pada Algoritme Index Calculus

Misalkan order irredusibel

adalah sebuah generator grup multiplikatif

(2)∗

menentukan

= 2 − 1,

adalah

berderajad , 0≤

Untuk menentukan

atas

≤

ℤ .

Masalah

(2)∗

dan

logaritma

( )∗ dengan (2)∗ , dengan

( )polinomial

diskret

≡ log

={ ,

,…,

} dari

, sedemikian sehingga elemen-elemen

efisien dapat dinyatakan sebagai produk dari elemen-elemen di ,…,

(mod

adalah ( )) .

(mod ( )), dengan Algoritme Index Calculus

Pertama pilih sebuah subset disebut faktor basis

∈

− ,1 sedemikian sehingga

≡ log

berikut langkah-langkahnya.

,

( ,)

(2)∗ , yang

(2)∗ secara . Dengan

adalah merupakan polinomial-polinomial irredusibel atas ℤ . Dalam 84

Menezes et al. (1997), belum ada ketentuan berapa banyak polinomial basis ( ) yang harus diambil atau dipilih. Dalam tulisan ini faktor basis

diambil atau

dipilih dari polinomial irredusibel-polinomial irredusibel atas ℤ yang berderajad kurang dari atau sama dengan setengah

.

Langkah kedua menghitung logaritma elemen-elemen , 0≤

integer acak

≤

elemen-elemen ;

− ,1 hingga

=

,

dapat dinyatakan sebagai produk

≥ 0.

( )

Peluang keberhasilan memfaktorkan faktor basis . Jika

ini tergantung dari pemilihan

besar maka peluang acak setiap anggota grup multiplikatif

(2)∗ dapat difaktorkan sebagai elemen-elemen

jika ukuran

. Caranya pilih

akan lebih besar, sebaliknya

lebih kecil maka peluang kegagalan memfaktorkan elemen-elemen (2)∗ akan lebih besar. Disisi lain ukuran

grup multiplikatif

lebih besar

mengakibatkan sistem persamaan linear yang harus dikumpulkan menjadi lebih banyak dan tahapan untuk menyelesaikan sistem persamaan linearnya pun menjadi lebih rumit dan panjang. Jika

sudah dapat difaktorkan, selanjutnya logaritmakan kedua ruas

persamaan ( )dengan basis =

log

log

=

.

= log (

= log ≡

untuk memperoleh persamaan ( ) :

.

.

log

… +

.

log

…

(mod

+ )

)

log

Prosedur ini diulang hingga diperoleh paling sedikit

+⋯+

(

log )

persamaan, sedemikian

sehingga sistem persamaan linear yang diperoleh tersebut konsisten dan memiliki solusi tunggal. Suatu persamaan linear disebut konsisten jika memiliki paling sedikit satu penyelesaian, disebut takkonsisten jika tidak memiliki penyelesaian.

85

Langkah ketiga, sistem persamaan linear yang diperoleh pada langkah 2 di atas diselesaikan untuk mendapatkan log

, untuk 1 ≤

. Pilih integer acak , 0 ≤

Langkah keempat menentukan

hingga

dapat dinyatakan sebagai produk elemen-elemen ≡

(

≤.

,

Langkah kelima menghitung log

≥0

≤

:

(

−1

)

. Logaritmakan kedua ruas persamaan

dengan ) basis , diperoleh : =

log

log

=

.

= log (

+ log

=

+ log

=

log

= log

.

.

log

…

+

=−

.

log

…

mod +

+

)

log

Berikut Algoritme Index Calculus pada Algoritme 3.2.16

log

+ ⋯+

log

mod

(2)∗.

Algoritme Index Calculus untuk menentukan masalah logaritma diskret pada (2 )∗

Deskripsi : menentukan solusi logaritma diskret , dimana Input :

∈

(2)∗ .


(2)∗ ,


Memilih faktor basis

≡ log .

(mod ( ))

={ ,

sehingga setiap elemen-elemen

,…,

≡

(mod

(2)∗ berorder } subset

( ).)

= 2 − 1,

(2 )∗ , sedemikian

(2)∗ secara efisien dapat dinyatakan

sebagai produk dari elemen-elemen di . 2)

Pilih bilangan acak , 0 ≤

dari elemen-elemen

≤

− .1Coba nyatakan

sebagai product

seperti berikut :

86

≥ 0.

dengan Jika

mod

berhasil

=∑

maka

log

logaritmakan

(mod

4) 5)

Menentukan nilai dari log

,1≤

Pilih integer acak , 0 ≤

ruas

sehingga

≤

≤.

− .1Coba tentukan

dari elemen-elemen di

sehingga

Jika

berhasil

logaritmakan

(∑

log

maka

kedua

diperoleh

). Ulangi langkah ini hingga diperoleh paling

sedikit persamaan. 3)

( )=

=∏

sebagai product

, dengan

kedua

ruas

sehingga

− )mod . Solusi logaritma diskret adalah : = log

=

−

+

≥ 0.

log

log

=

mod

Dalam Menezes et al. (1997) nilai harapan kompleksitas waktu Algoritme ,

Index Calculus adalah

=2 ,

, dimana

> 0 adalah konstanta.

Implementasinya dengan bantuan sofware Maple 11 dapat dilihat pada Lampiran 3.9. Contoh 30 (Menentukan masalah logaritma diskret pada grup siklik dengan Index Calculus) Diketahui : polinomial primitif ( ) = + + + + 1, ≡ log

Tentukan

Penyelesaian :  

Pilih

⊆

={ , = 13,

= 87,

+

+ 1.

(mod ( )). (2 )∗ .

+ 1, +

+ 1,

mod ( ) =

log

(2 )∗

(2)∗ , dan

generator =

=

= log

13 = 2 log

mod ( ) =

+

+ (

+

+ 1,

+

+

+ log ( +

=

+

+ 1) +

+1

(

+ 1}.

+

+ 1)

+ 1) ( ) 87

log

= log (

log

= 121,

+

= log (

100 = 2 log ( (

121 = log log

Dengan

+

+ 1) (

+ log (

= log (

145 = log ( = log

= log (

+

+ 1)(

+

+ 1) + log (

+

+ 1)

+ 1) (

+

+

+

+ 1)(

+ 1)

+ 1 =(

+ 1)(

+

+

= log (

persamaan ( ), ( ), ( ), ( ) dan ( ) diperoleh : 13 ≡ 2 87 ≡

100 ≡ 2

+

121 ≡  

+

145 ≡

+

)

( )

+ 1)(

+

= log (

dan

(

+ 1)

+ 1)

+ 1),

+ 1)

+ 1)

+ 1)

+

+

+ 1) + log (

+

+

+ 1) + log (

+

+

+ 1),

+

+

+

+

,

+

+ 1)

+ 1)

+ 1) + 2 log (

= (

mod ( ) =

+ 1)( +

+1=(

mod ( ) =

= log

+

+ 1)( +

+ 1) + log (

mod ( ) =

= 145, 

+ 1)(

+ 1)(

87 = log (

= 100,

log

=(

+

+ 1) +

+ 1)

= log ( + 1),

(

)

+ 1). +

maka

( )

+ 1), dari

(mod 255) +

+2

+

+

(mod 255) (mod 255)

+

(mod 255)

(mod 255)

Penyelesaian 5 sistem kongruensi di atas adalah : = 0,

= −58,

= 108,

Selanjutnya pilih , 0 ≤ = 50, maka :

=(

= Sehingga

=

≡ log

+

.

+

= 37,

≤

− .1

+ 1)

mod

+ 1.

mod ( )

=

= 13.

( )

− 50 (mod ( ))= 58.

Berikut Tabel Nilai Harapan Kompleksitas Waktu Algoritme untuk Algoritme Exhaustive Search, Baby-Step Giant-Step, Baby-Step Giant-Step 2,

88

Baby-Step Giant-Step 3, Naif Square, Pollard’s rho, Pohlig Hellman, dan Index Calculus. Tabel 3.2.17 Nilai Harapan Kompleksitas Waktu Algoritme No

3.3

Algoritme

Bentuk Oh-Besar O(2 )

1

Exhaustive Search

2

Baby-Step Giant Step

O(√2 )

3

Baby-Step Giant Step 2

O(√2 )

4

Baby-Step Giant Step 3

O(√2 )

5

Naif Square

O(√2 )

6

Pollard’s rho

O(√2 )

7

Pohlig Hellman

8

Index Calculus

(∑

,

,

(log 2 + =2 ,

>0

KOMPUTASI MASALAH LOGARITMA DISKRET PADA Diketahui

( )polinomial irredusibel atas ℤ ,

= 2 − 1 adalah order dari

memenuhi

≡

(mod

(2 )∗ ,

∈

(2)∗ ,

)

generator

( )∗

(2 )∗,

logaritma diskret yang

( )) . Berikut waktu komputasi logaritma diskret

dengan menggunakan Algoritme Exhaustive Search, Baby-Step Giant-Step, BabyStep Giant-Step 2, Baby-Step Giant-Step 3, Naif Square, Pollard’s rho, Pohlig Hellman, dan Index Calculus jika diketahui

dan

, dengan menggunakan

computer Intel Core 2 Duo 1,83 GHz 1 GB. Tabel 3.3.1. Waktu Komputasi dengan Algoritme Exhaustive Search (detik) 16

65.535

60.000

5,92

17

131.071

130.944

13,08

18

262.143

142.422

14,69

19

524.287

345.461

38,00

20

1.048.575

996.754

127,53

21

2.097.151

1.096.754

162,67

89

(detik) 22

4.194.303

3.167.543

539,90

23

8.388.607

6.987.241

1.337,89

24

16.777.215

10.765.423

2.320,59

25

33.554.431

30.768.121

6.377,30

Dari Tabel 3.3.1 terlihat bahwa dengan bertambah besarnya

dan , maka waktu

komputasi ( ) yang diperlukan untuk menentukan logaritma diskret

akan

semakin besar. Sehingga Algoritme Exhaustive Search ini lebih efektif digunakan (2)∗ berorder

menentukan masalah logaritma diskret pada grup multiplikatif kecil.

Tabel 3.3.2, 3.3.3, 3.3.4 dan 3.3.5 berikut adalah waktu komputasi untuk algoritme yang idenya adalah Algoritme Baby-Step Giant-Step pada grup siklik umum. Keempat algoritme tersebut pada fase baby-step (fase menyimpan mod ( ) ) memerlukan waktu komputasi yang sama. Walaupun pada

kenyataannya jika

mod ( ) sudah disimpan di memori komputer pada saat

mengkomputasi salah satu algoritme tersebut sebenarnya

mod ( ) dapat

digunakan untuk komputasi algoritme lain (Algoritme 3.2.2 , 3.2.3, 3.2.4 atau 3.2.5) dengan

yang sama.

Tabel 3.3.2 Waktu Komputasi dengan Algoritme Baby-Step Giant-Step (detik) =

+

16

65.535

60.000

0,00 + 1,13 = 1,13

17

131.071

130.944

0,00 + 0,17 = 0,17

18

262.143

142.422

0,16 + 0,20 = 0,36

19

524.287

345.461

0,16 + 0,27 = 0,43

20

1.048.575

996.754

0,13 + 0,58 = 0,71

21

2.097.151

1.096.754

0,08 + 0,53 = 0,61

22

4.194.303

3.167.543

0,15 + 0,97 = 1,12

23

8.388.607

6.987.241

0,27 + 1,50 = 1,77

24

16.777.215

10.765.423

0,28 + 1,65 = 1,93

25

33.554.431

30.768.121

0,08 + 3,63 = 3,71

90

Ket :

adalah waktu yang diperlukan untuk menentukan masalah logaritma

diskret dengan

adalah waktu untuk menyimpan

mod ( ) , 0 ≤

≤

komputer adalah sebanyak

− ,1

,

waktu menentukan nilai .

= √2 − 1 , yang disimpan di memori

dengan ide membagi

dengan

. Waktu komputasi

untuk algoritme ini sudah jauh lebih cepat jika dibanding dengan Algoritme Exhaustive Search pada saat

dan

sama.

Tabel 3.3.3 Waktu Komputasi dengan Algoritme Baby-Step Giant-Step 2 (detik) =

+

16

65.535

60.000

0,00 + 1,56 = 1,56

17

131.071

130.944

0,00 + 2,98 = 2,98

18

262.143

142.422

0,16 + 2,73 = 2,89

19

524.287

345.461

0,16 + 7,71 = 7,87

20

1.048.575

996.754

0,13 + 24,83 = 24,96

21

2.097.151

1.096.754

0,08 + 40,27 = 40,35

22

4.194.303

3.167.543

0,15 + 133,61 = 133,76

23

8.388.607

6.987.241

0,27 + 253,51 = 253,78

24

16.777.215

10.765.423

0,28 + 431,52 = 431,80

25

33.554.431

30.768.121

0,08 + 1.275,72 = 1.275,80

Ket :

adalah waktu yang diperlukan untuk menentukan masalah logaritma

diskret dengan

adalah waktu untuk menyimpan

mod ( ) , 0 ≤

≤

komputer adalah sebanyak

− ,1

,

waktu menentukan nilai .


dengan ide membagi

dengan

.

Tabel 3.3.4 Waktu Komputasi dengan Algoritme Baby-Step Giant-Step 3 (detik) =

+

16

65.535

60.000

8

0,00 + 0,11 = 0,11

17

131.071

130.944

8

0,00 + 0,19 = 0,19

18

262.143

142.422

10

0,16 + 0,10 = 0,26

19

524.287

345.461

10

0,16 + 0,15 = 0,31

20

1.048.575

996.754

10

0,13 + 0,54 = 0,67

91

(detik) =

+

21

2.097.151

1.096.754

11

0,08 + 0,33 = 0,41

22

4.194.303

3.167.543

12

0,15 + 0,37 = 0,52

23

8.388.607

6.987.241

11

0,27 + 1,72 = 1,99

24

16.777.215

10.765.423

14

0,28 + 0,34 = 0,62

25

33.554.431

30.768.121

12

0,08 + 5,80 = 5,88

mod ( ) , 0 ≤

≤

komputer adalah sebanyak ,

− ,1


dengan ide membagi

dengan

,

= 2 − 1. Untuk algoritme ini sebenarnya banyaknya

= 2, 0 ≤

mod ( )

yang boleh disimpan di memori komputer tidak harus sama dengan

≤

, tetapi

dalam tulisan ini untuk mempermudah fase baby-step maka digunakan mod ( )

yang sudah tersimpan di memori komputer pada waktu

mengkomputasi logaritma diskret dengan algoritme sebelumnya. Dari Tabel 3.3.2, 3.3.3 dan 3.3.4 terlihat perbedaan pada saat fase giant-step, Algoritme Baby-Step Giant-Step 2 memerlukan waktu komputasi logaritma diskret ( ) lebih lama jika dibandingkan dengan 2 algoritme lainnya. Tabel 3.3.5 Waktu Komputasi dengan Algoritme Naif Square (detik) 16

65.535

60.000

0,00 + 0,00 = 0,00

17

131.071

130.944

0,00 + 0,38 = 0,38

18

262.143

142.422

0,16 + 0,37 = 0,53

19

524.287

345.461

0,16 + 0,00 = 0,16

20

1.048.575

996.754

0,13 + 0,67 = 0,80

21

2.097.151

1.096.754

0,08 + 0,38 = 0,46

22

4.194.303

3.167.543

0,15 + 0,70 = 0,85

23

8.388.607

6.987.241

0,27 + 0,52 = 0,79

24

16.777.215

10.765.423

0,28 + 2,20 = 2,48

25

33.554.431

30.768.121

0,08 + 3,41 = 3,49

92

Sama seperti Algoritme Baby-Step Giant-Step, Baby-Step Giant-Step 2, dan BabyStep Giant-Step 3, perhitungan logaritma diskret dengan Algoritme Naif Square mod ( ) sebanyak . Terlihat pada Tabel 3.3.5

ini juga dengan menyimpan

ini waktu komputasinya juga lebih cepat jika dibanding dengan waktu komputasi logaritma diskret dengan Algoritme Baby-Step Giant-Step 2. Tabel 3.3.6 Waktu Komputasi dengan Algoritme Pollard’s rho (detik)

Ket

16

65.535

60.000

17.164

0,55

17

131.071

130.944

14.478

0,47

18

262.143

142.422

182.012

0,82

19

524.287

345.461

126.954

0,87

20

1.048.575

996.754

86.323

-

127.384

1,34

1.995.591

-

1.727.088

2,18

2.989.841

-

2.724.953

8,73

65.194

-

3.716.467

1,83

21 22 23

2.097.151 4.194.303 8.388.607

1.096.754 3.167.543 6.987.241

24

16.777.215

10.765.423

15.773.804

14,9

25

33.554.431

30.768.121

7.774.661

17,39

a) c) c) c)

Ket : a) tak ada invers modulo c) Jawaban tak sesuai/sama dengan y. Komputasi dengan Algoritme Pollard’s rho bergantung pada pemilihan tepat. Sehingga dalam komputasi dengan Algoritme Pollard’s rho ini

yang dipilih

dengan beberapa kali mencoba sampai ditemukan jawaban yang benar.

93

Tabel 3.3.7 Waktu Komputasi dengan Algoritme Pohlig-Hellman (detik) 16

65.535

60.000

0,23

17

131.071

130.944

13,28

18

262.143

142.422

30,23

19

524.287

345.461

39,69

20

1.048.575

996.754

0,15

21

2.097.151

1.096.754

0,29

22

4.194.303

3.167.543

0,46

23

8.388.607

6.987.241

7,72

24

16.777.215

10.765.423

0,34

25

33.554.431

30.768.121

1,45

Tabel 3.3.8 Waktu Komputasi dengan Algoritme Index Calculus Faktor basis (dlm 16

65.535

60.000

17

131.071

130.944

18

262.143

142.422

19

524.287

345.461

20

1.048.575

996.754

21

2.097.151

1.096.754

22

4.194.303

3.167.543

23

8.388.607

6.987.241

24

16.777.215

10.765.423

25

33.554.431

30.768.121

deg( ))

(detik)

≤4

7,15

≤3

12,69

≤5

36,37

≤4

193,06

≤4

680,48

≤4

4,08

≤3

30,65

≤4

74,14

≤5 ≤4

87,16 954,65

Komputasi logaritma diskret ( ) dengan Algoritme Index Calculus ini bergantung pada pemilihan faktor basis S, pemilihan

sedemikian sehingga

dapat

difaktorkan atas elemen-elemen .

94

Tabel 3.3.9 Waktu Komputasi Logaritma Diskret

dengan Beberapa Algoritme Waktu Komputasi (t) dalam Satuan Detik dengan Algoritme

m

n

y

Exhaustive Search

BSGS

BSGS 2

BSGS 3

Naif Square

t

t

t

t

t

Pohlig Hellman

Pollard’s rho d

t

Ket

t

16

65.535

60.000

5,92

1,13

1,56

0,11

0,00

17.164

0,55

0,23

17

131.071

130.944

13,08

0,17

2,98

0,19

0,38

14.478

0,47

13,28

18

262.143

142.422

14,69

0,36

2,89

0,53

182.012

0,82

30,23

19

524.287

345.461

38,00

0,43

7,87

0,31

0,16

126.954

0,87

39,69

20

1.048.575

996.754

127,53

0,71

24,96

0,67

0,80

86.323

-

127.384

1,34

1.995.591

-

1.727.088

2,18

2.989.841

-

2.724.953

8,73

65.194

-

3.716.467

1,83

21

22 23

2.097.151 4.194.303 8.388.607

1.096.754 3.167.543 6.987.241

162,67 539,90 1.337,89

0,61 1,12 1,77

40,35

133,76 253,78

0,26

0,41

0,52 1,99

0,46

0,85 0,79

7,15 4,08

≤3

12,69

≤3

30,65

≤5

36,37

c)

0,29

≤4

74,14

c)

0,46

≤4

193,06

c)

7,72

≤5

87,16

≤4

680,48

10.765.423

2.320,59

1,93

431,80

0,62

2,48

15.773.804

14,9

0,34

25

33.554.431

30.768.121

6.377,30

3,71

1.275,80

5,88

3,49

7.774.661

17,39

1,45

BSGS : Baby-Step Giant-Step

≤4

t

0,15

16.777.215

c) jawaban tak sesuai atau tak sama dengan y.

Faktor Basis dalam deg( )) ≤4

a)

24

Ket. a) tak ada invers modulo

Index Calculus

≤4

954,65

95

BAB IV KESIMPULAN DAN SARAN 4.1 KESIMPULAN Dari penelitian yang dilakukan dapat diambil beberapa kesimpulan sebagai berikut : 1.

Algoritme Exhaustive Search adalah algoritme untuk menentukan masalah logaritme diskret yang secara pasti akan memperoleh hasil yang tepat, tetapi karena metodenya dengan melacak lengkap maka algoritme ini tidak efisien untuk grup multiplikatif

2.

(2)∗ berorder besar.

Algoritme Baby-Step Giant-Step, Baby-Step Giant-Step 2, Baby-Step GiantStep 3, adalah algoritme yang ide dasarnya adalah membagi representasi polinomial √ ,

, dan 2 ,

dengan

, dengan ℎ untuk masing-masing algoritme adalah

adalah order grup multiplikatif

(2)∗ , dan 0 ≤

≤

sampai ditemukan salah satu representasi polinomial yang tersimpan di

memori komputer. Banyaknya representasi polinomial yang disimpan di memori komputer tidak harus sama dengan √ √

boleh kurang atau lebih dari

tergantung dari kapasitas memori komputer yang digunakan. Jika

representasi polinomial yang disimpan di memori komputer adalah sebanyak = √ , maka Algoritme Baby-Step Giant-Step 2 adalah algoritme yang

memerlukan waktu komputasi logaritme diskret 3.

yang paling banyak.

Algoritme Naif Square adalah algoritme yang juga dieksplorasi dari Algoritme Baby-Step Giant-Step pada grup siklik dengan mengalikan

dengan

umum, tetapi idenya

sampai ditemukan salah satu representasi

polinomial yang tersimpan di memori komputer. 4.

Grup multiplikatif

(2)∗ dipartisi menjadi 3 subset misalkan

,

, dan

Keberhasilan komputasi dengan Algoritme Pollard’s rho bergantung pada pendefinisian syarat keanggotaan himpunan , dan juga pada pemilihan Jika grup multiplikatif

(2)∗ berorder prima maka setiap

akan selalu menghasilkan logaritma diskret

.

yang terpilih

yang benar, tetapi jika grup

(2)∗ berorder komposit maka tidak semua

multiplikatif

akan menghasilkan logaritma diskret dilakukan pemilihan 5.

yang benar, jadi dalam hal ini

berulang-ulang sampai ditemukan

yang tepat.

Komputasi dalam Algoritme Pohlig Hellman dilakukan pada subgrup berorder prima berpangkat integer positif (

6.

yang dipilih

).

Faktorisasi polinomial dapat dilakukan dalam 4 tahap. Tahap pertama adalah faktorisasi bebas kuadrat, kedua faktorisasi bebas kuadrat berderajad , ketiga berderajad ,

faktorisasi 7.

( )=

( )

dan

terakhir

faktorisasi

lengkap

( ) … ( ).

Algoritme Index Calculus memerlukan penentuan faktor basis pemilihan

yang tepat, agar komputasi dan pemfaktoran

dan

lebih efisien.

4.2 SARAN Algoritme ∗

solusi

( ) dengan

masalah

logaritma

diskret

dapat

diaplikasikan

pada

= 5, 7, ….

97

DAFTAR PUSTAKA Adamek J. 1991. Foundation of Coding. John wiley & sons,Inc. Aliatiningtyas N. 2002. Struktur Aljabar. Bogor: Fakultas Matematika dan Ilmu Pengetahuan Alam, Institut Pertanian Bogor. Buchmann JA. 2000. Introduction to Cryptography. Springer-Verlag New York, Inc. USA. Fraleigh JB. 2000. A First Course in Abstract Algebra. Sixth Edition. AddisonWesley Publishing Company, Inc., USA. Guritman S. 2004. Struktur Aljabar. Bogor: Departemen Matematika, Institut Pertanian Bogor. Guritman S, Supriyo PT. 2004. Matematika Diskret. Bogor: Fakultas Matematika dan Ilmu Pengetahuan Alam, Institut Pertanian Bogor. Guritman S. 2005. Aljabar Linear Lanjut. Bogor: Program Pascasarjana, Institut Pertanian Bogor. Hankerson D, Menezes A, Vanstone S. 2004. Guide to Elliptic Curve Cryptography. CRC Press,Inc. New York. Hoffstein J, Pipher J, Silverman JH. 2008. An Introduction to Mathematical Cryptography. New York: Spinger. Leon SJ. 1998. Aljabar Linear dan Aplikasinya. Bondan A, penerjemah; Hardani HW, editor. Jakarta: Erlangga. Terjemahan dari: Linear Algebra with Application. Fifth Edition. Lestari E. 2007. Solusi Masalah Logaritma Diskret pada Grup Zn* dan keterkaitannya dalam Persetujuan Kunci Diffie-Hellman [skripsi]. Bogor: Fakultas Matematika dan Ilmu Pengetahuan Alam, Institut Pertanian Bogor. Menezes A, Oorschot PV, Vanstone S. 1997. Handbook of Applied Cryptography. New York: CRC Press, Inc. Michaels JG. 2000. Algebraic Structures. Di dalam: Rosen KH, editor in chief. Handbook of Discrete and combinatorial Mathematics. USA: CRC Press LLC. Munir R. 2001. Matematika Diskrit. Edisi Kedua. Bandung: Informatika. 98

Munir R. 2006. Kriptografi. Bandung: Informatika. Pretzel O. 1992. Error-Correcting Codes and Finite Fields. Oxford University Press, New York. Rosdiana S. 2009. Konstruksi Algoritme Aritmetika GF(2n) dengan Operasi Perkalian Dibangkitkan dari Sifat Grup Siklik [tesis]. Bogor: Program Pascasarjana, Institut Pertanian Bogor. Saeki M. 1997. Elliptic Curve Cryptosystem. [tesis]. School of Computer Science. McGill University, Montreal. Safaat R. 2007. Kajian Teoritik Algoritme Pollard p – 1 dan Algoritme Pollard ρ [skripsi]. Fakultas Matematika dan Ilmu Pengetahuan Alam, Institut Pertanian Bogor. Stinson DR. 2006, Cryptography Theory and Practice. Third Edition. Taylor & Francis Group, LLC.

99

LAMPIRAN

( )

Lampiran 1 Program Aritmetika Finite Field

(2 ) adalah program pendukung

Program Aritmetika Finite Field

untuk menyelesaikan masalah logaritma diskret GF(2^m)*, diacu dari tesis Rosdiana 2009. Program ini adalah program dengan mempergunakan software Maple 11. Jika diketahui

( )=

+

+

+ 1, maka dalam program ini

( b) erbentuk set, dengan representasi {0, 2, 3, 6}.

1. UbahBinKeSet (Prosedur untuk mengubah Vektor Biner ke Set) UbahBinKeSet:= proc(A::list) local H::set, i,n::integer: n := nops(A): H:={}: for i from 1 to n do if A[i]=1 then H:=H union {i-1}: end if: end do: return(H): end proc:

2. UbahDesKeSet (Mendefinisikan himpunan dari integer) UbahDesKeSet:=proc(n::integer) local X::list: X:=convert(n,base,2): UbahBinKeSet(X); end proc:

3. UbahSetKeDes (Prosedur untuk mengubah Set ke Desimal). UbahSetKeDes := proc( N::set ) local D::set, Des::integer; D:=map(x -> 2^x,N): Des:=add( i, i=D ); end proc:

4. AcakSet (Membangkitkan himpunan m bit secara acak). AcakSet:=proc(m::posint) local AcIn::procedure, p::integer: AcIn := rand(2^m): p:=AcIn(): UbahDesKeSet(p); end proc:

5. AdisiSet (Penjumlahan pada Himpunan) AdisiSet:=proc(S::set,T::set) return((S union T) minus (S intersect T)); end proc:

101

6. KaliSet (Perkalian pada Himpunan) KaliSet:=proc(A::set,B::set) local H::set, i,j::integer: H:={}: for i in A do H:=AdisiSet(H,map(j->(j+i),B)): end do: return(H): end proc:

7. MultiSet (Multiplikasi Himpunan dengan modulo

)

MultiSet:=proc(A::set,B::set,m::integer) local H::set: H:=KaliSet(A,B): ModSet(H,m); end proc:

8. BagiSet (Pembagian Himpunan dengan Himpunan) BagiSet:=proc(T::set,S::set) local K,Q,R::set, i,r,s,t::integer: R:=T: Q:={}: r:=max(op(R)): s:=max(op(S)): for i while r>=s do t:=r-s: Q:=Q union {t}: K:=KaliSet({t},S): R:=AdisiSet(K,R): r:=max(op(R)): end do: return([Q,R]); end proc:

9. InvSet (Invers Himpunan) InvSet:=proc(T::set,m::integer) local QA,QB,RA,RB,R,S,Tmp::set, L::list, i::integer: S:=DatB[m]: if T={} then return("Tidak ada invers") end if: RA:=S union {m}: RB:=T: QA:={}: QB:={0}: L:=BagiSet(RA,RB): RA:=RB: RB:=op(2,L): for i while RB<>{} do Tmp:=QA: QA:=QB: R:=KaliSet(QB,op(1,L)): QB:=AdisiSet(Tmp,R): L:=BagiSet(RA,RB): RA:=RB: RB:=op(2,L): end do: return(QB); end proc:

102

10. ModN (Prosedur yang menghitung a mod n 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: return(b): end proc:

11. ExpSet (Pangkat Himpunan) ExpSet:=proc(A::set,x::integer,m::integer) local H,G::set, X::list, i,p,k,n::integer: p:=2^m-1: k:=ModN(x,p): if k>=0 then X:=convert(k,base,2); G:=A: H:={0}: if op(1,X)=1 then H:=G: end if: for i from 2 to nops(X) do G:=MultiSet(G,G,m): if op(i,X)=1 then H:=MultiSet(H,G,m): end if: end do: else n:=-k: X:=convert(n,base,2); G:=InvSet(A,m): H:={0}: if op(1,X)=1 then H:=G: end if: for i from 2 to nops(X) do G:=MultiSet(G,G,m): if op(i,X)=1 then H:=MultiSet(H,G,m): end if: end do: end if: return(H); end proc:

12. PrimaRelAcak (Prosedur untuk membangkitkan bilangan prima relatif modulo 2 − 1 secara acak).

PrimaRelAcak:=proc(m::posint) local AcIn::PrimaRelAcak, g,i,R,p::integer: p:=2^m-1: AcIn := rand(p): R:=AcIn(): g:=gcd(R,p): for i while g<>1 do R:=AcIn(): g:=gcd(R,p): end do:

103

return(R): end proc:

13. HasilBagi (Hasil Bagi Himpunan) HasilBagi:=proc(A::set,B::set) local L::list: L:=BagiSet(A,B): return(op(1,L)); end proc:

14. SisaBagi (Sisa Pembagian Himpunan) SisaBagi:=proc(A::set,B::set) local L::list: L:=BagiSet(A,B): return(op(2,L)); end proc:

15. PangkatM (PangkatMod Himpunan) PangkatM:=proc(A::set,x::integer,B::set) local H,G,K,L::set, X::list, i::integer: X:=convert(x,base,2); G:=A: H:={0}: if op(1,X)=1 then H:=G: end if: for i from 2 to nops(X) do K:=KaliSet(G,G): G:=SisaBagi(K,B): if op(i,X)=1 then L:=KaliSet(H,G): H:=SisaBagi(L,B): end if: end do: return(H); end proc:

16. GcdSet (Gcd Himpunan) GcdSet:=proc(A::set,B::set) local RA,RB,S,T,L::set, i,a,b::integer: a:=max(op(A)): b:=max(op(B)): RA:=A: RB:=B: if a{} do L:=SisaBagi(RA,RB): RA:=RB: RB:=L: end do: return(RA); end proc:

104

17. TestIrrB (Test Reduce Himpunan) TestIrrB:=proc(A::set) local T,U,H,C,S,W::set, i,m,a::integer: if A={1} or A={0,1} then return(true); end if: if op(1,A)<>0 or (nops(A) mod 2)=0 then return(false); end if: a:=max(op(A)): m:=floor(a/2): W:={1}: for i from 1 to m do W:=PangkatM(W,2,A); U:=AdisiSet(W,{1}): H:=GcdSet(U,A): if H<>{0} then return(false); break; end if: end do: return(true); end proc:

Lampiran 2 Program Faktorisasi Polinomial 2.1 Faktorisasi Bebas Kuadrat 1

( )

OrderS:=proc(s::integer,G::set) local H,T,W,R,U::set, i::integer: U:=SisaBagi({s},G): W:=U: T:=SisaBagi({2*s},G): for i while T<>U do W:=AdisiSet(W,T): H:=KaliSet(T,T): T:=SisaBagi(H,G): end do: R:=GcdSet(W,G): return(R); end proc:

2.2 Faktorisasi Bebas Kuadrat 2 Order1S:=proc(G::set) local W,T::set, i::integer: W:=G: T:=OrderS(1,W): for i from 3 by 2 while T={0} or T=W do T:=OrderS(i,W): end do: return(T); end proc:

105

2.3 Faktorisasi Bebas Kuadrat 3 Order2S:=proc(G::set,m::posint) local R,T::set, i::integer: T:=Order1S(G): for i from 1 while max(op(T))<>m do T:=Order1S(T): end do: return(T); end proc:

2.4 Faktorisasi Bebas Kuadrat berderajad FaktorOS:=proc(G::set,m::posint) local R,W,T::set, i,j,k::integer: k:=(max(op(G))/m): j:=1: R:=[]: W:=G: for i from 1 while j
2.5 Sisa Bagi 1 SisaBagiM:=proc(m::integer,B::set) local R,P::set, b,l::integer: b:=max(op(B)): l:=ceil(eval(log[2](b))): if (2^m < b) then return({2^m}); else R:=SisaBagi({2^l},B): P:=PangkatM(R,2^(m-l),B); end if: end proc:

2.6 Sisa Bagi 2 SisaBagiMn1:=proc(m::integer,B::set) local R,U,H::set: R:=SisaBagiM(m,B): if op(1,B)=0 then if op(1,R)=0 then H:=AdisiSet(B,R): U:=map(i->i-1,H): AdisiSet(U,{0}); else U:=map(i->i-1,R): AdisiSet(U,{0}); end if: else if op(1,B)=op(1,R) then H:=AdisiSet(B,R): U:=map(i->i-1,H): AdisiSet(U,{0}); else

106

U:=map(i->i-1,R): AdisiSet(U,{0}); end if: end if: end proc:

2.7 Satu Faktor Derajad FaktorOM:=proc(A::set,m::posint) local G,K,B,C,W,H,T::set, R,L::list, i,j,k,s,t,c::integer: W:=SisaBagiMn1(m,A); G:=GcdSet(A,W): B:=A: R:=[]: if G={0} then return(A) end if: if max(op(G))=m then L:=BagiSet(B,G): K:=op(2,L): j:=0: for i while K={} do B:=op(1,L): j:=j+1: L:=BagiSet(B,G): K:=op(2,L): end do: return([[j,G],B]): else T:=FaktorOS(G,m); k:=nops(T): L:=BagiSet(B,G); B:=op(1,L): for i from 1 to k do C:=op(i,T): L:=BagiSet(B,C): H:=op(2,L): c:=1: for j while H={} do B:=op(1,L); L:=BagiSet(B,C): H:=op(2,L): c:=c+1: end do: R:=[op(R),[c,C]]: end do: return([op(R),B]); end if: end proc:

2.8 Faktorisasi Lengkap FaktorB:=proc(A::set) local B,G,W::set, R,L::list, T::symbol, i,bb::integer: T:=TestIrrB(A): if T=true then return(A) end if: if nops(A)=1 then return([op(A),{1}]): end if: B:=A: bb:=min(op(B)): R:=[]: if bb>0 then B:=map(x -> (x-bb),B): R:=[[bb,{1}]]:

107

for i from 1 while B<>{0} do W:=SisaBagiMn1(i,B); G:=GcdSet(B,W): if G<>{0} then L:=FaktorOM(B,i): R:=[op(R),seq(op(r,L),r=1..nops(L)-1)]: B:=op(nops(L),L); end if: end do: else for i from 1 while B<>{0} do W:=SisaBagiMn1(i,B); G:=GcdSet(B,W): if G<>{0} then L:=FaktorOM(B,i): R:=[op(R),seq(op(r,L),r=1..nops(L)-1)]: B:=op(nops(L),L); end if: end do: end if: return(R); end proc:

Lampiran 3 Program Solusi Masalah Logaritma Diskret pada Lampiran 3.1 Exhaustive Search

( )∗

NaiflogES:=proc(B::set,m::posint) local A::set, i,x::integer: A:={1}: x:=1: for i from 1 while A<>B do A:=MultiSet(A,{1},m): x:=x+1: end do: return(x): end proc:

Lampiran 3.2 Penyimpanan Baby-Step m:=1; a:=1; b:= ceil(sqrt(2^m-1)); DatBG5:=array(1..2^m-1): X:=ExpSet({1},a-1,m): for i from 1 to (b-a+1) do X:=MultiSet({1},X,m): h:=UbahSetKeDes(X): DatBG5[h]:=(a-1)+i: end do: save DatBG5, "d:\\ProgramGF\\GF2^m\\DatB5.m";

Lampiran 3.3 Baby-Step Giant-Step BSGS:= proc(T::set,m::posint) local p,i,j,h,s,k,z::integer, K,H::set, t::anything: p:=2^m-1: z:=ceil(sqrt(p)); K:=ExpSet({1},-z,m); H:=T: s:=UbahSetKeDes(H);

108

t:=DatBG25[s]; k:=t: j:=0: for i from 1 while type(t,'indexed') do H:=MultiSet(H,K,m): s:=UbahSetKeDes(H); t:=DatBG25[s]; j:=j+1: k:=(z*j+t) mod p: end do: return(k); end proc:

Lampiran 3.4 Baby-Step Giant-Step 2 BSGS2:= proc(T::set,m::posint) local p,i,j,h,s,k::integer, K,H::set, t::anything: p:=2^m-1: K:=ExpSet({1},-m,m); H:=T: s:=UbahSetKeDes(H); t:=DatBG5[s]; k:=t: j:=1: for i from 1 while type(t,'indexed') do H:=MultiSet(H,K,m): s:=UbahSetKeDes(H); t:=DatBG5[s]; j:=j+1: k:=(m*(j-1)+t) mod p: end do: return(k); end proc:

Lampiran 3.5 Baby-Step Giant-Step 3 BSGS3:= proc(T::set,x::posint,m::posint) local p,i,j,g,h,s,u::integer, H,K,S,U::set, t::anything: p:=2^m-1: g:=2^x: S:=ExpSet({1},g,m): K:=InvSet(S,m): U:=T: u:=op(1,U): if u<>0 then H:=map(k->k-u,U): s:=UbahSetKeDes(H); t:=DatBG5[s]; else s:=UbahSetKeDes(U); t:=DatBG5[s]; end if: j:=0: for i from 1 while type(t,'indexed') do U:=MultiSet(U,K,m): u:=op(1,U): if u<>0 then H:=map(k->k-u,U): s:=UbahSetKeDes(H); t:=DatBG5[s]; else s:=UbahSetKeDes(U);

109

t:=DatBG5[s]; end if: j:=j+1: end do: h:=(j*g+t+u) mod p: return(h); end proc:

Lampiran 3.6 Naif Square NaifSqrB:= proc(T::set,m::posint) local p,i,j,h,s::integer, H::set, t::anything: p:=2^m-1: H:=T: s:=UbahSetKeDes(H); t:=DatBG5[s]; j:=1: for i from 1 while type(t,'indexed') do H:=MultiSet(H,T,m): s:=UbahSetKeDes(H); t:=DatBG5[s]; j:=j+1: end do: h:=(t*(1/j)) mod p: return(h); end proc:

Lampiran 3.7 Pollard’s rho 3.7.1 FPolard (Pendefinisian Syarat Keanggotaan

untuk Algoritme Pollard’s

rho). FPolard:=proc(L::list,A::set,B::set,m::posint) local a,b,q,h::integer, H::set: q:=2^m-1: H:=op(1,L): a:=op(2,L): b:=op(3,L): h:=op(nops(H),H) mod 3: if h=0 then H:=MultiSet(H,A,m): a:=(a+1) mod q: elif h=1 then H:=MultiSet(H,B,m): b:=(b+1) mod q: else H:=MultiSet(H,H,m): a:=(2*a) mod q: b:=(2*b) mod q: end if: return([H,a,b]); end proc:

3.7.2 AlgPolard (Algoritme Pollard's Rho) AlgPolard:=proc(T::set,n::integer,m::posint) local i,aM,bM,aL,bL,q,r,s,u::integer, Hm,Hl,G::set, L,M::list: q:=2^m-1: G:=ExpSet({1},n,m): M:=[{0},0,0]: M:=FPolard(M,G,T,m): L:=M:

110

Hm:=op(1,M): L:=FPolard(L,G,T,m): Hl:=op(1,L): for i while Hm<>Hl do M:=FPolard(M,G,T,m): Hm:=op(1,M): L:=FPolard(L,G,T,m): L:=FPolard(L,G,T,m): Hl:=op(1,L): end do: aM:=op(2,M): bM:=op(3,M): aL:=op(2,L): bL:=op(3,L): r:=(bL-bM) mod q: if r=0 then return(FAIL); else s:=(aM-aL) mod q: u:=(s/r) mod q; return(u); end if: end proc:

Lampiran 3.8 Pohlig-Hellman Naiflog:=proc(A::set,B::set,m::posint) local K::set, i,x::integer: K:=A: x:=1: for i from 1 while K<>B do K:=MultiSet(K,A,m): x:=x+1: end do: return(x): end proc: PolHellman:=proc(B::set,m::posint) local i,l,c,R,n,r,s,u,q,t,j,k::integer,P::anything, xA,d,G,Y,g,L,b,a,T,iG,bG,xB,X::set: n:=2^m-1: P:=ifactor(n); r:=nops(P); X:=[seq(0*i,i=1..r)]; Y:=[seq(0*i,i=1..r)]; for i from 1 to r do s:=op(i,P); q:=op(op(1,s)); if nops(s)=1 then t:=1: else t:=op(2,s); end if: g:={0}: l:=0: u:=n/q: xA:=ExpSet({1},u,m); for j from 0 to (t-1) do if j=0 then k:=0; else k:=R*(q^(j-1)): end if: T:=ExpSet({1},k,m); G:=MultiSet(g,T,m): iG:=InvSet(G,m):

111

bG:=MultiSet(iG,B,m): xB:=ExpSet(bG,(n/(q^(j+1))),m): R:=Naiflog(xA,xB,m); l:=l+(R*(q)^j); end do: X[i]:=l; b:=(q^j); Y[i]:=b; end do; a:=X; d:=Y; c:=chrem(a,d); return(c); end proc:

Lampiran 3.9 Index Calculus 3.9.1 Program untuk memisahkan polinomial dengan pangkatnya PisahPangkat:=proc(m::integer,A::set) local n,s,t::integer, roll,P,Q,w::symbol, E::set, F,K,L,M::list: n:=2^m-1; roll := rand(1..n-1): s:=roll(); E:=MultiSet(A,(ExpSet({1},s,m)),m); F:=FaktorB(E); w:=whattype(F): if w=set then M:=[[F],[1],s]; elif nops(op(1,F))=1 then M:=[[op(2,F)],[op(1,F)],s]; else P:=array(1..nops(F)): Q:=array(1..nops(F)): for t from 1 to nops(F) do P[t]:=op(1,op(t,F)); Q[t]:=op(2,op(t,F)); end do: K:=convert(P, `list`); L:=convert(Q, `list`); M:=[L,K,s]; end if: return(M); end proc:

3.9.2 Program Ekstrak untuk matriks EkstrakMP:=proc(M::list,S::symbol) local M2,A,list,Z1,MM::list, i,m,f,r::integer, M1,L::set, J,Z::symbol, a,b::anything: r:=op(3,M); MM:=[op(op(1,M))]; M1:={op(op(1,M))}; M2:=(op(2,M)); A:=convert(S, `list`):

112

L:={op(A)}; J:= M1 subset L; if J=true then Z:=array(1..nops(A)): for i from 1 to nops(A) do Z[i]:=0; end do: for m from 1 to nops(MM) do b:=op(m,MM); for f from 1 while a <> b do a:=op(f,A); end do: Z[f-1]:=op(m,M2); end do: Z1:=convert(Z, `list`): else Z1:=[]; r:=[]; end if: return(Z1,r); end proc:

3.9.3 Program Solusi Masalah Logaritma Diskret with(LinearAlgebra): Solusi:=proc(B::set,m::integer,L::symbol) local n,Hasil,RS,rS,i,j::integer, Cek,SS,a,CC,MM,BB,PP,C,N,V,A,M,T,H,Q::list, P,t,S,SH::anything, SB::symbol: n:=2^m-1; Q:=[op(convert(L, `list`))]; for j from 1 while RS<>nops(Q) do H:=[]; T:=[]; for i from 1 while nops(H)<>nops(Q) do M:=PisahPangkat(m,{0}); A:=[EkstrakMP(M,L)]; if A <> [[], []] and SB=false then H:=[op(H),op(1,A)]: T:=[op(T),op(op(2,A))]: SH:= Matrix(H): rS:=Rank(SH); end if: SB:={op(1,A)} subset {op(H)}; end do: V:=H; N:= map(x->(x mod n),T); S := Matrix(V): RS:=Rank(S); end do: t := Vector(N): P:=LinearSolve(S, t, method='modular'); C:=convert(P, `list`); PP:=map(x->(x mod n),C); BB:=B; for j from 1 while Cek<>BB do MM:=PisahPangkat(m,B); CC:=[EkstrakMP(MM,L)]; if CC <> [[], []] then

113

a:=op(1,CC); SS:=[seq((op(i,a)*op(i,PP)) mod n,i=1..nops(a))]; Hasil:=(add( i, i=SS )-op(op(2,CC))) mod n; Cek:=ExpSet({1},Hasil,m); end if: end do: return(Hasil); end proc:

3.9.4 Program untuk menyimpan polinomial basis . SubBasis6:=array(1..11): J:=GenIrrDm(5); L:=op(6,J); SubBasis6[11]:=L; save SubBasis6, "e:\\Bahan Tesis Aq\\ProgramGF\\GF2^m\\SubBasis6.m"; print(SubBasis6);

114

EKSPLORASI MASALAH LOGARITMA DISKRET PADA FINITE FIELD ( ) Y A N A

Recommend Documents