materi kuliah PTB

3. Teori Bilangan
· Teori bilangan (number theory) adalah teori yang mendasar
dalam memahami algoritma kriptografi
· Bilangan yang dimaksudkan adalah bilangan bulat (integer)
3.1 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 a dan b adalah dua buah bilangan bulat dengan
syarat a ¹ 0. Kita menyatakan bahwa 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. (Z = himpunan
bilangan bulat)
· Kadang-kadang pernyataan “a habis membagi b“ ditulis juga
“b kelipatan a”.
· 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).
Teori Bilangan
Rinaldi Munir – IF5054 Kriptografi 2
Teorema 1 (Teorema Euclidean). Misalkan m dan n adalah dua
buah bilangan bulat dengan syarat n > 0. Jika m dibagi dengan n
maka terdapat dua buah bilangan bulat unik q (quotient) dan r
(remainder), sedemikian sehingga
m = nq + r (1)
dengan 0 £ r < n.
Contoh 2.
(i) 1987 dibagi dengan 97 memberikan hasil bagi 20 dan sisa 47:
1987 = 97 × 20 + 47
(ii) –22 dibagi dengan 3 memberikan hasil bagi –8 dan sisa 2:
–22 = 3(–8) + 2
tetapi –22 = 3(–7) – 1 salah karena r = –1 tidak memenuhi
syarat 0 £ r < n.
3.2 Pembagi Bersama Terbesar (PBB)
· Misalkan a dan b adalah dua buah bilangan bulat tidak nol.
Pembagi bersama terbesar (PBB – greatest common divisor
atau gcd) dari a dan b adalah bilangan bulat terbesar d
sedemikian sehingga 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 dari 45 dan 36 adalah 1, 3, 9
PBB(45, 36) = 9.
Teori Bilangan
Rinaldi Munir – IF5054 Kriptografi 3
Algoritma Euclidean
· Algoritma Euclidean adalah algoritma untuk mencari PBB
dari dua buah bilangan bulat.
· Euclid, penemu algoritma Euclidean, adalah seorang
matematikawan Yunani yang menuliskan algoritmanya
tersebut dalam bukunya yang terkenal, Element.
· Diberikan dua buah bilangan bulat tak-negatif m dan n (m ³
n). Algoritma Euclidean berikut mencari pembagi bersama
terbesar dari m dan n.
Algoritma Euclidean
1. Jika n = 0 maka
m adalah PBB(m, n);
stop.
tetapi jika n ¹ 0,
lanjutkan ke langkah 2.
2. Bagilah m dengan n dan misalkan r adalah sisanya.
3. Ganti nilai m dengan nilai n dan nilai n dengan nilai r, lalu
ulang kembali ke langkah 1.
Contoh 4. m = 80, n = 12 dan dipenuhi syarat m ³ n
80 = 6×12 +8
12 = 1×8+ 4
8 = 2×4 + 0
Sisa pembagian terakhir sebelum 0 adalah 4, maka PBB(80, 12) =
4.
Teori Bilangan
Rinaldi Munir – IF5054 Kriptografi 4
3.3 Relatif Prima
· Dua buah bilangan bulat a dan b dikatakan relatif prima jika
PBB(a, b) = 1.
· Contoh 5. 20 dan 3 relatif prima sebab PBB(20, 3) = 1.
Begitu juga 7 dan 11 relatif prima karena PBB(7, 11) = 1.
Tetapi 20 dan 5 tidak relatif prima sebab PBB(20, 5) = 5 ¹ 1.
· Jika a dan b relatif prima, maka terdapat bilangan bulat m
dan n sedemikian sehingga
ma + nb = 1 (2)
· Contoh 6. Bilangan 20 dan 3 adalah relatif prima karena
PBB(20, 3) =1, atau dapat ditulis
2 . 20 + (–13) . 3 = 1
dengan m = 2 dan 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.
3.4 Aritmetika Modulo
· Misalkan a adalah bilangan bulat dan m adalah bilangan bulat
> 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.
Teori Bilangan
Rinaldi Munir – IF5054 Kriptografi 5
· Bilangan m disebut modulus atau modulo, dan hasil
aritmetika modulo m terletak di dalam himpunan {0, 1, 2, …,
m – 1} (mengapa?).
Contoh 7. 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 (v): Karena a negatif, bagi |a| dengan m mendapatkan
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 kita katakan
38 º 13 (mod 5) (baca: 38 kongruen dengan 13 dalam
modulo 5).
· Misalkan a dan b adalah bilangan bulat dan m adalah
bilangan > 0, maka a º b (mod m) jika m habis membagi a –
b.
· Jika a tidak kongruen dengan b dalam modulus m, maka
ditulis a º/ b (mod m) .
Contoh 8.
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)
Teori Bilangan
Rinaldi Munir – IF5054 Kriptografi 6
· Kekongruenan a º b (mod m) dapat pula dituliskan dalam
hubungan
a = b + km (3)
yang dalam hal ini k adalah bilangan bulat.
Contoh 9.
17 º 2 (mod 3) dapat ditulis sebagai 17 = 2 + 5 × 3
–7 º 15 (mod 11) dapat ditulis sebagai –7 = 15 + (–2)11
· Berdasarkan definisi aritmetika modulo, kita dapat
menuliskan a mod m = r sebagai
a º r (mod m)