- Teori bilangan (number theory) adalah teori yang mendasar dalam memahami algoritma kriptografi.
- Bilangan yang dimaksudkan adalah bilangan bulat (integer).
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 bahwaa habismembagi 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”.
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.
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.
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.
Relatif Prima
Dua buah bilangan bulat a dan b dikatakan relatif prima jika PBB(a, b) = 1.
Aritmetika Modulo
- Misalkan a adalah bilangan bulat dan m adalah bilangan bulat > 0. Operasi a mod m (dibaca “amodulo m”) memberikan sisa jika a dibagi dengan m.
- Notasi: a mod m = r sedemikian sehingga a = mq + r, dengan 0 r < m.
- Bilangan m disebut modulus atau modulo, dan hasil aritmetika modulo m terletak di dalam himpunan {0, 1, 2, …, m – 1}.
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 mhabis membagi a – b.
- Jika a tidak kongruen dengan b dalam modulus m, maka ditulis a º/ b (mod m) .
Teorema 2.
Misalkan m adalah bilangan bulat positif.
1. Jika a kongruen b (mod m) dan c adalah sembarang bilangan bulat maka
(i) (a + c) kongruen (b + c) (mod m)
(ii) ac kongruen bc (mod m)
(iii) ap kongruen bp (mod m) untuk suatu bilangan bulat tak negatif p.
2. Jika a kongruen b (mod m) dan c kongruen d (mod m), maka
(i) (a + c) kongruen (b + d) (mod m)
(ii) ac kongruen bd (mod m)
Balikan Modulo (modulo invers)
Jika a dan m relatif prima dan m > 1, maka kita dapat menemukan balikan (invers) dari a modulo m. Balikan dari a modulo m adalah bilangan bulat (a invers) sedemikian sehingga a (a invers) kongruen 1 (mod m).
Kekongruenan Lanjar
- Kekongruenan lanjar adalah kongruen yang berbentuk ax º b (mod m) dengan m adalah bilangan bulat positif, a dan b sembarang bilangan bulat, dan x adalah peubah bilangan bulat.
- Nilai-nilai x dicari sebagai berikut: ax = b + km yang dapat disusun menjadi x = (b+km)/adengan k adalah sembarang bilangan bulat. Cobakan untuk k = 0, 1, 2, … dan k = –1, –2, … yang menghasilkan x sebagai bilangan bulat.
TEOREMA (Chinese Remainder Theorem)
Misalkan m1, m2, …, mn adalah bilangan bulat positif sedemikian sehingga PBB(mi, mj) = 1 untuk i j. Maka sistem kongruen lanjar x kongruen ak (mod mk) mempunyai sebuah solusi unik modulo m = m1 × m2 × … × mn.
Aritmetika Modulo dan Kriptografi
Aritmetika modulo cocok digunakan untuk kriptografi karena dua alasan:
- Oleh karena nilai-nilai aritmetika modulo berada dalam himpunan berhingga (0 sampai modulus m– 1), maka kita tidak perlu khawatir hasil perhitungan berada di luar himpunan.
- Karena kita bekerja dengan bilangan bulat, maka kita tidak khawatir kehilangan informasi akibat pembulatan (round off) sebagaimana pada operasi bilangan riil.
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 3. (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.
Teorema 4 (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 kongruen 1 (mod p)
Fungsi Euler f
Fungsi Euler f medefinisikan f(n) untuk n >= 1 yang menyatakan jumlah bilangan bulat positif < n yang relatif prima dengan n.
Teorema 5.
Jika n = pq adalah bilangan komposit dengan p dan q prima, maka f(n) = f(p) f(q) = (p – 1)(q – 1).
Teorema 6.
Jika p bilangan prima dan k > 0, maka f(pk) = pk – pk-1 = pk-1(p – 1) .
