My Note: Matematika Diskrit

ALGORITMA DAN BILANGAN BULAT

Kriptografi saat ini berkembang sedemikaian rupa sehingga menjadi sebuah ilmu tidak hanya seni. Memahami kriptografi dan kriptanalis memerlukan pengetahuan matematik. Matematika memberikan landasan matematis pada sebagian besar konsep di dalam kriptografi. Pada kryptography dasar tidak membutuhkan pengetahuan yang dalam atau sulit tapi seperti juga kita mempelajari ilmu-ilmu yang bukan matematika, yang kita butuhkan hanya sebatas pengenalan semua ide dari yang dibutuhkan saja.

Teori bilangan adalah teori yang mendasar dalam memahami kriptografi, khususnya system kriptografi kunci public. Bilangan yang dimaksudkan di sini hanyalah blangan bulat (integer). Bilangan bulat adalah blangan yang tidak mempunyai pecahan decimal, misalnya 8, 21, 8765, -34, 0.

1. Modular Arithmetic
Aritmatika modular sering kali diberikan diawal bangku sekolah dasar sebagai pemahaman aritmatik jam. Sebagai contoh 14 jam setelah jam 3 pagi adalah jam 5 pagi. Secara sederhana dapat dipahami sebagai berikut :
5 ( mod 12)º14 + 3
atau
14 + 3 = 1 . 12 + 5
Misalkan a adalah bilangan bulat dan m adalah bilangan bulat > 0. Operasi a mod m (dibaca a modulo m) memberkan sisa jika a dibagi dengan m. Bilangan m disebut modulus atau modulo, dan hasil arimetika modulo m terletak di dalam himpunan { 0, 1, 2, …, n-1 }
Notasi : m mod n = r sedemikian sehingga m = nq + r, dengan 0 ≤ r < n

Teorema EUCLIDEAN :
Misalkan m dan n adalah dua buah bilangan bulat dengan syarat n > 0. Jika m dibagi denga n maka terdapat dua buah bilangan bulat unik q (quotient) dan r (remainder), sedemikian sehingga
    m = nq + r
Dengan 0 ≤ r < n

Contoh :
•    1987 dibagi dengan 97 memberikan hasil bagi 20 dan sisa 47, atau ditulis sebagai 1987 mod 97 = 47    (1987 = 97. 20 + 47)
•    -22 dibagi dengan 3 memberikan hasil bagi -8 dan sisa 2, atau ditulis sebagai
-22 mod 3 = 2 ( -22 = (-8). 3 + 2 )
•    -22 = (-7).3 -1 salah karena r = -1 tidak memenuhi 0 ≤ r ≤ n
Apabila m negative, bagi | m | dengan n mendapatkan sisa r.
Maka m mod n = n – r bila r ≠ 0.
Jadi |-22| mod 3 = 1, sehingga – 22 mod 3 = 3 – 1 = 2

