31
lapangan. Konsep
ini penting, karena pada pembahasan selanjutnya
mengenai algoritma
ElGamal, perhitungan-perhitungannya dilakukan di dalam suatu struktur aljabar.
A. Partisi dan Relasi Ekuivalensi
Berikut ini dijelaskan tentang partisi, relasi ekuivalensi dan klas ekuivalensi pada
suatu himpunan.
Definisi 2.1.3.1. (Fraleigh, 2000)
Suatu
partisi
pada
himpunan
tak
kosong
S
adalah
suatu dekomposisi S ke dalam subset-subset
yang saling asing sedemikian
hingga
setiap
elemen dari S berada pada tepat satu subset. Subset yang demikian ini dinamakan cell.
Definisi 2.1.3.2. (Fraleigh, 2000)
Diberikan
himpunan
tak
kosong
S
dan
~
adalah
relasi
antar
elemen-elemen
S.
Relasi
~
disebut
relasi
ekuivalensi
jika
memenuhi
sifat-
sifat berikut. Untuk setiap
a, b, c ? S
1. Refleksif, yaitu a ~ a,
2. Simetris, yaitu jika a ~ b, maka b ~ a,
3. Transitif, yaitu jika a ~ b dan b ~ c, maka a ~ c.
Dengan adanya suatu relasi ekuivalensi pada S, maka dapat ditentukan suatu partisi pada
S. Partisi
ini
mendekomposisi S
menjadi cell-cell. Cell
yang
memuat
a
?
S
dilambangkan dengan
a
=
{x
?
S
:
x
~
a
}. Cell seperti
ini disebut dengan klas
ekuivalensi yang memuat a.
B.
Grup
Grup
merupakan
suatu
himpunan
tak
kosong
yang
dilengkapi
dengan
operasi
biner dan memenuhi beberapa sifat, seperti dijelaskan berikut ini.
 |