71
p
p
p
C. Tes Miller-Rabbin
Tes
Miller-Rabbin
merupakan penyempurnaan dari tes
Fermat. Pada
tes
keprimaan
ini,
kelemahan
yang
terdapat
dalam tes
Fermat
telah
dapat
dihilangkan.
Tes
Miller-Rabbin didasarkan pada teorema di bawah ini.
Teorema 2.1.5.2. (Buchmann, 2000) Diberikan sebarang bilangan bulat positif
ganjil
p
=
3
.
Diambil
bilangan
bulat
s
menjadi
pangkat
terbesar
sedemikian
hingga
2
s
membagi p – 1, yaitu:
s
=
max
{r ? N
:
2
r
(
p
-
1
)
membagi
p
-
1
}.
Kemudian
dihitung
d
=
.
Jika
p
adalah
bilangan
prima,
maka
untuk
sebarang
2
s
a
?
(Z
,*
)
berlaku:
a
d
=
1
(mod p
)
atau terdapat
r
?
{0,1,2,K, s - 1} sedemikian hingga
a
2 (
d
)
=
p - 1
(mod p
)
.
Bukti:
Diberikan sebarang bilangan bulat positif ganjil
p
=
3
dan
a
?
(Z
,*
). Diambil bilangan
bulat
s
=
max
{r ? N
:
2
r
membagi
p
-
1
}. Selanjutnya, dihitung
(
p
-
1
)
d
=
.
Misalkan p
2
s
adalah
bilangan
prima,
maka
order
dari
(Z
,*
)
adalah
p
-
1
=
2
s
(d ) .
Menggunakan
Teorema 2.1.4.11, jika k adalah order dari
a
d
,
maka k merupakan suatu pangkat dari 2.
Jika
k
=
1
=
2
0
,
maka:
a
d
=
1
(mod p
)
.
 |