Algoritma uji komposit berdasarkan teorema kongruensi fermat dan teorema strong pseudoprime

Abstract

Dalam menentukan apakah suatu bilangan bulat positif ganjil m merupakan bilangan komposit atau bukan, diperlukan suatu uji. Uji tersebut dinamakan uji komposit. Uji Komposit I 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 anggota 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 ditentukan kekompositannya menggunakan Uji Komposit II, yaitu bilangan diduga prima berbasis a. Jika uji berhasil maka m merupakan bilangan komposit dan disebut bilangan prima semu berbasis a. Jika tidak, maka m dikatakan bilangan diduga kuat prima berbasis a.