57
i
k
i
2
Berikut
ini
dijelaskan
suatu
metode
yang
dapat
digunakan
untuk
menghitung
secara cepat pangkat bilangan bulat khususnya untuk bilangan bulat yang besar.
G.
Metode Fast Exponentiation
Diberikan
sebarang
grup
G,
g
?
G
dan
bilangan
bulat
positif
z.
Untuk
menghitung
g
z
dilakukan langkah berikut ini.
Dibentuk ekspansi biner dari bilangan bulat z, yaitu
k
z
=
?
i
=
(a
)(2
i
)
.
0
Karena z ditulis dalam ekspansi biner, maka
a
i
?
{0,1}. Sehingga,
k
?
g
z
=
g
=
(
a
i
)(
2
i
)
=
?
(g
2
i
)
a
i
=
?
g
2
.
i 0
i
=0
1=i= k , a
i
=1
Dengan
hasil
ini
diperoleh
cara
yang cepat
untuk
menghitung g
z
yang disebut dengan
metode fast exponentiation, yaitu:
1)
Hitung nilai
g
2
,
0
=
i
=
k
.
2)
Nilai g
z
merupakan
hasil
dari
perkalian
nilai-nilai
g
2
,
dengan
a
i
=
1.
Diperoleh bahwa:
i 1
+1
g
=
(g
2
i
)
2
.
Contoh 2.1.4.8. (Buchmann, 2000)
Akan dihitung nilai dari
6
73
mod100 . Pertama, ditentukan ekspansi biner dari 73:
73 = (1)(2
6
)
+
(1)(2³) + (1)(2
0
)
atau
(1001001)
2
.
 |