Matematika Diskrit - Teori Bilangan

Pengertian

• 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 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”.

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 “a modulo 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 m habis 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)/a dengan 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:

1. 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.
2. 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) .