ABSTRAK
Nama : Febry Antonius
Program Studi : Ilmu Komputer
Judul : Faktorisasi Integer Besar dengan Algoritma Quadratic
Sieve untuk Aplikasi Kriptografi
Kriptografi kunci publik sering kali digunakan untuk meningkatkan keamanan komputer
maupun komunikasi data. Kriptografi kunci publik juga memungkinkan pembuatan
dan penggunaan digital signature. RSA adalah salah satu kriptosistem
kunci publik yang paling sering digunakan saat ini. RSA memanfaatkan kompleksitas
faktorisasi integer besar untuk keamanannya. Faktorisasi integer merupakan
salah satu permasalahan yang masih sulit diselesaikan secara efisien. Sampai
saat ini, belum ada algoritma yang dapat menyelesaikan permasalahan ini dengan
waktu polinomial. Quadratic Sieve merupakan salah satu algoritma faktorisasi integer
tercepat setelah algoritma Number Field Sieve. Meskipun begitu, algoritma
Quadratic Sieve masih membutuhkan waktu eksponensial untuk menyelesaikan
permasalahan faktorisasi integer. Tugas akhir ini menelaah algoritma Quadratic
Sieve dan mengimplementasikannya untuk menyelesaikan faktorisasi integer. Untuk
memahami algoritma tersebut, diperlukan pengetahuan-pengetahuan seperti
residu kuadratik, smooth numbers, dan simbol Legendre. Program dibangun dengan
menggunakan bahasa Python 3.3.2 dan dijalankan pada komputer dengan prosesor
Intel(R) Core(TM) i7-4770S CPU @ 3.10GHz, memori 8 GB dan menggunakan
sistem operasi Linux Ubuntu 13.10. Bahasa Python sangat membantu dalam
proses implementasi karena Python mampu melakukan operasi pada integer besar
dengan mudah. Beberapa trik juga diimplementasikan dalam program yang dibangun
untuk melakukan optimisasi kompleksitas waktu maupun kompleksitas memori
yang digunakan. Eksperimen yang dilakukan pada tugas akhir ini adalah membandingkan
waktu yang diperlukan algoritma Quadratic Sieve dan Trial Division
dalam melakukan faktorisasi integer besar. Hasil eksperimen menunjukkan bahwa
algoritma Trial Division dalam waktu 79,5 jam belum berhasil memfaktorkan sebuah
integer 36 digit sedangkan algoritma Quadratic Sieve dapat memfaktorkannya
dalam waktu 244 detik. Hasil eksperimen juga memperlihatkan bahwa algoritma
Quadratic Sieve membutuhkan waktu 2 jam 30 menit untuk memfaktorkan sebuah
integer 50 digit. Hasil plotting menunjukkan bahwa bentuk kurva kompleksitas
dari algoritma Quadratic Sieve yang diimplementasikan mirip dengan bentuk kurva
kompleksitas dari algoritma Quadratic Sieve yang teoritis.
|
|