Skip to content
Narrow screen resolution Wide screen resolution Auto adjust screen size Increase font size Decrease font size Default font size blue color orange color green color Sign In

Matematika IPB

Beranda arrow Akademik arrow S-1 Matematika arrow Karya Ilmiah Alumni
 
Data Tesis
 
Judul : EKSPLORASI MASALAH LOGARITMA DISKRET PADA FINITE FIELD GF(5m)
Jenis :
Penulis : Salamia, Dra.
NRP : G551070621
Tanggal Lulus : 20 January 2011
Tanggal Seminar :
Tanggal Sidang :
Pembimbing : Dr. Sugi Guritman
Dra. Nur Aliatiningtyas, MS.
Drs. Prapto Tri Supriyo, M.Kom.
Ringkasan : Misal 􀜩 adalah grup siklik hingga berorder 􀝊, 􀟙 adalah generator dari 􀜩, dan 􀟚􀗐􀜩. Logaritma diskret dari 􀟚 dengan basis 􀟙 dinotasikan log􀮑􀟚 adalah integer positif unik 􀝕, 0􀵑􀝕􀵑􀝊􀵆1, sedemikian sehingga 􀟙􀯬 􀵌 􀟚. Bagaimana menentukan nilai 􀝕 disebut masalah logaritma diskret pada grup siklik hingga 􀜩 (Menezes et al. 1997). Mudah untuk menghitung nilai 􀝕 jika dipilih 􀝊 yang relatif kecil, akan tetapi akan menjadi tak layak hitung jika dipilih 􀝊 yang relatif besar. Algoritme untuk menentukan solusi masalah logaritma diskret adalah algoritme Exhaustive search, algoritme Baby-step Giant-step, algoritme Pollardrho, algoritme Pohlig-Hellman, dan algoritme Index-calculus. Algoritmealgoritma tersebut telah digunakan pada grup siklik 􀔺p􀗛 dengan 􀝌 bilangan prima (Menezes et al. 1997). Eksplorasi algoritme-algoritme tersebut dilakukan sehingga dapat digunakan untuk menentukan solusi masalah logaritma diskret pada 􀜩􀜨􁈺5􀯠􁈻􀗛. Hasil eksplorasi yang diperoleh adalah algoritme Negative Exhaustive search (pelacakan lengkap negatif), algoritme Baby-step Giant-step 2, algoritme Baby-step Giant-step 3 algoritme Baby-step Giant-step 4, algoritme Pohlig Hellman untuk 􀝉 genap atau 􀝉 ganjil, dan algoritme Pollard rho untuk grup berorder komposit. Himpunan semua polinomial dalam peubah (indeterminit) 􀟙 dengan koefisien 􀔺􀬹, dinotasikan dengan 􀔺􀬹􁈾􀟙􁈿. Jika dipilih 􀝂􁈺􀟙􁈻􀗐􀔺􀬹􁈾􀟙􁈿 adalah polinomial irreducible berderajat 􀝉 atas 􀔺􀬹 dan suatu 􀟙􀗐􀔺5􁈺􀟙􁈻 dengan 􀔺5􁈺􀟙􁈻 merupakan perluasan field dari 􀔺􀬹 maka 􀜩􀜨􁈺5􀯠􁈻􀵌􀔺5􁈾􀟙􁈿 / 􀛦􀝂􁈺􀟙􁈻􀛧􀵌􀔺5􁈺􀟙􁈻 adalah finite field berorder 5􀯠 di bawah operasi penjumlahan dan perkalian modulo 􀝂􁈺􀟙􁈻. Setiap elemen 􀜩􀜨􁈺5􀯠􁈻 dapat direpresentasikan dalam bentuk polinomial yaitu 􀜩􀜨􁈺5􀯠􁈻􀵌􀜾􀬴􀵅􀜾􀬵􀝔􀬵􀵅􀜾􀬶􀟙􀬶􀵅􀚮􀵅􀜾􀯠􀭀􀬵􀟙􀯠􀬿􀬵 dengan 􀜾􀯜 􀗐􀔺5 dan dapat juga direpresentakan dalam bentuk vektor yaitu 􀜩􀜨􁈺5􀯠􁈻􀵌􁈼􁈾􀜾􀬴,􀜾􀬵,􀜾􀬶,,􀜾􀯠􀬿􀬵􁈿 | 􀜾􀯜 􀗐􀔺5􁈽. Elemen-elemen tak nol dari 􀜩􀜨􁈺5􀯠􁈻 membentuk grup siklik perkalian dinotasikan dengan 􀜩􀜨􁈺5􀯠􁈻􀗛 berorder 􀝊􀵌5􀯠􀵆1, jadi 􀜩􀜨􁈺5􀯠􁈻􀗛􀵌􀜩􀜨􁈺5􀯠􁈻􀵆􁈼0􁈽. Jika dipilih 􀝂􁈺􀟙􁈻􀗐􀔺􀬹􁈾􀟙􁈿 polinomial primitif maka 􀟙 adalah generator 􀜩􀜨􁈺5􀯠􁈻􀗛. Sehingga 􀜩􀜨􁈺5􀯠􁈻􀗛􀵌􀛦􀟙􀛧􀵌􁈼1,􀟙,􀟙􀬶,,􀟙􀯡􀬿􀬵􁈽. Diberikan grup siklik hingga 􀜩􀜨􁈺5􀯠􁈻􀗛 berorder 􀝊􀵌5􀯠􀵆1 , dengan 􀟙,􀟚􀗐􀜩􀜨􁈺5􀯠􁈻􀗛, 􀟙 adalah generator dan 􀝂􁈺􀟙􁈻􀗐􀔺􀬹􁈾􀟙􁈿 polinomial primitif berderajat 􀝉 atas 􀔺􀬹. Logaritma diskret dari 􀟚 dengan basis 􀟙 dinotasikan log􀮑􀟚 adalah integer positif unik 􀝕, 0􀵑􀝕􀵑􀝊􀵆1 sedemikian sehingga 􀟙􀯬 􀘠􀟚􁈺mod 􀝂􁈺􀟙􁈻. Bagaimana menentukan integer 􀝕 disebut masalah logaritma diskret pada 􀜩􀜨􁈺5􀯠􁈻􀗛 ((Menezes et al. 1997). Algoritme Exhaustive search (pelacakan lengkap) merupakan algoritme yang berdasarkan pada definisi masalah logaritma diskret. Solusi masalah logaritma diskret diperoleh dengan cara melacak semua kemungkinan solusi yang ada. Kemungkinan solusi sebanyak 􀝊. Kemungkinan terburuk jika solusi ada pada pelacakan ke-􀝊. Oleh karena itu komputasi algoritme pelacakan lengkap kurang efisien jika dipilih 􀝊 yang relatif besar. Berdasarkan sifat order, di mana 􀜩􀜨􁈺5􀯠􁈻􀗛 selalu berorder genap. Sifat ini menjadi ide dasar eksplorasi algoritme pelacakan lengkap. Algoritme hasil ekplorasi adalah algoritme pelacakan lengkap negatif. Algoritme ini lebih efisien karena komputasi dilakukan hanya sampai pada setengah order 􀜩􀜨􁈺5􀯠􁈻􀗛. Algoritme Baby-step Giant-step 1 melalui dua tahap perhitungan yaitu tahap satu disebut Baby-step dan tahap dua disebut Giant-step 1 (Hoffstein et al. 2008). Tahap Baby-step digunakan untuk mengurangi beban komputasi dengan menggunakan memori komputer. Tahap Giant-step digunakan untuk memperoleh solusi. Jika dipilih 􀝊 yang relatif besar maka diperlukan memori komputer yang besar. Oleh karena itu eksplorasi algoritme Baby-step Giant-step 1 dilakukan sehingga diperoleh algoritme yang dapat mengurangi beban memori komputer. Algoritme tersebut adalah algoritme Baby-step Giant-step 2, algoritme Baby-step Giant-step 3 , dan algoritme Baby-step Giant-step 4. Algoritme Pollard-rho mengambil ide dasar teori Floyd's Cycle-finding dan teori Birthday Paradox. Teori Birthday paradox digunakan untuk menjamin bahwa adanya satu atau lebih bilangan yang sama dalam barisan dengan peluang lebih dari setengah sedikitnya setelah langkah ke √n√2 ln 2 (Hoffstein et al. 2008). Teori Floyd's cycle-finding digunakan untuk menemukan cycle dalam barisan 􁈼􀝔􀬴,􀝔􀬵,􀝔􀬶,,􀝔􀯞􁈽 dengan membandingkan unsur-unsur 􀝔􀯜 dengan 􀝔􀬶􀯜 sehingga diperoleh pasangan 􀝔􀯜 􀵌􀝔􀬶􀯜. Pasangan 􀝔􀯜 􀵌􀝔􀬶􀯜 diperoleh dengan membangkitkan suatu barisan fungsi dari barisan 􁈼􀝔􀬴,􀝔􀬵,􀝔􀬶,,􀝔􀯞􁈽 yang dipartisi menjadi tiga bagian. Selanjutnya dibangkitkan fungsi lain untuk memperoleh solusi. Algoritme Pollard-rho biasanya digunakan pada grup siklik berorder prima. Order 􀜩􀜨􁈺5􀯠􁈻􀗛. selalu komposit. Oleh Karena itu dilakukan eksplorasi algoritme Pollard-rho. Eksplorasi dilakukan pada pemilihan basis. Jika dipilih basis 􀟙􀯣, di mana gcd􁈺􀝊,􀝌􁈻􀵌1 dan 􀝌 dipilih secara acak maka diperoleh algoritme yang dapat digunakan untuk menentukan solusi masalah logaritme diskret pada 􀜩􀜨􁈺5􀯠􁈻􀗛. Pemilihan 􀝌 memerlukan waktu yang lama sehingga algoritme ini kurang efisien digunakan pada 􀜩􀜨􁈺5􀯠􁈻􀗛. Algoritme Pohlig-Hellman dipengaruhi oleh faktorisasi prima dari order grup. Algoritme ini hanya berlaku pada 􀜩􀜨􁈺5􀯠􁈻􀗛 untuk 􀝉 ganjil (Menezes et al., 1997). Eksplorasi dilakukan berdasarkan pada sifat grup siklik 􀜩􀜨􁈺5􀯠􁈻􀗛. Algoritme hasil eksplorasi dapat digunakan untuk 􀝉 ganjil maupun 􀝉 genap. Algoritme Index-Calculus dapat digunakan untuk menentukan solusi masalah logaritma diskret pada 􀜩􀜨􁈺5􀯠􁈻􀗛 (Menezes et al. 1997). Kekuatan algoritme ini terletak pada faktorisasi polinomial. Ide dasarnya adalah memilih subset 􀜵􀵌􁈼􀜲􀬵,􀜲􀬶,,􀜲􀯧􁈽 dari 􀜩􀜨􁈺5􀯠􁈻􀗛 sebagai faktor basis sedemikian sehingga elemen-elemen 􀜩􀜨􁈺5􀯠􁈻􀗛dapat dinyatakan sebagai produk dari elemen-elemen 􀜵. Implementasi algoritme-algoritme yang dihasilkan menggunakan software Maple 11. Komputasi masalah logaritma diskret pada 􀜩􀜨􁈺5􀯠􁈻􀗛 dapat dilakukan kasus per kasus berdasarkan nilai 􀝉. Algoritme Pohlig-Hellman cukup efisien untuk menentukan solusi masalah logaritma diskret pada 􀜩􀜨􁈺5􀯠􁈻􀗛 untuk 􀝉 􀵑 20. Kata kunci: grup siklik, masalah logaritma diskret, finite field 􀜩􀜨􁈺5􀯠􁈻.

Random Quotes

Kebiasaan membuat segala hal menjadi mudah.

anonim