Aritmatika Modular

Definisi Aritmatika Modular

Aritmatika modular, atau sering disebut mod (modulus), adalah sistem perhitungan di mana angka-angka diputar kembali setelah mencapai nilai tertentu. Nilai tersebut disebut modulus (biasanya dilambangkan dengan m). Dua bilangan a dan b disebut kongruen modulo m bila selisihnya habis dibagi m:

a b (mod m)

Contoh: 17 5 (mod 12) karena 175 = 12, dan 12 habis dibagi 12.

Sifat-sifat Penting

• Refleksif: a a (mod m)
• Simetris: Jika a b (mod m), maka b a (mod m)
• Transitif: Jika a b (mod m) dan b c (mod m), maka a c (mod m)
• Penjumlahan: (a + b) (c + d) (mod m) bila a c (mod m) dan b d (mod m)
• Perkalian: (ab) (cd) (mod m) bila a c (mod m) dan b d (mod m)
• Eksponensial: a^k b^k (mod m) bila a b (mod m)

Operasi Dasar

Penjumlahan

Misalkan a = 7, b = 15, dan m = 10. Maka:

Pengurangan

Perkalian

Invers Modular

Invers perkalian dari a modulo m adalah bilangan a yang memenuhi aa 1 (mod m). Invers ada bila gcd(a,m)=1. Contoh: invers 3 modulo 7 adalah 5, karena 35 = 15 1 (mod 7).

Algoritma Euclid

Digunakan untuk menghitung gcd(a,m) dan menemukan invers modular dengan Algoritma Euclid Terbalik.

Aplikasi Aritmatika Modular

Berbagai bidang memanfaatkan konsep modular, antara lain:

• Kriptografi RSA dan sistem enkripsi lainnya bergantung pada operasi modulo besar.
• Clock arithmetic Jam 12jam merupakan contoh seharihari dari modulus 12.
• Pengujian keutuhan data Checksum CRC menggunakan operasi modulo2.
• Algoritma hashing Menyebarkan nilai ke dalam tabel hash dengan h(k) = k mod m.
• Teori graf Warnawarna pada graf dapat dipelajari dengan teknik kombinatorial berbasis modul.

Contoh Kriptografi RSA Sederhana

Misalkan pilih dua bilangan prima p = 5 dan q = 11. Hitung n = pq = 55 dan (n) = (p1)(q1) = 40. Pilih e = 3 (gcd(3,40)=1). Cari d sehingga ed 1 (mod 40). Dengan algoritma Euclid, d = 27. Maka kunci publik (e,n) = (3,55) dan kunci privat (d,n) = (27,55). Enkripsi suatu pesan m menjadi c = m^e mod n, dekripsi m = c^d mod n.

Latihan Soal

1. Hitung 23 + 17 (mod 5).
2. Temukan invers 9 modulo 26.
3. Jika a 4 (mod 9) dan b 7 (mod 9), tentukan ab (mod 9).
4. Sebuah jam menunjukkan pukul 7. Setelah berapa jam lagi jam akan kembali menunjuk angka 7?
5. Berapa nilai 2^10 mod 13?

Jawaban Singkat

• 1. (23+17) = 40 40 mod 5 = 0
• 2. Invers 9 modulo 26 adalah 3, karena 93 = 27 1 (mod 26).
• 3. 47 = 28 28 mod 9 = 1
• 4. Karena jam 12jam, selisihnya 12 jam. Jadi setelah 12 jam jam kembali ke 7.
• 5. 2^10 = 1024 1024 mod 13 = 9