Matdis — Bab 7
Teori Bilangan
Keterbagian, bilangan prima, FPB/KPK, aritmetika modular, kongruensi, teorema Fermat & Euler, hingga algoritma RSA.
Ref: Rinaldi Munir, Matematika Diskrit, Edisi 7 (2020), Bab 7. — Rosen, Discrete Mathematics, 8th ed., Ch. 4.
Mengapa Teori Bilangan?
Analogi: jam dinding. Pukul 10 ditambah 5 jam bukan pukul 15, melainkan pukul 3 — karena kita menghitung modulo 12. Aritmetika modular adalah "matematika jam", dan ternyata itulah cara komputer menangani hash, checksum, dan indeks tabel.
Bab ini juga memuat algoritma RSA (Munir, Bab 7): mengapa mᵉᵈ ≡ m (mod n) bekerja mengikuti langsung dari Teorema Euler φ(n), karena e·d ≡ 1 (mod φ(n)). Mengalikan dua bilangan prima besar itu mudah, tetapi memfaktorkan hasilnya sangat sulit — asimetri inilah yang dimanfaatkan.
Analogi: Jam sebagai Aritmetika Modular
Aritmetika modular seperti jam analog. Pukul 10 + 5 jam = pukul 3 (bukan 15). Di mod 12, semua bilangan "berputar". RSA bekerja di ruang modular raksasa (mod n dengan n ratusan bit) — enkripsi dan dekripsi adalah "memutar" di ruang ini ke arah yang tepat.
1. Pembagian & Sifat Keterbagian
Definisi & Sifat
a | b ("a membagi b") jika ada k ∈ ℤ sehingga b = k·a.
Sifat Keterbagian
- a|b dan a|c → a|(b+c)
- a|b → a|(kb) untuk k ∈ ℤ
- a|b dan b|c → a|c (transitif)
- a|b dan b|a → a = ±b
Algoritma Pembagian
Untuk a,b ∈ ℤ, b > 0:
∃! q,r: a = bq + r
0 ≤ r < b
q = kuosien, r = sisa (remainder).
2. FPB & Algoritma Euclidean
Algoritma Euclidean (sekitar 300 SM)
gcd(a, b) = gcd(b, a mod b) karena pembagi bersama a dan b juga membagi a mod b.
gcd(a, 0) = a (base case)
Demo Algoritma Euclidean Interaktif
Langkah-langkah:
gcd(252, 198) = 36
KPK = 1386
3. Algoritma Extended Euclidean
Identitas Bézout
gcd(a,b) = ax + by (ada x,y ∈ ℤ)
Extended Euclidean menemukan koefisien Bézout x, y. Aplikasi kritis: Mencari modular inverse! Jika gcd(a,n)=1, maka a·x ≡ 1 (mod n), sehingga x = a⁻¹ (mod n).
Demo Extended GCD
gcd(35, 15) = 5
35·(1) + 15·(-2) = 5
gcd ≠ 1 → modular inverse tidak ada (a dan b tidak relatif prima)
4. Bilangan Prima & Teorema Fundamental Aritmetika
Teorema Fundamental Aritmetika
Setiap bilangan bulat n > 1 dapat difaktorkan secara unik sebagai produk bilangan prima:
n = p₁^a₁ × p₂^a₂ × ... × pₖ^aₖ
Uniknya faktorisasi prima adalah mengapa RSA bekerja — memfaktorkan n = p×q dari n saja sangat sulit (intractable untuk bilangan besar).
Uji Primalitas & Saringan Eratosthenes
97 adalah PRIMA ✓
Prima ≤ 50 (Sieve of Eratosthenes):
5. Kongruensi Modulo
Definisi & Sifat
a ≡ b (mod n) ↔ n | (a−b)
Sifat Kongruensi
- Refleksif: a ≡ a (mod n)
- Simetris: a≡b → b≡a
- Transitif: a≡b, b≡c → a≡c
- Jika a≡b dan c≡d: a+c≡b+d, ac≡bd
Operasi Modular
(a+b) mod n = ((a mod n)+(b mod n)) mod n
(a×b) mod n = ((a mod n)×(b mod n)) mod n
(aᵏ) mod n dengan fast exponentiation
Visualisasi SMIL: Aritmetika Modular (mod 12)
Eksplorasi Aritmetika Modular Interaktif
7×0,7×1,...,7×12 (mod 13)
6. Teorema Fermat Kecil & Teorema Euler
Teorema Fermat Kecil
Jika p prima dan p ∤ a:
aᵖ⁻¹ ≡ 1 (mod p)
Atau: aᵖ ≡ a (mod p)
Contoh: 2⁶ = 64 ≡ 1 (mod 7) ✓
Teorema Euler
Jika gcd(a,n)=1 maka:
aᵠ⁽ⁿ⁾ ≡ 1 (mod n)
φ(n) = Euler's Totient = |{k ≤ n : gcd(k,n)=1}|
Generalisasi Fermat kecil. Dasar RSA.
Demo Euler Totient φ(n)
Koprima dengan 12: { 1, 5, 7, 11 }
φ(12) = 4
Formula Euler Totient:
φ(p) = p-1 (p prima)
φ(p^k) = p^k - p^(k-1)
φ(mn) = φ(m)φ(n) jika gcd(m,n)=1 (multiplicatif)
φ(pq) = (p-1)(q-1) untuk p,q prima (kunci RSA!)
7. Teorema Sisa Cina (CRT)
Chinese Remainder Theorem
Jika m₁,m₂,...,mₖ pairwise coprime, maka sistem kongruensi:
x ≡ a₁ (mod m₁)
x ≡ a₂ (mod m₂)
⋮
x ≡ aₖ (mod mₖ)
memiliki solusi unik modulo M = m₁×m₂×...×mₖ.
Demo CRT: x ≡ 2 (mod 3), x ≡ 3 (mod 5), x ≡ 2 (mod 7)
Solusi: x ≡ 23 (mod 105)
Verifikasi: 23 mod 3 = 2 (✓), 23 mod 5 = 3 (✓), 23 mod 7 = 2 (✓)
8. RSA: Penerapan Teori Bilangan
RSA Algorithm — Teori Bilangan dalam Aksi
Key Generation
- Pilih dua prima berbeda p, q (ratusan bit di praktik)
- Hitung n = p × q dan φ(n) = (p-1)(q-1)
- Pilih e: 1 < e < φ(n), gcd(e,φ(n)) = 1 (biasanya e = 65537)
- Hitung d = e⁻¹ mod φ(n) (via Extended Euclidean)
- Public key = (e, n), Private key = (d, n)
Enkripsi
c = mᵉ mod n
Siapapun dengan public key (e,n) bisa mengenkripsi.
Dekripsi
m = cᵈ mod n
Hanya pemilik private key (d,n) bisa mendekripsi.
Kebenaran RSA: cᵈ = (mᵉ)ᵈ = m^(ed) ≡ m^(1+kφ(n)) ≡ m × (mᵠ⁽ⁿ⁾)ᵏ ≡ m×1ᵏ = m (mod n) via Teorema Euler.
Catatan: keamanan RSA bertumpu pada asumsi bahwa faktorisasi bilangan besar itu sulit — hingga kini belum ada algoritma polinomial yang diketahui untuk komputer biasa. Perhatikan bahwa ini adalah asumsi, bukan teorema yang terbukti.
9. Contoh Soal & Pembahasan
Soal 1: Algoritma Euclidean
Hitung gcd(1071, 462) menggunakan algoritma Euclidean.
Soal 2: Modular Inverse
Hitung 7⁻¹ mod 26 (berguna untuk Caesar cipher).
Soal 3: Fermat Kecil
Hitung 3¹⁰⁰ mod 101 (gunakan Fermat kecil; 101 prima).
Soal 4: Euler Totient
Hitung φ(360).
Soal 5: CRT
Selesaikan: x ≡ 1 (mod 2), x ≡ 2 (mod 3), x ≡ 3 (mod 5).
Soal 6: RSA Mini
RSA dengan p=5, q=11, n=55, φ(n)=40, e=7. Enkripsi m=3.
Bank Soal Multi-Kompleksitas & Kasus Terintegrasi
Ref: Munir, R. (2020). Matematika Diskrit, Edisi 7, Bab 7.
Mudah
1. Hitung gcd(252, 198) menggunakan algoritma Euclid.
2. Tentukan φ(36) menggunakan rumus Euler totient.
3. Hitung 7¹⁰ mod 13 menggunakan teorema Fermat.
4. Selesaikan: x ≡ 2 (mod 3), x ≡ 3 (mod 5) dengan CRT.
Sedang
1. Gunakan extended Euclidean untuk cari invers 17 mod 43.
2. RSA: p=11, q=13, e=7. Enkripsi pesan m=5. Cari kunci publik, privat, dan ciphertext.
3. Buktikan: jika p prima dan a tidak habis dibagi p, maka aᵖ⁻¹ ≡ 1 (mod p). Beri contoh.
4. Apa itu bilangan prima safe? Mengapa penting dalam kriptografi?
Sulit
1. Jelaskan RSA-CRT: Mengapa dekripsi RSA dengan CRT 4× lebih cepat? Tunjukkan konstruksi matematis lengkap untuk p=5, q=11, d=privat key.
2. Buktikan teorema Euler: aᵠ⁽ⁿ⁾ ≡ 1 (mod n) untuk gcd(a,n)=1. Hitung 7ˣ mod 60 menggunakan teorema ini (x=2020).
3. Extended Euclidean digunakan untuk menghitung invers modular dalam ECC. Hitung 15⁻¹ mod 26 dan jelaskan relevansinya dalam Hill cipher dan ECC.
Kasus Terintegrasi (2+ Topik)
Implementasikan dekripsi RSA-CRT secara penuh: n=pq=3·7=21, e=5, d=? Enkripsi m=4. Lakukan dekripsi konvensional dan CRT. Bandingkan jumlah langkah komputasi.
Buktikan: jika p dan q prima berbeda, maka a^(φ(pq)) ≡ 1 mod pq untuk gcd(a,pq)=1. Jelaskan mengapa ini menjadi fondasi kebenaran RSA (bahwa dekripsi mengembalikan plaintext asli).
Dalam ECC atas F_p, tambahan dua titik P=(x₁,y₁) dan Q=(x₂,y₂) memerlukan λ=(y₂-y₁)·(x₂-x₁)⁻¹ mod p. Hitung P+Q untuk P=(2,7), Q=(5,11) pada kurva y²=x³+2x+3 mod 13.