73
Contoh 2.1.5.3. (Buchmann, 2000)
Telah
diketahui
bahwa
561
adalah
bilangan
Carmichael
dan tes Fermat
gagal
untuk
membuktikan
kekompositannya.
Selanjutnya
akan
digunakan
tes Miller-Rabbin untuk
membuktikan
kekompositan
bilangan
ini.
Diambil
a
=
2,
s
=
4,
dan
r
=
35.
Dari
sini
diperoleh
2
35
=
263
(mod 561),
2
2.35
=
166
(mod 561)
,
2
4.35
=
67
(mod 561)
,
2
8.35
=
1
(mod 561)
. Jadi, terbukti bahwa 561 adalah bilangan komposit.
2.1.6. Masalah Logaritma Diskret
Misalkan
G
adalah
grup
siklik
dengan
order
n,
a
adalah
pembangun
G
dan
1
adalah
elemen
identitas
G.
Diberikan
ß
?
G
.
Permasalahan
yang
dimunculkan
adalah
bagaimana menentukan suatu bilangan bulat nonnegatif terkecil a sedemikian hingga:
ß
=
a
a
.
Bilangan bulat a seperti
ini disebut dengan logaritma diskrit (discrete logarithm) dari
ß
dengan
basis
a.
Selanjutnya,
masalah
bagaimana
menentukan
bilangan
bulat
a
seperti
ini
disebut
dengan
masalah
logaritma
diskrit
(discrete
logarithm
problem).
Masalah
logaritma
diskrit
ini
menjadi
sulit
apabila
digunakan
grup
dengan
order
yang
besar
(Buchmann, 2000).
•
Masalah Logaritma Diskret pada Grup Pergandaan Bilangan Bulat Modulo
Prima
Diberikan bilangan prima p,
menggunakan
Akibat 2.1.4.6, diperoleh bahwa
(Z
,*
)
adalah
grup siklik
yang
mempunyai order
p
-
1
. Akibatnya terdapat suatu
elemen
yang
membangun
(
Z
,*
)
yang
disebut
dengan
elemen
primitif.
Misalkan
 |