Sidang Tugas Akhir

Yuliarti Ningsih
G05400004

Masalah Residu Kuadratik

Masalah residu kuadratik memuat pertanyaan apakah a adalah residu kuadratik modulo n atau bukan jika diberikan n >= 3 integer ganjil dan a,x suatu integer. Jika ada solusi yang memenuhi x pangkat 2 ? a(mod n), maka a adalah residu kuadratik modulo n. Hal yang sama juga berlaku untuk sebaliknya. Tujuan penulisan ini adalah untuk mempelajari teorema dan definisi yang berhubungan dengan masalah residu kuadratik. Kemudian dari teorema tersebut akan dikostruksi algoritma penyelesaian masalah residu kuadratik. Hasil dari skripsi ini menunjukkan bahwa unttu menyelesaikan masalah residu kuadratik diperlukan algoritma faktorisasi integer. Akan dilakukan pemfaktoran lebih dulu untuk n yang diketahui nilainya. Kemudian Simbol Jacobi akan menentukan apakah kongruensi diatas memiliki solusi berdasarkan beberapa teorema dan definisi yang berhubungan dengan masalah tersebut. Adapun untuk n yang sangat besar, penyelesaian masalah residu kuadratik tidak lebih mudah bila dibandingkan dengan n prima. Bila faktor n diketahui, sampai saat ini belum ada cara yang efisien dalam menyelesaikan masalah residu kuadratik. Jika suatu kongruensi telah diketahui memiliki solusi, maka selanjutnya adalah menentukan solusi tersebut. Hal terakhir itu tidak dibahas lebih lanjut. Demikian pula dengan aplikasi masalah residu kuadratik itu sendiri. Meski begitu salah satu masalah dalam teori bilangan ini sangat bermanfaat dalam kriptografi.