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.