58
4
5
6
3
2
6
Selanjutnya
dihitung
6
2
0
=
6
,
6
21
=
36 ,
6
22
=
36
2
=
96
(mod100)
,
6
23
=
16
(mod100),
6
2
=
16
2
=
56
(mod100)
,
6
2
=
56
2
=
36
(mod100)
,
6
2
=
56
2
=
96
(mod100) Sehingga
. Sehingga
diperoleh:
6
73
=
(6)(6
2
)(6
)
(mod100)
=
(6)(16)(96)
(mod100)
=
16
(
mod100
)
.
Jadi,
6
73
mod100 = 16
.
Algoritma 2.6 : Metode Fast Exponentiation (Menezes, Oorschot and Vanstone,1996)
Input
:
a
?
Z
m
, m ? Z positif
dan
bilangan
bulat
k,
0
=
k
<
m
dengan
representasi
t
biner dari
k
=
?
k
2
i
.
i
=0
Output
:
a
k
mod m .
Langkah :
1. Set
b ? 1 . Jika
k
=
0
,
maka output(b).
2. Set
A
?
a
.
3. Jika
k
0
=
1, maka set
b
?
a
.
4. Untuk i dari 1 sampai t kerjakan:
4.1 Set
A
?
A
2
mod n .
4.2 Jika
k
i
=
1
,
maka set
b
?
Ab mod n
5. Output(b).
 |