Seminar Tugas Akhir

Bangun Jati Kusumo
G54101045

Algoritma Uji Komposit Berdasarkan Teorema Kongruensi Fermat dan Teorema Strong Pseudoprime

Dalam menentukan apakah suatu bilangan bulat positif ganjil m merupakan bilangan komposit atau bukan, diperlukan suatu uji. Uji tersebut dinamakan uji komposit. Uji komposit 1 adalah uji yang didasarkan pada teorema Kongruensi fermat. Input dari uji ini adalah bilangan bulat m dan a sebagai basis. Jika uji berhasil maka m dapat dikatakan sebagai bilangan komposit. Jika tidak, maka m dikatakan bilangan diduga prima berbasis a, dimana a adalah angota dari himpunan bilangan-bilangan bulat modulo m yang relatif prima dengan m. Uji komposit II adalah uji yang didasarkan pada Teorema Strong Pseudoprime. Input dari uji ini adalah bilangan yang tidak dapat ditemukan kekompositannya menggunakan uji komposit II, yaitu bilangan diduga prima berbasis a. Jika uji berhasil maka m merupakan bilamngan komposit dan disebut bilangan semu bebasis a. Jika tidak, maka m dikatakan bilangan diduga kuat prima berbasis a. Uji Carmichael adalah uji untuk menentukan apakah suatu bilangan merupakan bilangan Carmichael atau bukan. Input dari uji ini adalah bilangan prima semu berbasis a. Jika uji berhasil maka bilangan tersebut merupakan bilangan Carmichael. Jika tidak, maka bilangan tersebut merupakan bilangan prima semu berbasis a. Uji Komposit III adalah Uji Diduga Kuat Prima dengan basis a yang telah ditentukan, yaitu: 2,3,5,dan7. Input dari Uji ini adalah bilangan diduga kuat prima berbasis a. Jika uji berhasil maka m dapat dikatakan sebagai bilangan komposit. Jika tidak, maka m disebut bilangan diduga kuat prima berbasis 2,3,5dan7 yang merupakan hasil akhir dari tulisan ini. Bilangan komposit dan diduga kuat prima berbasis a disebut bilangan prima semu kuat berbasis a. Jadi bilangan komposit dari uji komposit III merupakan prima semu kuat berbasis a.