68
p
dengan
order
dari
(Z
13
,*
)
,
yaitu
12.
Karena
elemen
yang
mempunyai
order
12
adalah
pembangun,
maka elemen
tersebut adalah elemen primitif.
Empat elemen tersebut
adalah 2, 6, 7 dan 11. Dengan demikian, elemen primitif
(Z
13
,*
)
adalah 2, 6, 7 dan 11.
2.1.5. Tes Keprimaan
Salah
satu
hal
yang
berperan
sangat
penting
dalam
algoritma
kriptografi
kunci
publik adalah kunci, semakin besar kunci
maka tingkat keamanan sistem akan
semakin
tinggi
pula. Pada algoritma ElGamal, bilangan prima digunakan sebagai salah satu
kuncinya. Untuk mendapatkan bilangan prima yang besar diperlukan suatu pembangun
kunci
yang
juga
harus
besar.
Sebelumnya
telah
diberikan
sebuah
algoritma
tes
keprimaan
(Algoritma
2.4),
akan
tetapi
algoritma
ini
sangat
tidak
efisien
untuk
mengecek bilangan yang besar.
Di sini dijelaskan dua buah tes keprimaan yang dapat digunakan
untuk bilangan
bulat positif ganjil yang besar, yaitu tes Fermat dan tes Miller-Rabbin.
A. Tes Fermat
Tes Fermat
didasarkan
pada
teorema
Fermat
(Teorema
2.1.4.13)
yang
sedikit
dirubah seperti diberikan pada Teorema 2.1.5.1 di bawah ini.
Teorema 2.1.5.1. (Buchmann, 2000) Jika
p
adalah
bilangan
prima,
maka
a
p
-1
=
1
(mod p)
, untuk sebarang
a
?
(Z
,*
). Untuk selanjutnya, a disebut dasar (base).
Bukti:
Teorema 2.1.4.13
mengatakan bahwa
untuk sebarang
a
?
(Z
m
,*
)
dan m bilangan bulat,
berlaku
a
?
(
m
)
=
1
(mod m)
.
Dari
sini
diambil
m
= p ,
dengan
p
bilangan
prima.
 |