Home Start Back Next End
  
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.
Word to PDF Converter | Word to HTML Converter