Teori bilangan & aritmetika modular: latihan soal dengan penyelesaian langkah demi langkah

1Sisa dan kongruensi

Membagi a dengan n memberi hasil bagi q dan sisa r: a = q·n + r dengan 0 ≤ r < n. Sisa ditulis a mod n. Untuk bilangan negatif q juga negatif: −3 = −1·7 + 4, jadi −3 mod 7 = 4.

Dua bilangan kongruen modulo n, a ≡ b (mod n), jika keduanya memberi sisa yang sama, yaitu jika n membagi a − b.

Sisa dapat direduksi pada setiap langkah, sehingga bilangan tetap kecil:

Misalnya 47·58 mod 9: 47 ≡ 2 dan 58 ≡ 4, jadi 47·58 ≡ 8 (mod 9).

2Algoritma Euclid

Faktor persekutuan terbesar FPB(a, b) adalah bilangan terbesar yang membagi keduanya. Algoritma Euclid memakai FPB(a, b) = FPB(b, a mod b):

1. Bagi: a = q·b + r.
2. Ganti (a, b) dengan (b, r).
3. Ulangi sampai sisanya 0. Sisa taknol terakhir adalah FPB.

Kelipatan persekutuan terkecil mengikutinya: KPK(a, b) = a·b / FPB(a, b).

3Invers dan algoritma yang diperluas

Invers a modulo n adalah bilangan x dengan a·x ≡ 1 (mod n). Invers ini ada tepat ketika FPB(a, n) = 1.

Algoritma Euclid yang diperluas menjalankan Euclid pada (n, a) dan mencatat koefisien t untuk setiap sisa, sehingga setiap sisa r ≡ t·a (mod n). Mulai dengan t = 0 untuk n dan t = 1 untuk a; setiap t baru adalah t dua baris di atas dikurangi q kali t satu baris di atas. Ketika sisa 1 muncul, t-nya adalah invers.

Dengan invers, kongruensi a·x ≡ b (mod n) diselesaikan dengan x ≡ a⁻¹·b. Bila d = FPB(a, n) lebih besar dari 1, ada d penyelesaian jika d membagi b, dan tidak ada jika tidak.

Dua kongruensi dengan modulus yang saling prima, x ≡ r₁ (mod m₁) dan x ≡ r₂ (mod m₂), memiliki tepat satu penyelesaian modulo m₁·m₂ (teorema sisa Cina). Tuliskan x = r₁ + m₁k dan selesaikan untuk k.

4Pangkat modular dan RSA

Pengkuadratan berulang menghitung aᵏ mod n dengan cepat: tulis k dalam biner, cari a, a², a⁴, a⁸, … mod n dengan mengkuadratkan dan mereduksi, lalu kalikan pangkat yang bitnya 1.

Teorema kecil Fermat: untuk bilangan prima p yang tidak membagi a, aᵖ⁻¹ ≡ 1 (mod p). Jadi eksponen dapat direduksi modulo p − 1.

RSA membangun kunci dari dua bilangan prima p dan q:

1. n = p·q dan φ(n) = (p − 1)(q − 1).
2. Pilih e dengan FPB(e, φ(n)) = 1; (n, e) adalah kunci publik.
3. Hitung d = e⁻¹ mod φ(n): kunci privat.
4. Enkripsi c = mᵉ mod n; dekripsi m = cᵈ mod n.

φ(n) Euler menghitung bilangan dari 1 sampai n yang saling prima dengan n: φ(p) = p − 1 untuk bilangan prima, φ(pᵏ) = pᵏ − pᵏ⁻¹, dan φ bersifat multiplikatif untuk faktor yang saling prima.

5Kesalahan umum

• Memberi sisa negatif untuk bilangan negatif: −17 mod 5 adalah 3, bukan −2.
• Menghentikan Euclid pada sisa pertama dan bukan sisa taknol terakhir.
• Lupa menambahkan n pada koefisien negatif dari algoritma yang diperluas.
• Menghitung eksponen RSA d modulo n dan bukan modulo φ(n).
• Mereduksi eksponen modulo p dan bukan p − 1 pada teorema Fermat.

6Seperti apa soal ujiannya

• Mudah: FPB dan sisa. Anda menjalankan algoritma Euclid untuk FPB atau KPK, mencari sisa bilangan negatif, dan mereduksi jumlah serta hasil kali modulo n.
• Sedang: invers dan kongruensi. Anda mencari invers modular dengan algoritma yang diperluas, menyelesaikan kongruensi linear, menggabungkan dua kongruensi dengan teorema sisa Cina, dan menghitung φ(n) Euler.
• Sulit: pangkat modular dan RSA. Anda memakai pengkuadratan berulang dan teorema Fermat, menyelesaikan kongruensi dengan beberapa penyelesaian, serta mencari eksponen privat RSA, teks sandi, dan pesan hasil dekripsi.