48
Dari Teorema 2.1.4.5 dapat dilihat bahwa persamaan kongruen (2.7) dapat
diselesaikan
menggunakan algoritma
Euclide
yang diperluas, sebab akan diperoleh dua
hal
sekaligus
yaitu
gcd
(a, m)
=
ax + my .
gcd
(a, m)
serta
bilangan
bulat
x
dan
y
sedemikian
hingga
Menurut
Teorema
2.1.4.5,
persamaan
kongruen
(2.7)
akan
mempunyai
penyelesaian
jika
gcd
(a, m)
=
1.
Apabila
diperoleh
gcd
(a, m)
=
1,
maka
invers
a
?
Z
m
juga dapat diperoleh, yaitu
a
-1
mod
m
=
x
.
Berikut
ini
diberikan
algoritma
yang
dapat
digunakan
untuk
menghitung
invers
pergandaan
menggunakan
algoritma
Euclide
yang
diperluas
pada
himpunan
bilangan
bulat modulo m, dengan m bilangan bulat positif.
Algoritma
2.5
:
Mencari
Invers
Pergandaan
Modulo
(Menezes,
Oorschot
and
Vanstone, 1996)
Input
:
a
?
Z
m
, m bilangan bulat positif.
Output :
a
-1
mod m .
Langkah :
1. Tentukan
x, y ? Z
yang
memenuhi
ax + my =
d
dengan
d
=
gcd
(a, m)
menggunakan algoritma Euclide yang diperluas (Algoritma 2.3).
2. Jika
d
>
1
,
maka
a
-1
mod m
tidak ada. Jika tidak, output (x).
Contoh 2.1.4.4.
Akan
dihitung
35
-1
mod100 .
Dari
Contoh
2.1.2.11
diperoleh
gcd(100,35)
=
5,
x
=
-1
dan y = 3. Karena d = gcd(100,35) = 5 > 1, maka
35
-1
mod100
tidak ada.
 |