72
Jika
k
>
1
, maka
k
=
2
l
dengan
1
=
l
=
s
. Menggunakan Teorema 2.1.4.11,
l
-1
a
(
d
)
mempunyai order 2. Karena
p
-
1
mempunyai order 2, hal ini berakibat
a
2 (
d
)
=
p - 1
(mod p
)
untuk
r
=
l - 1
dan
0
=
r
=
s
.
Algoritma 2.8 : Tes Miller-Rabbin (Menezes, Oorschot and Vanstone, 1996)
Input
: Sebuah bilangan bulat positif ganjil
p
=
3
dan sebuah parameter
t
=
1
.
Output : Pernyataan “prima” atau “komposit”.
Langkah :
1. Tulis
p
-
1
=
2
s
(r ) , dengan r bilangan bulat positif ganjil.
2. Untuk i dari 1 sampai t kerjakan:
2.1. Diambil sebarang bilangan bulat positif a,
2
=
a
=
p - 1
.
2.2. Hitung
y
=
a
r
(mod p)
menggunakan metode fast exponentiation.
2.3. Jika
y
?
1
dan
y
?
p - 1 kerjakan:
2.3.1. Set
j
?
1.
2.3.2. While
j
=
s
-
1
dan
y
?
p - 1 kerjakan:
2.3.2.1. Set
y
?
y
2
mod p .
2.3.2.2. Jika
y
=
1
,
maka output(“komposit”).
2.3.2.3. Set 1, maka output(“komposit”).
j
?
j + 1 .
2.3.3. Jika
y
?
p - 1, maka output(“komposit”).
3. Output (“prima”).
 |