* Teori Bilangan
* Bahan Kuliah IF2091 Struktur Diskrit
* Bilangan Bulat
* Bilangan bulat adalah bilangan yang tidak mempunyai pecahan desimal, misalnya 8, 21, 8765, -34, 0
* Berlawanan dengan bilangan bulat adalah bilangan riil yang mempunyai titik desimal, seperti 8.0, 34.25, 0.02.
* Sifat Pembagian pada Bilangan Bulat
* Misalkan adan b bilangan bulat, a ¹ 0.
a habis membagi b (a divides b) jika terdapat bilangan bulat c sedemikian sehingga b = ac.
* Notasi: a| b jika b = ac, cÎ Z dan a ¹ 0.
* Contoh 1: 4 | 12 karena 12/4 = 3 (bilangan bulat) atau 12 = 4 ´ 3. Tetapi 4 | 13 karena 13/4 = 3.25 (bukan bilangan bulat).
* Teorema Euclidean
Teorema 1 (Teorema Euclidean). Misalkan mdan n bilangan bulat, n > 0. Jika m dibagi dengan nmaka terdapat bilangan bulat unik q (quotient) dan r (remainder), sedemikian sehingga
m = nq + r (1)
dengan 0 £ r < n.
Contoh 2.
(i) 1987/97 = 20, sisa 47:
1987 = 97 × 20 + 47
(ii) –22/3 = –8, sisa 2:
–22 = 3(–8) + 2
tetapi –22 = 3(–7) – 1 salah
karena r= –1 (syarat 0 £ r < n)
* Pembagi Bersama Terbesar (PBB)
* Misalkan adan b bilangan bulat tidak nol.
* Pembagi bersama terbesar (PBB – greatest common divisor atau gcd) dari a dan b adalah bilangan bulat terbesar d sedemikian hingga d | a dan d | b.
* Dalam hal ini kita nyatakan bahwa PBB(a, b) = d.
* Contoh 3.
Faktor pembagi 45: 1, 3, 5, 9, 15, 45;
Faktor pembagi 36: 1, 2, 3, 4, 9, 12, 18, 36;
Faktor pembagi bersama 45 dan 36: 1, 3, 9
à PBB(45, 36) = 9.
* Teorema 2. Misalkan m dan n bilangan bulat, dengan syarat n > 0 sedemikian sehingga
m = nq + r , 0 £ r < n
maka PBB(m, n) = PBB(n, r)
* Contoh 4: m = 60, n = 18,
60 = 18 × 3 + 6
maka PBB(60, 18) = PBB(18, 6) = 6
* Algoritma Euclidean
* Tujuan: algoritma untuk mencari PBB dari dua buah bilangan bulat.
* Penemu: Euclides, seorang matematikawan Yunani yang menuliskan algoritmanya tersebut dalam buku, Element.
* Lukisan Euclides versi lain
* Kombinasi Lanjar
* PBB(a,b) dapat dinyatakan sebagai kombinasi lanjar (linear combination) adan b dengan dengan koefisien-koefisennya.
* Contoh 6: PBB(80, 12) = 4 ,
4 = (-1) × 80 + 7 × 12.
* Teorema 3. Misalkan a dan b bilangan bulat positif, maka terdapat bilangan bulat m dan n sedemikian sehingga PBB(a, b) = ma + nb.
* Contoh 7: Nyatakan PBB(21, 45) sebagai kombinasi lanjar dari 21 dan 45.
* Solusi:
45 = 2 (21) + 3
21 = 7 (3) + 0
Sisa pembagian terakhir sebelum 0 adalah 3, maka PBB(45, 21) = 3
Substitusi dengan persamaan–persamaan di atas menghasilkan:
3 = 45 – 2 (21)
yang merupakan kombinasi lanjar dari 45 dan 21
Contoh 8: Nyatakan PBB(312, 70) sebagai kombinasi lanjar 312 dan 70.
Solusi: Terapkan algoritma Euclidean untuk memperoleh PBB(312, 70):
312 = 4 × 70 + 32 (i)
70 = 2 × 32 + 6 (ii)
32 = 5 × 6 + 2 (iii)
6 = 3 × 2 + 0 (iv)
Sisa pembagian terakhir sebelum 0 adalah 2, maka PBB(312, 70) = 2
Susun pembagian nomor (iii) dan (ii) masing-masing menjadi
2 = 32 – 5 × 6 (iv)
6 = 70 – 2 × 32 (v)
Sulihkan (v) ke dalam (iv) menjadi
2 = 32 – 5×(70 – 2×32) = 1×32 – 5×70 + 10×32 = 11 × 32 – 5 × 70 (vi)
Susun pembagian nomor (i) menjadi
32 = 312 – 4 × 70 (vii)
Sulihkan (vii) ke dalam (vi) menjadi
2 = 11 × 32 – 5 × 70 = 11 × (312 – 4 × 70) – 5 × 70 = 11 . 312 – 49 × 70
Jadi, PBB(312, 70) = 2 = 11 × 312 – 49 × 70
* Relatif Prima
* Dua buah bilangan bulat a dan b dikatakan relatif prima jika PBB(a, b) = 1.
* Contoh 9.
(i) 20 dan 3 relatif prima sebab PBB(20, 3) = 1.
(ii) 7 dan 11 relatif prima karena PBB(7, 11) = 1.
(iii) 20 dan 5 tidak relatif prima sebab PBB(20, 5) = 5 ¹ 1.
* Jika adan b relatif prima, maka terdapat bilangan bulat m dan nsedemikian sehingga
ma + nb = 1
* Contoh 10. Bilangan 20 dan 3 adalah relatif prima karena PBB(20, 3) =1, atau dapat ditulis
2 . 20 + (–13) . 3 = 1 (m = 2, n= –13)
Tetapi 20 dan 5 tidak relatif prima karena PBB(20, 5) = 5 ¹ 1 sehingga 20 dan 5 tidak dapat dinyatakan dalam m. 20 + n . 5 = 1.
* Aritmetika Modulo
* Misalkan adan m bilangan bulat (m > 0). Operasi
a mod m (dibaca “a modulo m”)
memberikan sisa jika a dibagi dengan m.
* Notasi: a mod m = r sedemikian sehingga
a = mq + r, dengan 0 £ r < m.
* m disebut modulus atau modulo, dan hasil aritmetika modulo m terletak di dalam himpunan {0, 1, 2, …, m – 1}.
* Contoh 11. Beberapa hasil operasi dengan operator modulo:
(i) 23 mod 5 = 3 (23 = 5 × 4 + 3)
(ii) 27 mod 3 = 0 (27 = 3 × 9 + 0)
(iii) 6 mod 8 = 6 (6 = 8 × 0 + 6)
(iv) 0 mod 12 = 0 (0 = 12 × 0 + 0)
(v) – 41 mod 9 = 4 (–41 = 9 (–5) + 4)
(vi) – 39 mod 13 = 0 (–39 = 13(–3) + 0)
* Penjelasan untuk (v): Karena a negatif, bagi |a| dengan mmendapatkan sisa r’. Maka a mod m = m – r’ bila r’ ¹ 0. Jadi |– 41| mod 9 = 5, sehingga –41 mod 9 = 9 – 5 = 4.
* Kongruen
* Misalnya 38 mod 5 = 3 dan 13 mod 5 = 3, maka dikatakan 38 º 13 (mod 5)
(baca: 38 kongruen dengan 13 dalam modulo 5).
* Misalkan adan b bilangan bulat dan m adalah bilangan > 0, maka aº b (mod m) jika mhabis membagi a – b.
* Jika atidak kongruen dengan b dalam modulus m, maka ditulis a º/ b (mod m) .
* Contoh 12.
17 º 2 (mod 3) ( 3 habis membagi 17 – 2 = 15)
–7 º 15 (mod 11)
(11 habis membagi –7 – 15 = –22)
12 º/ 2 (mod 7)
(7 tidak habis membagi 12 – 2 = 10 )
–7 º/ 15 (mod 3)
(3 tidak habis membagi –7 – 15 = –22)
* a º b (mod m) dalam bentuk “sama dengan” dapat dituliskan sebagai
a = b + km (k adalah bilangan bulat)
* Contoh 13.
17 º 2 (mod 3) è 17 = 2 + 5 × 3
–7 º 15 (mod 11) è –7 = 15 + (–2)11
* a mod m = r dapat juga ditulis sebagai
aº r (mod m)
* Contoh 14.
(i) 23 mod 5 = 3 è 23 º 3 (mod 5)
(ii) 27 mod 3 = 0 è 27 º 0 (mod 3)
(iii) 6 mod 8 = 6 è 6 º 6 (mod 8)
(iv) 0 mod 12 = 0 è 0 º 0 (mod 12)
(v) – 41 mod 9 = 4 è –41 º 4 (mod 9)
(vi) – 39 mod 13 = 0 è – 39 º 0 (mod 13)
Teorema 4. Misalkan m adalah bilangan bulat
positif.
1)Jika a º b (mod m) dan c adalah sembarang bilangan bulat maka
(i) (a + c) º (b + c) (mod m)
(ii) acº bc (mod m)
(iii) apº bp (mod m) , p bilangan bulat tak-negatif
2) Jika a º b (mod m) dan c º d (mod m), maka
(i) (a + c) º (b + d) (mod m)
(ii) acº bd (mod m)
Contoh 15.
Misalkan 17 º 2 (mod 3) dan 10 º 4 (mod 3), maka menurut Teorema 4,
17 + 5 = 2 + 5 (mod 3) Û 22 = 7 (mod 3)
17 . 5 = 5 × 2 (mod 3) Û 85 = 10 (mod 3)
17 + 10 = 2 + 4 (mod 3) Û 27 = 6 (mod 3)
17 . 10 = 2 × 4 (mod 3) Û 170 = 8 (mod 3)
* Teorema 4 tidak memasukkan operasi pembagian pada aritmetika modulo karena jika kedua ruas dibagi dengan bilangan bulat, maka kekongruenan tidak selalu dipenuhi.
* Contoh 16:
10 º 4 (mod 3) dapat dibagi dengan 2
karena 10/2 = 5 dan 4/2 = 2, dan 5 º 2 (mod 3)
14 º 8 (mod 6) tidak dapat dibagi dengan 2, karena 14/2 = 7 dan 8/2 = 4, tetapi 7 º/ 4 (mod 6).
* Latihan
Jika aº b (mod m) dan c º d (mod m) adalah sembarang bilangan bulat maka buktikan bahwa
acº bd (mod m)
.
* Solusi
a º b (mod m) à a = b + k1m
c º d (mod m) à c = d + k2m
maka
Û ac = (b + k1m)(d + k2m)
Û ac = bd + bk2m + dk1m + k1k2m2
Û ac = bd + Km dengan K = bk2 + dk1 + k1k2m
Û acº bd (mod m) (terbukti)
* Balikan Modulo (modulo invers)
* Di dalam aritmetika bilangan riil, inversi (inverse) dari perkalian adakah pembagian.
* Contoh: Inversi 4 adalah 1/4, sebab 4 ´ 1/4 = 1.
* Di dalam aritmetika modulo, masalah menghitung inversi modulo lebih sukar.
* Jika adan m relatif prima dan m > 1, maka balikan (invers) dari a (mod m) ada.
* Balikan dari a(mod m) adalah bilangan bulat xsedemikian sehingga
xaº 1 (mod m)
* Dalam notasi lainnya, a–1(mod m) = x
Bukti: a dan m relatif prima, jadi PBB(a, m) = 1, dan terdapat bilangan bulat x dan y sedemikian sehingga:
xa+ ym = 1
yang mengimplikasikan bahwa
xa+ ym º 1 (mod m)
Karena ymº 0 (mod m) (kenapa?), maka
xaº 1 (mod m)
Kekongruenan yang terakhir ini berarti bahwa x adalah balikan dari a (mod m). ¾
* Pembuktian di atas juga menceritakan bahwa untuk mencari balikan dari a (mod m), kita harus membuat kombinasi lanjar dari a dan m sama dengan 1.
* Koefisien adari kombinasi lanjar tersebut merupakan balikan dari a (mod m).
* Contoh 17. Tentukan balikan dari 4 (mod 9), 17 (mod 7), dan 18 (mod 10).
Solusi:
* (a) Karena PBB(4, 9) = 1, maka balikan dari 4 (mod 9) ada. Dari algoritma Euclidean diperoleh bahwa
9 = 2 × 4 + 1
Susun persamaan di atas menjadi
–2 × 4 + 1 × 9 = 1
Dari persamaan terakhir ini kita peroleh –2 adalah balikan dari 4 (mod 9).
Periksa bahwa –2 × 4 º 1 (mod 9)
* Catatan: setiap bilangan yang kongruen dengan
–2 (mod 9)
juga adalah inversi dari 4, misalnya 7, –11, 16, dan seterusnya, karena
7 º –2 (mod 9) (9 habis membagi 7 – (–2) = 9)
–11 º –2 (mod 9) (9 habis membagi –11 – (–2) = –9)
16 º –2 (mod 9) (9 habis membagi 16 – (–2) = 18)
* (b) Karena PBB(17, 7) = 1, maka balikan dari 17 (mod 7) ada. Dari algoritma Euclidean diperoleh rangkaian pembagian berikut:
17 = 2 × 7 + 3 (i)
7 = 2 × 3 + 1 (ii)
3 = 3 × 1 + 0 (iii) (yang berarti: PBB(17, 7) = 1) )
Susun (ii) menjadi:
1 = 7 – 2 × 3 (iv)
Susun (i) menjadi
3 = 17 – 2 × 7 (v)
Sulihkan (v) ke dalam (iv):
1 = 7 – 2 × (17 – 2 × 7) = 1 × 7 – 2 × 17 + 4 × 7 = 5 × 7 – 2 × 17
atau
–2 × 17 + 5 × 7 = 1
Dari persamaan terakhir diperoleh –2 adalah balikan dari 17 (mod 7)
* –2 × 17 º 1 (mod 7) (7 habis membagi –2 × 17 – 1 = –35)
(c) Karena PBB(18, 10) = 2 ¹ 1, maka balikan dari
18 (mod 10) tidak ada.
* Cara lain menghitung balikan
* Ditanya: balikan dari a (mod m)
* Misalkan xadalah balikan dari a (mod m), maka
ax º 1 (mod m) (definisi balikan modulo)
atau dalam notasi ‘sama dengan’:
ax = 1 + km
atau
x = (1 + km)/a
Cobakan untuk k = 0, 1, 2, … dan k = -1, -2, …
Solusinya adalah semua bilangan bulat yang memenuhi.
* Contoh 18: Balikan dari 4 (mod 9) adalah x sedemikian sehingga 4x º 1 (mod 9)
4x º 1 (mod 9) à 4x = 1 + 9k à x = (1 + 9k)/4
Untuk k = 0 à x tidak bulat
k = 1 x tidak bulat
k = 2 x tidak bulat
k= 3 x = (1 + 9 . 3)/4 = 7
k = -1 x = (1 + 9. –1)/4 = -2
Balikan dari 4 (mod 9) adalah 7 (mod 9),
-2 (mod 9), dst
* Latihan
* Tentukan semua balikan dari 9 (mod 11).
* Solusi:
* Misalkan 9-1(mod 11) = x
* Maka 9x º 1 (mod 11) atau 9x = 1 + 11k atau
x = (1 + 11k)/9
Dengan mencoba semua nilai k yang bulat (k = 0, -1, -2, ..., 1, 2, ...) maka
* diperoleh x= 5. Semua bilangan lain yang kongruen dengan 5 (mod 11) juga merupakan solusi, yaitu –6, 16, 27, ...
* Kekongruenan Lanjar
* Kekongruenan lanjar berbentuk:
ax º b (mod m)
(m> 0, a dan b sembarang bilangan bulat, dan x adalah peubah bilangan bulat).
Pemecahan: ax = b + km è
(Cobakan untuk k = 0, 1, 2, … dan k = –1, –2, … yang menghasilkan xsebagai bilangan bulat)
* Cara lain menghitung solusi
ax º b (mod m)
ax º b (mod m)
* Seperti dalam persamaan biasa,
4x = 12 à kalikan setiap ruas dengan 1/4 (yaitu invers 4), maka 1/4 . 4x = 12 . 1/4 x = 3
* 4x º 3 (mod 9) à kalikan setiap ruas dengan balikan dari
4 (mod 9) (dalam hal ini sudah kita hitung, yaitu –2)
(-2) . 4x º (-2) . 3 (mod 9) -8x -6 (mod 9)
Karena –8 1 (mod 9), maka x -6 (mod 9). Semua blangan bulat yang kongruen dengan –6 (mod 9) adalah solusinya, yitu 3, 12, …, dan –6, -15, …
* Latihan
* Sebuah bilangan bulat jika dibagi dengan 3 bersisa 2 dan jika ia dibagi dengan 5 bersisa 3. Berapakah bilangan bulat tersebut
* Solusi
Misal : bilangan bulat = x
x mod 3 = 2 à x º 2 (mod 3)
x mod 5 = 3 à x º 3 (mod 5)
Jadi, terdapat sistem kekongruenan:
x º 2 (mod 3) (i)
x º 3 (mod 5) (ii)
Untuk kongruen pertama:
x = 2 + 3k1 (iii)
Substitusikan (iii) ke dalam (ii):
2 + 3k1 º 3 (mod 5) à 3k1 º 1 (mod 5)
diperoleh
k1 º 2 (mod 5) atau k1 = 2 + 5k2
x = 2 + 3k1
= 2 + 3 (2 + 5k2)
= 2 + 6 + 15k2
= 8 + 15k2
atau
x º 8 (mod 15)
Semua nilai xyang kongruen dengan 8 (mod 15) adalah solusinya, yaitu
x = 8, x = 23, x = 38, …, x = -7, dst
* Chinese Remainder Problem
* Pada abad pertama, seorang matematikawan China yang bernama Sun Tse mengajukan pertanyaan sebagai berikut:
Tentukan sebuah bilangan bulat yang bila dibagi dengan 5 menyisakan 3, bila dibagi 7 menyisakan 5, dan bila dibagi 11 menyisakan 7.
* Misakan bilangan bulat tersebut = x. Formulasikan kedalam sistem kongruen lanjar:
xº 3 (mod 5)
xº 5 (mod 7)
xº 7 (mod 11)
Teorema 5. (Chinese Remainder Theorem) Misalkan m1, m2, …, mnadalah bilangan bulat positif sedemikian sehingga PBB(mi, mj) = 1 untuk i ¹ j. Maka sistem kongruen lanjar
xº ak (mod mk)
mempunyai sebuah solusi unik dalam modulo m = m1 × m2 × … × mn.
* Solusi unik ini mudah dibuktikan sebagai berikut. Solusi tersebut dalam modulo:
m = m1 × m2 × m3 = 5 × 7 × 11 = 5 × 77 = 11 × 35.
Karena 77 . 3 º 1 (mod 5),
55 × 6 º 1 (mod 7),
35 × 6 º 1 (mod 11),
maka solusi unik dari sistem kongruen tersebut adalah
xº 3 × 77 × 3 + 5 × 55 × 6 + 7 × 35 × 6 (mod 385)
º 3813 (mod 385)
348 (mod 385)
* Bilangan Prima
* Bilangan bulat positif p (p > 1) disebut bilangan prima jika pembaginya hanya 1 dan p.
* Contoh: 23 adalah bilangan prima karena ia hanya habis dibagi oleh 1 dan 23.
* Karena bilangan prima harus lebih besar dari 1, maka barisan bilangan prima dimulai dari 2, yaitu 2, 3, 5, 7, 11, 13, ….
* Seluruh bilangan prima adalah bilangan ganjil, kecuali 2 yang merupakan bilangan genap.
* Bilangan selain prima disebut bilangan komposit (composite). Misalnya 20 adalah bilangan komposit karena 20 dapat dibagi oleh 2, 4, 5, dan 10, selain 1 dan 20 sendiri.
Teorema 6. (The Fundamental Theorem of Arithmetic). Setiap bilangan bulat positif yang lebih besar atau sama dengan 2 dapat dinyatakan sebagai perkalian satu atau lebih bilangan prima.
Contoh 16.
9 = 3 ´ 3
100 = 2 ´ 2 ´ 5 ´ 5
13 = 13 (atau 1 ´ 13)
* Tes bilangan prima:
(i) bagi n dengan sejumlah bilangan prima, mulai dari 2, 3, … , bilangan prima £ Ön.
(ii) Jika n habis dibagi dengan salah satu dari bilangan prima tersebut, maka n adalah bilangan komposit,
(ii) tetapi jika n tidak habis dibagi oleh semua bilangan prima tersebut, maka n adalah bilangan prima.
* Contoh 17. Tes apakah (i) 171 dan (ii) 199 merupakan bilangan prima atau komposit.
Penyelesaian:
(i) Ö171 = 13.077. Bilangan prima yang £ Ö171 adalah 2, 3, 5, 7, 11, 13.
Karena 171 habis dibagi 3, maka 171 adalah bilangan komposit.
(ii) Ö199 = 14.107. Bilangan prima yang £ Ö199 adalah 2, 3, 5, 7, 11, 13.
Karena 199 tidak habis dibagi 2, 3, 5, 7, 11, dan 13, maka 199 adalah bilangan prima.
* Teorema 6 (Teorema Fermat). Jika p adalah bilangan prima dan a adalah bilangan bulat yang tidak habis dibagi dengan p, yaitu PBB(a, p) = 1, maka
ap–1º 1 (mod p)
Contoh 18. Tes apakah 17 dan 21 bilangan prima atau bukan dengan Teorema Fermat
Ambil a= 2 karena PBB(17, 2) = 1 dan PBB(21, 2) = 1.
(i) 217–1= 65536 º 1 (mod 17)
karena 17 habis membagi 65536 – 1 = 65535
Jadi, 17 prima.
(ii) 221–1 =1048576 º\ 1 (mod 21)
karena 21 tidak habis membagi 1048576 – 1 =
1048575.
Jadi, 21 bukan prima
* Kelemahan Teorema Fermat: terdapat bilangan komposit n sedemikian sehingga 2n–1º 1 (mod n). Bilangan bulat seperti itu disebut bilangan prima semu (pseudoprimes).
* Contoh: 341 adalah komposit (karena 341 = 11 × 31) sekaligus bilangan prima semu, karena menurut teorema Fermat,
2340º 1 (mod 341)
* Untunglah bilangan prima semu relatif jarang terdapat.
* Untuk bilangan bulat yang lebih kecil dari 1010 terdapat 455.052.512 bilangan prima, tapi hanya 14.884 buah yang merupakan bilangan prima semu terhadap basis 2.
* Aplikasi Teori Bilangan
* ISBN (International Book Serial Number)
* Fungsi hash
* Kriptografi
* Pembangkit bilangan acak-semu
* dll
* ISBN
* Kode ISBN terdiri dari 10 karakter, biasanya dikelompokkan dengan spasi atau garis, misalnya 0–3015–4561–9.
* ISBN terdiri atas empat bagian kode:
- kode yang mengidentifikasikan bahasa,
- kode penerbit,
- kode unik untuk buku tersebut,
- karakter uji (angka atau huruf X (=10)).
* Karakter uji dipilih sedemikian sehingga
* Karakter uji
* Contoh: ISBN 0–3015–4561–8
0 : kode kelompok negara berbahasa Inggris,
3015 : kode penerbit
4561 : kode unik buku yang diterbitkan
8 : karakter uji.
Karakter uji ini didapatkan sebagai berikut:
1 × 0 + 2 × 3 + 3 × 0 + 4 × 1 + 5 × 5 + 6 × 4 +
7 × 5 + 8 × 6 + 9 × 1 = 151
* Jadi, karakter ujinya adalah 151 mod 11 = 8.
* Fungsi Hash
* Tujuan: pengalamatan di memoriuntuk tujuan pengaksesan data dengan cepat.
* Bentuk: h(K) = K mod m
- m : jumlah lokasi memori yang tersedia
- K : kunci (integer)
- h(K) : lokasi memori untuk record dengan
kunci unik K
* Kolisi (collision) terjadi jika fungsi hash menghasilkan nilai h yang sama untuk K yang berbeda.
* Jika terjadi kolisi, cek elemen berikutnya yang kosong.
Contoh: K = 71 à h(71) = 74 mod 11 = 8
Oleh karena elemen pada indeks 8 sudah berisi 558, maka
74 ditaruh pada elemen kosong berikutnya: 9
* Fungsi hashjuga digunakan untuk me-locate elemen yang dicari.
* Kriptografi
* Dari Bahasa Yunani yang artinya “secret writing”
* Kriptografi adalah ilmu dan seni untuk menjaga keamanan pesan dengan cara menyandikannya menjadi bentuk lain yang tidak bermakna.
* Tujuan: agar pesan yang bersifat rahasia tidak dapat dibaca oleh pihak yang tidak berhak.
* Pesan: data atau informasi yang dapat dibaca dan dimengerti maknanya. Nama lain: plainteks (plaintext)
* Cipherteks (ciphertext): pesan yang telah disandikan sehingga tidak memiliki makna lagi.
Contoh:
Plainteks: culik anak itu jam 11 siang
Cipherteks: t^$gfUi9rewoFpfdWqL:[uTcxZy
* Enkripsi (encryption): proses menyandikan plainteks menjadi cipherteks.
* Dekripsi (decryption): Proses mengembalikan cipherteks menjadi plainteksnya.
* Aplikasi Enkripsi-Dekripsi
• Pengiriman data melalui saluran komunikasi (data encryption on motion).
à pesan dikirim dalam bentuk cipherteks
• Penyimpanan data di dalam disk storage
(data encryption at rest)
à data disimpan di dalam memori dalam bentuk cipherteks
* Data ditransmisikan dalam bentuk chiperteks. Di tempat penerima chiperteks dikembalikan lagi menjadi plainteks.
* Data di dalam media penyimpanan komputer (seperti hard disk) disimpan dalam bentuk chiperteks. Untuk membacanya, hanya orang yang berhak yang dapat mengembalikan chiperteks menjadi plainteks.
* Contoh enkripsi pada dokumen
* Caesar Cipher
* Algoritma enkripsi sederhana pada masa raja Julius Caesar
* Tiap huruf alfabet digeser 3 huruf ke kanan secara wrapping
Contoh: Plainteks: AWASI ASTERIX DAN TEMANNYA OBELIX
Cipherteks: DZDVL DVWHULA GDQ WHPDQQBA REHOLA
* Misalkan setiap huruf dikodekan dengan angka:
* A = 0, B = 1, C = 2, …, Z = 25
maka secara matematis enkripsi dan dekripsi pada Caesar cipher dirumuskan sebagai berikut:
Enkripsi: ci = E(pi) = (pi + 3) mod 26
Dekripsi: pi = D(ci) = (ci – 3) mod 26
Contoh:
Plainteks: AWASI ASTERIX DAN TEMANNYA OBELIX
Cipherteks: DZDVL DVWHULA GDQ WHPDQQBA REHOLA
p1 = ‘A’ = 0 à c1 = E(0) = (0 + 3) mod 26 = 3 = ‘D’
p2 = ‘W’ = 22 à c2 = E(22) = (22 + 3) mod 26 = 25 = ‘Z’
p3 = ‘A’ = 0 à c3 = E(0) = (0 + 3) mod 26 = 3 = ‘D’
p4 = ‘S’ = 18 à c4 = E(18) = (18 + 3) mod 26 = 21 = ‘V’
dst…
* Jika pergeseran huruf sejauh k, maka:
Enkripsi: ci = E(pi) = (pi + k) mod 26
Dekripsi: pi = D(ci) = (ci – k) mod 26
k = kunci rahasia
• Pada Caesar Cipher, k = 3
• Untuk alfabet ASCII 256 karakter,
Enkripsi: ci = E(pi) = (pi + k) mod 256
Dekripsi: pi = D(ci) = (ci – k) mod 256
* Algoritma RSA
* Dibuat oleh tiga peneliti dari MIT (Massachussets Institute of Technology), yaitu Ron Rivest, Adi Shamir, dan Len Adleman, pada tahun 1976.
* Termasuk algoritma kriptografi asimetri.
* Asimetri: kunci untuk enkripsi berbeda dengan kunci untuk dekripsi
* Setiap pengguna memiliki sepasang kunci:
1. Kunci publik, e: untuk enkripsi pesan
2. Kunci privat, p: untuk dekripsi pesan
* Kunci publik tidak rahasia, kunci privat rahasia
Algoritma pembangkitan pasangan kunci
1. Pilih dua bilangan prima, p dan q (rahasia)
2. Hitung n = pq. Besaran n tidak perlu dirahasiakan.
3. Hitung m = (p – 1)(q – 1).
4. Pilih sebuah bilangan bulat untuk kunci publik, e,
relatif prima terhadap m.
5. Hitung kunci dekripsi, d, melalui kekongruenan
ed º 1 (mod m).
* Contoh. Misalkan p = 47 dan q = 71 (keduanya prima), maka dapat dihitung
n = p ´ q = 3337
m = (p – 1)´(q – 1) = 3220.
Pilih kunci publik e = 79 (yang relatif prima dengan 3220.
Nilai edan n dapat dipublikasikan ke umum.
* Catatan: Dalam praktek, nilai a, b, dan e adalah bialngan yang sangat besar (minimal 200 digit)
* Selanjutnya dihitung kunci dekripsi d dengan kekongruenan:
e´ d º 1 (mod m)
Diperoleh nilai d = 1019. Ini adalah kunci dekripsi.
Algoritma enkripsi-dekripsi:
Enkripsi: ci = pie mod n
Dekripsi: pi = cid mod n,
* Misalkan plainteks: ‘HARI INI’
atau dalam desimal ASCII: 7265827332737873
Pecah pesan menjadi blok yang lebih kecil (misal 3 digit):
p1 = 726 p4 = 273
p2= 582 p5= 787
p3= 733 p6= 003
* Enkripsi setiap blok:
c1 = 72679mod 3337 = 215
c2 = 58279 mod 3337 = 776
dst untuk sisa blok lainnya
Keluaran: chiperteks C = 215 776 1743 933 1731 158.
* Dekripsi (menggunakan kunci privat d = 1019)
p1= 2151019 mod 3337 = 726
p2 =7761019 mod 3337 = 582
dst untuk sisi blok lainnya
Keluaran: plainteks = 7265827332737873
atau dalam kode ASCII karakternya adalah HARI INI.
* Pembangkit Bilangan Acak
* Pembangkit bilangan acak yang berbasis kekongruenan lanjar adalah linear congruential generator atau LCG:
Xn = (aXn– 1 + b) mod m
Xn = bilangan acak ke-n dari deretnya
Xn– 1 = bilangan acak sebelumnya
a = faktor pengali
b = increment
m = modulus
Kunci pembangkit adalah X0 yang disebut umpan (seed).
* Latihan Soal Teori Bilangan
* Soal 1
* Buktikan untuk setiap bilangan bulat positif n dan a, PBB(a, a + n) habis membagi n.
* Jawaban:
Misalkan PBB(a, a + n) = d.
Maka:
d | a + n à a + n = k1d
d | a à a = k2d
------------------ -
a + n – a = (k1 – k2)d
n = Kd (misal k1– k2 = K)
n = Kd à d | n (terbukti)
* Soal 2
Perlihatkan bahwa bila n| m, yang dalam hal ini n dan m adalah bilangan bulat positif yang lebih besar dari 1, dan jika a º b (mod m) dengan a dan badalah bilangan bulat, maka a º b (mod n).
* Jawaban:
Diketahui bahwa n | m atau dapat dituliskan sebagai :
m = k1. n ….(i)
Jika a ≡ b(mod m) maka m habis membagi a – b atau dapat dituliskan :
a = b + k2. m ….(ii)
Substitusikan (i) ke dalam (ii):
a = b + k2. k1. n
a = b + k3. n (misalkan k3= k2 . k1) (iii)
a – b = k3 . n yang berarti bahwa n | (a – b) atau
a ≡ b (mod n) <
* Soal 3
* Salah satu program enkripsi di dalam sistem operasi Linux adalah rot13. Enkripsi dilakukan dengan mengganti sebuah huruf dengan huruf ke-13 berikutnya dari susunan alfabet.
(a) Nyatakan fungsi enkripsi dan dekripsi di dalam rot13 sebagai persamaan aritmetika modulo dalam pi dan ci.
(b) Jika enkripsi dilakukan dua kali berturut-turut terhadap plainteks, apa yang terjadi?
* Jawaban:
• ci = E(pi) = (pi + 13) mod 26
pi = D(ci) = (ci– 13) mod 26
b) Jika dilakukan 2 kali enkripsi thd plaintext, maka hasilnya sama dengan plaintextawal.
* Soal 4
* Buktikan dengan induksi matematika bahwa semua bilangan berbentuk 11...1 pasti kongruen dengan 0 (mod 11) atau 1 (mod 11) (misalnya 111 ≡ 1 (mod 11) dan 111111 ≡ 0 (mod 11))
* Jawaban:
(i) Basis: 1 ≡ 1 (mod 11). Benar.
(ii) Rekurens:
* Jika 11...1 (nsuku) ≡ 1 (mod 11), maka
11...1 (n+1 suku) ≡ {11...1 (n suku) x 10 + 1} (mod 11)
≡ {1 x 10 + 1} (mod 11)
≡ 0 (mod 11)
* Jika 11...1 (n suku) ≡ 0 (mod 11), maka
11...1(n+1 suku) ≡ {11...1 (n suku) x 10 + 1} (mod 11)
≡ {0 x 10 + 1} (mod 11)
≡ 1 (mod 11)
* Menurut PIM, benar.
* Soal 5
* Carilah semua bilangan bulat positif yang tidak habis dibagi 2 dan bersisa 2 jika dibagi 3
* Jawaban:
Misal bilangan tersebut adalah x = 2k+1
k º 2 (mod 3) à k = 3n+2
Berarti x = 2(3n+2)+1= 6n+5
Jadi bilangan-bilangan yang memenuhi adalah
x = {5,11,17,23,…}
* Soal 6
* Tentukan xdan y bilangan bulat yang memenuhi persamaan 312x + 70y = 2, lalu hitunglah nilai dari : y mod x .
Jawaban:
Dengan menggunakan algoritma Euclid, ditemukan bahwa :
312 = 4.70 + 32 (i)
70 = 2.32 + 6 (ii)
32 = 5.6 + 2 (iii)
6 = 3.2 + 0 (iv)
Persamaan (iii) dapat dituliskan menjadi : 2 = 32 – 5.6 (v)
Persamaan (ii) dapat dituliskan menjadi : 6 = 70 – 2.32 (vi)
Sulihkan persamaan (vi) ke persamaan (v) :
2 = 32 – 5.(70 – 2.32)
2 = 32 – 5.70 + 10.32
2 = 11.32 – 5.70 (vii)
Persamaan (i) dapat dituliskan menjadi : 32 = 312 – 4.70 (viii)
Sulihkan persamaan (viii) ke persamaan (vii) :
2 = 11.(312 – 4.70) – 5.70
2 = 11.312 – 44.70 – 5.70
2 = 11.312 – 49.70 (ix)
Dari persamaan (ix) diketahui x dan y yang memenuhi adalah
x = 11 dan y = -49, sehingga y mod x = -49 mod 11 = 6
* Soal 7
Sebuah buku terbitan September 2008 memiliki ISBN 9X7-2309-97. Tentukan nilai X dan karakter uji dari nomor ISBN tersebut jika diketahui
* Jawaban:
* , à untuk k sebarang bilangan bulat
Untuk nilai k =
k = 1 → X = 2/3
k = 2 → X = 4
k = 3 → X = 17/3
k = 4 → X = 22/3
k = 5 → X = 9
k = 6 → X = 32/3
k = 7 → X = 37/3
k = 8 → X = 14
...dst
* Dapat dilihat di atas, untuk k = 2, 5, 8, ... nilai X bulat, namun untuk kode ISBN di atas, nilai X haruslah dalam rentang bilangan bulat 0-9, jadi nilai X yang memenuhi adalah 4 dan 9.
* Untuk mencari karakter uji, diketahui
mod 11 = karakter uji
Maka nilai karakter uji untuk :
kode ISBN 947-2309-97 dapat dicari sebagai berikut :
= 1(9) + 2(4) + 3(7) + 4(2) + 5(3) + 6(0) + 7(9) + 8(9) + 9(7) = 259
Jadi karakter uji untuk ISBN di atas = 259 mod 11 = 6
kode ISBN 997-2309-97 dapat dicari sebagai berikut :
= 1(9) + 2(9) + 3(7) + 4(2) + 5(3) + 6(0) + 7(9) + 8(9) + 9(7) = 269
Jadi karakter uji untuk ISBN di atas = 269 mod 11 = 5
* Soal 8
* Sebuah area parkir mempunyai sejumlah slot atau space yang dinomori 0 sampai 25. Mobil yang hendak parkir di area tersebut ditentukan dengan sebuah fungsi hash. Fungsi hash tersebut menentukan nomor slot yang akan ditempati mobil yang hendak parkir berdasarkan 3 angka terakhir pada plat nomor polisinya.
(a) Tentukan fungsi hash yang dimaksudkan.
(b) Tentukan nomor slot yang ditempati mobil yang datang berturut-turut dengan plat nomor polisinya adalah 423251, 76540, 17121, 2310, 4124, 1102, 1724
* Jawaban:
(a) h = x mod 26
(b) 423251 à 3 angka terakhir = 251 à 251 mod 26 = 17 (slot 17)
76540 à 3 angka terakhir = 540 à 540 mod 26 = 20 (slot 20)
17121 à 3 angka terakhir = 121 à 121 mod 26 = 17 (tetapi slot nomor 17 sudah terisi, jadi isi slot kosong berikutnya, yaitu 18)
2310 à 3 angka terakhir = 310 à 310 mod 26 = 24 (slot 24)
4124 à 3 angka terakhir = 124 à 124 mod 26 = 20 (slot 21 karena slot 20 sudah terisi)
1102 à 3 angka terakhir = 102 à 102 mod 26 = 24 (slot 25 karena slot 24 sudah terisi)
1724 à 3 angka terakhir = 724 à 724 mod 26 = 22 (slot 22)
Jadi, mobil-mobil yang datang mengisi slot 17, 20, 18, 24, 21, 25, dan 22
0 komentar:
Posting Komentar