26
Algoritma 2.3 : Algoritma Euclide yang Diperluas (Menezes, Oorschot and Vanstone,
1996)
Input
:
a, b ? Z ,
a
=
b
.
Output :
d
=
gcd
(a, b)
dan
x, y ? Z
yang memenuhi
ax + by =
d
.
Langkah :
1. Jika b = 0, maka set
d
?
a
,
x
?
1,
y
?
0
, output (d, x, y).
2. Set
x2 ?
1
,
x1 ?
0
,
y2 ?
0
,
y1 ?
1
.
3. While
b
>
0
:
q
?
?
a
?
,
r
?
a
-
qb ,
?
?
b
?
?
x
?
x2
-
qx1 ,
y
?
y
2
-
qy1
a
?
b
,
b ?
r
,
x2 ? x1 ,
x1 ? x ,
y2 ? y1
,
y1 ? y
4. Set
d
?
a
,
x
?
x2 ,
y
?
y
2
, output (d, x, y).
Contoh 2.1.2.11. (Buchmann, 2000)
Seperti
pada
Contoh
2.1.2.9
diperoleh
gcd
(100,35)
=
(-1)(100) + (3)(35) = 5 ,
bilangan
bulat
x
=
(-1)
dan
y
=
3.
Menggunakan
Algoritma
2.3,
diperoleh
hasil
perhitungan
seperti pada tabel di bawah ini.
Tabel 2.3. Perhitungan menggunakan algoritma Euclide yang diperluas
Dan ternyata diperoleh hasil yang sama seperti pada Contoh 2.1.2.10.
 |