70
p
y
=
1
,
ternyata p bukan bilangan prima. Untuk
menunjukkan bahwa p benar
merupakan
bilangan komposit dilakukan
tes Fermat sekali
lagi. Selanjutnya diambil a = 3, dengan
tes
Fermat
diperoleh
3
340
=
56
(mod 341)
yang
benar
menunjukkan
bahwa
341
adalah
bilangan komposit.
Contoh
di
atas
memperlihatkan
bahwa
pemgambilan
dasar
a
?
(Z
,*
)
sangat
mempengaruhi
hasil akhir perhitungan. Ini menjadi salah satu kelemahan dari tes
Fermat. Kelemahan
lain
dari
tes Fermat
adalah
gagal
saat
harus
mendeteksi
kekompositan suatu bilangan tertentu yang dinamakan bilangan Carmichael.
B. Bilangan Carmichael
Bilangan
Carmichael
adalah
bilangan
bulat
positif komposit
yang
tidak
dapat
dibuktikan
kekompositannya
menggunakan
tes
Fermat,
untuk
semua
dasar
yang
diambil.
Definisi 2.1.5.1. (Buchmann, 2000)
Diberikan sebarang bilangan bulat positif komposit
n.
Jika
untuk
setiap
a
?
Z
berlaku
a
n-¹
=
1
(mod n), maka
n
disebut
pseudoprime
ke
dasar
a.
Jika
n
pseudoprime
ke
semua
dasar
a
dengan
gcd
(a, n)
=
1
,
maka
p
disebut
bilangan Carmichael.
Contoh 2.1.5.2. (Buchmann, 2000)
Bilangan 561 = (3)(11)(17) merupakan bilangan Carmichael (yang paling kecil).
Ditemukannya
bilangan Carmichael
ini
membuat
tes
Fermat tidak
lagi
optimal
untuk digunakan sebagai tes keprimaan. Berikut dijelaskan mengenai tes Miller-Rabbin,
yaitu sebuah tes keprimaan yang menggantikan tes Fermat.
 |