17
Contoh 2.1.2.4.
Ekspansi
dengan
basis
7
dari
125
adalah
125 = (2)(7
2
)
+
(3)(7) + 6 = (236)
7
.
Ekspansi
biner (10010011)2 = (1)(2
7
)+ (1)(2
4
)+ (1)(2¹ )+ 1 = 147.
Berikut ini diberikan sebuah algoritma yang dapat
digunakan
untuk
merepresentasikan
suatu
bilangan
bulat
ke
dalam
ekspansi
yang
diinginkan.
Algoritma
ini didasarkan pada Teorema 2.1.2.3.
Algoritma 2.1: Representasi Bilangan Bulat (Menezes, Oorschot and Vanstone, 1996)
Input
: Bilangan bulat a dan b, dengan
a
=
0,
b
=
2
.
Output : Ekspansi b-adic
a
=
(r
r
Kr r
)
,
k
=
0
dan
r
?
0
jika
k
=
1.
k k -¹
1 0
b
k
Langkah :
1.
i
?
0, x ?
a, q ?
?
x
?
,
r
?
(x - qb)
.
?
?
b
?
?
i
2. While
q
>
0
, lakukan langkah berikut: i ?
i
+
1, x ?
q, q ?
?
x
?
,
r
?
(x - qb)
.
3. Output
((r
i
r
i
-1
Kr1
r
0
))
.
D.
Pembagi Persekutuan Terbesar
?
?
b
?
?
i
Berikut ini dijelaskan pengertian dan sifat-sifat suatu bilangan yang disebut
dengan pembagi persekutuan terbesar.
Definisi 2.1.2.4. (Buchmann, 2000)
Pembagi
persekutuan
dari
bilangan
bulat
a1 , a2 ,K, a
k
adalah suatu bilangan bulat yang membagi
a1 , a2 ,K, a
k
.
 |