2. Pembagi Bersama Terbesar (PBB)
Misalkan a dan b adalah dua buah bilangan bulat tidak nol. Pembagi bersama terbesar PBB (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 :
Factor pembagi 45 : 1, 3, 5, 9, 15, 45
Factor pembagi 36 : 1, 2, 3, 4, 9, 12, 18, 36
Factor pembagi bersama dari 45 dan 36 adalah : 1, 3, 9
Sehingga PBB(45,36) = 9

3.    Algoritma Euclidean
Algoritma Euclidean adalah algoritma untuk mencari PBB dari dua buah bilangan bulat. Euclid adalah matematikawan Yunani yang menuliskan algoritma Euclidean dalam bukunya yang berjudul Element yang sangat terkenal.
Apabila diberikan dua buah bilangan blat tak negative m dan n (m ≥ n). Algoritma Eulidean berikut mencari pembagi bersama terbesar dari m dan n
Algor itma Euclidean :
•    Jika n = 0 maka m adalah PBB(m,n); stop
Kalau tidak (yaitu n ≠ 0) lanjutkan ke langkah 2
•    Bailah m dengan n dan misalkan r adalah sisanya
•    Ganti nilai m dengan nilai n dan nilai n dengan nilai r, lalu ulangi kembali ke langkah 1.
Contoh :
Misalkan m = 80 dan n = 12 dan dipenuhi syarat m ≥ n, maka PBB(80,12) dihitung dengan algoritma Euclidean sebagai berikut :

Sisa pembagian terakhir sebelum 0 adalah 4, maka PB(80,12) = 4

4. Relatif Prima
Dua buah bilangan bulat a dan b dikatakan relaif prima jika PBB(a,b) = 1. Jika a dan b relatif prima, maka terdapat bilangan bulat m dan n sedemikian sehingga
    ma + nb = 1
Contoh :
20 dan 3 relatif prima sebab 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

5.    Kekongruenan
0 jika dan hanya jika¹ b (mod n) dibaca a adalah kongruen ke b modulo n. Dimana untuk integer a, b dan n ºNotasi a
A = b + k n       untuk beberapa k
Oleh sebab itu n | (a – b) yang mana disebut juga n dibagi (a-b)
ri (mod n). Untuk sembarang modulus { 0,1, …, n-1} bentuk-membentuk semua himpunan sisa mod n. Untuk n = 12 semua himpunan sisa adalah {0, 1, …, 11}º 5 (mod 12) dan 5 adalah sisa dari 17 modulo 12. A adalah himpunan {r1, r2, …,rn} disebut semua himpunan sisa mod n jika setiap bilangan bulat a, tepat berpasangan dengan satu ri di dalam himpunan yang memenuhi a º b (mod n), b disebut sisa dari a modulo n . Sebagai contoh 17 º    Jika a
{0, 1, …, n-1} tetapi kadang-kadang bilangan bulat berada didalamÎ    Kita selalu lebih suka menggunakan b{-½ (n-1), … ½(n-1)} yang lebih berguna lagi.Îrange b
Sebagai catatan :
… dst.º 9 (mod 7) º 2 (mod 7) º -5 (mod 7) º-12 (mod 7)

Beberapa contoh kekongruenan :
2 ( mod 3)     ( 3 habis membagi 17 – 2 = 15)º•    17
15 (mod 11) ( 11 habis membagi -7 – 15 = -22)º•    - 7
b (mod m) dapat pula dituliskan dalam hubunganºKekongruenan a
    a = b + km
yang dalam hal ini k adalah bilangan bulat. Bedasarkan definisi aritmetika modulo, kitajuga dapat menliskan a mod m = r sebagai
r (mod m )º            a
Contoh :
2 ( mod 3) dapat ditulis sebagai 17 = 2 + 5 . 3º•    17
15 (mod 11) dapat ditulis sebagai - 7 = 15 + (-2) . 11º•    - 7

Sekarang pembagian bilangan bulat n untuk penjumlahan dan perkalian dengan hukum assosiatif, komutatif, dan distributive terbentuk. Untuk faktanya kita dapat menurunkan modulo n dari yang lain dan kemudian dilakukan operasi dan kemudian dilakukan penurunan dari modulo n, karena sisa modulo n adalah homomorphism dari lingkaran bilangan bulat ke lingkaran bilangan bulat modulo n.
Maka,
b (mod n)] (mod n)± [a(mod n) º b) (mod n) ±(a
dan
[a(mod n) * b (mod n)] (mod n)º(a * b) (mod n)

Teorema : misalkan m adalah bilangan bulat positif
b (mod m) dan c adalah sembarang bilangan bulat makaº1.    Jika a
(b + c) (mod m)º•    (a + c)
bc (mod m)º•    ac
bp (mod m) untuk suatu bilangan bulat tak negative pº•    ap
d (mod m), makaº b (mod m) dan c º2.    Jika a
(b + d) (mod m)º•    (a + c)
bd (mod m)º•    ac

Contoh :
4 (mod 3), maka menurut teorema diatas:º 2 (mod 3) dan 10 ºMisalkan 17
    22 = 7 ( mod 3)ó•    17 + 5 = 2 + 5 ( mod 3 )
    85 = 10 ( mod 3 )ó•    17 . 5 = 2 . 5 ( mod 3 )
   27 = 6 (mod 3)ó•    17 + 10 = 2 + 4 (m0d 3)
   170 = 8 (mod 3)ó•    17 . 10 = 2 . 4 (m0d 3)

6.   Invers Modulo
Jika a dan m relative prima dan m > 1, maka kita dapat menemukan inversi dari a modulo m. Inversi dari a (mod m), disebut juga inversi perkalian, adalah bilangan bulat a-1, sedemikian sehingga
1 (mod m)ºaa-1
dari definisi relative prima diketahui bahwa PBB (a,m) = 1, dan menurut persamaan terdapat bilangan bulat p dan q, sedemikian sehingga
pa + qm = 1
yang mengimplikasikan bahwa
1 (mod m)ºpa + qm
   0 (mod m ) makaºKarena qm
   1 (mod m)ºpa
Kekongruenan yang terakhir ini berarti bahwa p adalah inverse dari a( mod m)
Pembuktian diatas juga menceritakan bahwa, untuk mencari inverse dari a(mod m),kita harus membuat kombinasi lanjar dari a dan m = 1. Koeffisien a dari kombinasi lanjar tersebut merupakan, inverse dari a Modulo m.

Contoh :
Tentukan inverse dari 4 (mod 9),17 (mod 7), dan 18 (mod 10 )

Penyelesaian :
a.    Karena PBB (4,9) = 1, maka inverse dari 4 (mod 9) ada. Dari algoritma Euclidean diperoleh bahwa
9 = 2 . 4 + 1
Susun persamaan diatas menjadi
-2 . 4 + 1 . 9 = 1
Dari persamaan terakhir ini kita peroleh -2 adalah inverse dari 4 (mod 9)
-2 (mod 9).ºJadi 4-1

Periksalah bahwa
1 (mod 9)         (9 habis membagi -2 . 4 – 1 = -9)º-2 . 4
-2 (mod 9)), karenaºPerhatikan bahwa semua bilangan bulat yang kongruen dengan -2 (mod 9) juga adalah inverse dari 4( mod 9), misalnya 7( perhatikan bahwa 7
1( mod 9)          (9 habis membagi 7 . 4 – 1 = 27)º7 . 4
Bilangan bulat lain yang kongruen dengan -2 (mod 9) adalah 16,25,…
b.    Karena PBB (17,7) = 1, maka inverse dari 17 (mod 7) ada. Dari algoritma Euclidean diperoleh bahwa
17 = 2 . 7 + 3 ……… ( i )
7 = 2 . 3 + 1    …….. ( ii )
3 = 3 . 1 + 0    …….. ( iii )
Susun persamaan ( ii ) menjadi
        1 = 7 – 2 . 3     …….. ( iv )
Susun persamaan ( i ) menjadi
        3 = 17 -2 . 7     …….. ( v )
Substitusikan ( 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 ini kita peroleh -2 adalah invers dari 17 modulo 7
1 (mod 7)       ( 7 habis membagi -2 . 17 – 1 = -35)º        -2 . 17
c.    Karena PBB (18,10) = 2 ≠ 1, maka inverse dari 18 (mod 10) tidak ada.

7. 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
Pertanyaan Sun Tse dapat diirumuskan ke dalam system konruen lanjar :
3 ( mod 5)º    x
5 ( mod 7)º    x
7 (mod 11)º    x

Teorema Chinese Remainder Theorem
Misalkan m = m1, m2… mn dan setiap pasang mi,mj coprime (bilagan bulat positif sedemikain hingga PBB(mi,mj) = 1 untuk i ≠ j), maka system kongruen lanjar
x = ak mod mk
mempunyai sebuah solusi unik modulo m = m1 .m2 … . mn

CONTOH :   Diketahui 3 x mod 10 = 1, maka tentukan nilai x untuk permasalahan tersebut.

Penyelesaian :
•    Nilai 10 = 2 x 5 ( 10 didapat dari perkalian 2 bilangan prime yaitu 2 dan 5)
•    Pertama dicari solusi untuk nilai x1 dan x2, maka :
   x1 = 1Þ3 x mod 2 = 1
   x2 = 2Þ3 x mod 5 = 1
•    Langkah selanjutnya aplikasikan Chinese remainder algorithm untuk mencari solusi dari persamaan :
X mod 2 = x1 = 1
X mod 5 = x2 = 2

Pertama dicari nilai y1 dan y2 sehingga didapat :

maka x = 7 adalah jawaban dari 3 x mod 10 = 1 (yang mana berarti 7 adalah multiplicative invers dari 3 modulo 10

1.    General Equations
Penyelesaian general equation pada bentuk ax mod n = b
•    Apabila gcd(a,n) = 1
Dicari penyelesaian x0 untuk ax mod n = b.
Jika ax0 mod n = 1 termasuk abx0 mod n = b, maka x = bx0 mod n
•    Apabila gcd(a,n) = g :
Jika g pembagi b, yang mana b mod g = 0. Maka ax mod n = b jika q penyelesaian dari bentuk

g-1, dimana x0 adalah penyelesaian untuk

Jika g bukan pembagi b maka tidak ada penyelesaiannya.

CONTOH : jika diketahui 6x mod 10 = 4Penyelesaian :

• g = gcd(6,10) = 2
dan 2 merupakan pembagi dari 4, maka tedapat 2 penyelesaian.
• Dihitung x0 dari

Diambil x0 = 2
• Kemudian dihitung kedua penyelesaian tersebut

• Cek :
6 x 4 mod 10 = 24 mod 10 = 4
6 x 9 mod 10 = 54 mod 10 = 4

2. Euler Totient Function
Dasar teorema dari teori bilangan adalah :
Setiap bilangan bulat positif dapat ditulis dalam bentuk yang unik.