Dalam matematika, aritmatika modular adalah sistem perhitungan bilangan bulat, dengan bantuan yang mereka "balik" ketika mereka mencapai nilai tertentu - modul (atau jamak dari mereka). Pendekatan modern untuk jenis ilmu ini dikembangkan oleh Carl Friedrich Gauss dalam bukunya Disquisitiones Arithmeticae yang diterbitkan pada tahun 1801. Ilmuwan komputer sangat suka menggunakan metode ini, karena sangat menarik dan membuka kemungkinan baru tertentu dalam operasi dengan angka.
Esensi
Karena jumlah jam dimulai lagi setelah mencapai 12, itu adalah aritmatika modulo 12. Menurut definisi di bawah, 12 tidak hanya sesuai dengan 12, tetapi juga dengan 0, sehingga waktu juga dapat disebut " 12:00". "0:00". Lagi pula, 12 sama dengan 0 modulo 12.
Aritmatika modular dapat diproses secara matematis dengan memperkenalkan relasi kongruen pada bilangan bulat yang kompatibel dengan operasi bilangan bulatbilangan: penjumlahan, pengurangan dan perkalian. Untuk bilangan bulat positif n, dua bilangan a dan b dikatakan kongruen modulo n jika selisihnya a - b adalah kelipatan dari n (yaitu, jika terdapat bilangan bulat k sehingga a - b=kn).
Pengurangan
Dalam matematika teoretis, aritmatika modular adalah salah satu dasar teori bilangan, yang mempengaruhi hampir semua aspek studinya, dan juga banyak digunakan dalam teori grup, ring, simpul, dan aljabar abstrak. Di bidang matematika terapan, digunakan dalam aljabar komputer, kriptografi, ilmu komputer, kimia, seni visual dan musik.
Latihan
Aplikasi yang sangat praktis adalah penghitungan checksum dalam pengenal nomor seri. Misalnya, beberapa standar buku umum menggunakan aritmatika modulo 11 (jika dirilis sebelum 1 Januari 2007) atau modulo 10 (jika dirilis sebelum atau setelah 1 Januari 2007). Demikian pula misalnya dalam International Bank Account Numbers (IBANs). Ini menggunakan aritmatika modulo 97 untuk mendeteksi kesalahan input pengguna dalam nomor rekening bank.
Dalam kimia, digit terakhir dari nomor registrasi CAS (nomor identifikasi unik untuk setiap senyawa kimia) adalah digit cek. Itu dihitung dengan mengambil digit terakhir dari dua bagian pertama dari nomor registrasi CAS dikalikan dengan 1, digit sebelumnya 2 kali, digit sebelumnya 3 kali, dll, menjumlahkan semuanya dan menghitung jumlah modulo 10.
Apa itu kriptografi? Faktanya adalah bahwamemiliki hubungan yang sangat kuat dengan topik yang sedang dibahas. Dalam kriptografi, hukum aritmatika modular secara langsung mendasari sistem kunci publik seperti RSA dan Diffie-Hellman. Di sini ia menyediakan bidang terbatas yang mendasari kurva eliptik. Digunakan dalam berbagai algoritma kunci simetris, termasuk Advanced Encryption Standard (AES), International Data Encryption Algorithm, dan RC4.
Aplikasi
Metode ini digunakan di area di mana Anda perlu membaca angka. Ini dikembangkan oleh ahli matematika, dan semua orang menggunakannya, terutama ilmuwan komputer. Ini didokumentasikan dengan baik dalam buku-buku seperti Modular Arithmetic for Dummies. Namun, sejumlah ahli menyarankan untuk tidak menganggap serius literatur tersebut.
Dalam ilmu komputer, aritmatika modular sering digunakan dalam bitwise dan operasi lain yang melibatkan struktur data melingkar dengan lebar tetap. Analis suka menggunakannya. Operasi modulo diimplementasikan dalam banyak bahasa pemrograman dan kalkulator. Dalam hal ini, ini adalah salah satu contoh aplikasi semacam itu. Perbandingan modulo, pembagian dengan sisa, dan trik lainnya juga digunakan dalam pemrograman.
Dalam musik, aritmatika modulo 12 digunakan ketika mempertimbangkan sistem temperamen yang sama dari dua belas nada, di mana oktaf dan enharmoniknya setara. Dengan kata lain, kunci dalam rasio 1-2 atau 2-1 adalah setara. Dalam musik dan humaniora lainnya, aritmatika memainkan peran yang agak signifikan, tetapi dalam buku teksilmuwan komputer biasanya tidak menulis tentang itu.
Metode pengurangan angka sembilan
Metode konversi 9s menawarkan pemeriksaan cepat perhitungan aritmatika desimal manual. Ini didasarkan pada aritmatika modular modulo 9 dan khususnya pada sifat penentu 10 10 1.
ada contoh lain. Modulo aritmatika 7 digunakan dalam algoritma yang menentukan hari dalam seminggu untuk tanggal tertentu. Secara khusus, kongruensi Zeller dan algoritma Doomsday banyak menggunakan modulo aritmatika 7.
Aplikasi lain
Telah dikatakan tentang aritmatika modular dalam kriptografi. Di area ini, dia tidak tergantikan. Lebih umum, aritmatika modular juga menemukan aplikasi dalam disiplin ilmu seperti hukum, ekonomi (seperti teori permainan), dan bidang ilmu sosial lainnya. Dengan kata lain, di mana pembagian proporsional dan distribusi sumber daya memainkan peran utama.
Karena aritmatika modular memiliki banyak kegunaan, penting untuk mengetahui betapa sulitnya menyelesaikan sistem perbandingan. Sistem kongruensi linier dapat diselesaikan dalam waktu polinomial dalam bentuk eliminasi Gauss. Hal ini dijelaskan secara lebih rinci oleh teorema kongruensi linier. Algoritma seperti reduksi Montgomery juga ada untuk memungkinkan operasi aritmatika sederhana dilakukan secara efisien. Misalnya, perkalian dan eksponensial modulo n, untuk bilangan besar. Ini sangat penting untuk diketahui untuk memahami apakriptografi. Bagaimanapun, ini hanya bekerja dengan operasi serupa.
Kesesuaian
Beberapa operasi, seperti menemukan logaritma diskrit atau kongruensi kuadrat, tampaknya serumit faktorisasi bilangan bulat dan dengan demikian merupakan titik awal untuk algoritma kriptografi dan enkripsi. Masalah ini mungkin NP-menengah.
Contoh
Berikut adalah tiga fungsi C yang cukup cepat - dua untuk melakukan perkalian modular dan satu untuk menaikkan ke bilangan modular untuk bilangan bulat tak bertanda hingga 63 bit, tanpa overflow sementara.
Tak lama setelah penemuan bilangan bulat (1, 2, 3, 4, 5…) menjadi jelas bahwa mereka dibagi menjadi dua kelompok:
- Genap: habis dibagi 2 (0, 2, 4, 6..).
- Ganjil: tidak habis dibagi 2 (1, 3, 5, 7…).
Mengapa perbedaan ini penting? Ini adalah awal dari abstraksi. Kami memperhatikan sifat-sifat bilangan (misalnya genap atau ganjil) dan bukan hanya bilangan itu sendiri ("37").
Hal ini memungkinkan kita untuk menjelajahi matematika pada tingkat yang lebih dalam dan menemukan hubungan antara jenis angka daripada yang spesifik.
Sifat bilangan
Menjadi "tiga" hanyalah properti lain dari sebuah angka. Mungkin tidak langsung berguna seperti genap/ganjil, tapi itu ada. Kita bisa membuat aturan seperti "tiga belas x tiga vena=tiga belas" dan seterusnya. Tapi itu gila. Kami tidak dapat membuat kata-kata baru setiap saat.
Operasi modulo (disingkat mod atau "%" dalam banyak bahasa pemrograman) adalah sisanya ketikadivisi. Misalnya, "5 mod 3=2", yang berarti 2 adalah sisa saat Anda membagi 5 dengan 3.
Saat mengubah istilah sehari-hari ke matematika, "bilangan genap" adalah "0 mod 2", artinya sisanya adalah 0 jika dibagi 2. Bilangan ganjil adalah "1 mod 2" (memiliki sisa dari 1).
Bilangan Genap dan Ganjil
Berapa genap x genap x ganjil x ganjil? Nah, itu 0 x 0 x 1 x 1=0. Sebenarnya, Anda dapat melihat jika bilangan genap dikalikan di mana saja, di mana seluruh hasilnya akan menjadi nol.
Trik dengan matematika modular adalah bahwa kita telah menggunakannya untuk menyimpan waktu - terkadang disebut "aritmatika jam".
Misalnya: 7:00 pagi (am/pm - tidak masalah). Di mana jarum jam dalam 7 jam?
Modulasi
(7 + 7) mod 12=(14) mod 12=2 mod 12 [2 adalah sisa 14 dibagi 12. Persamaan 14 mod 12=2 mod 12 berarti 14 jam dan 2 jam lihat sama pada jam 12 jam. Mereka kongruen, ditunjukkan oleh tanda sama dengan tiga kali lipat: 14 2 mod 12.
Contoh lain: sekarang jam 8:00 pagi. Di mana tangan besar akan berada dalam 25 jam?
Alih-alih menambahkan 25 hingga 8, Anda dapat memahami bahwa 25 jam hanyalah "1 hari + 1 jam". Jawabannya sederhana. Jadi, jam akan berakhir 1 jam lebih awal - jam 9:00.
(8 + 25) mod 12 (8) mod 12 + (25) mod 12 (8) mod 12 + (1) mod 12 9 mod 12. Anda secara intuitif mengonversi 25 ke 1 dan menambahkan ini ke 8.
Menggunakan jam sebagai analogi, kita dapat mengetahui apakahaturan aritmatika modular, dan mereka bekerja.
Penambahan/Pengurangan
Katakanlah dua kali terlihat sama pada jam kita ("2:00" dan "14:00"). Jika kita menambahkan x jam yang sama untuk keduanya, apa yang terjadi? Yah, mereka berubah untuk jumlah yang sama pada jam! 2:00 + 5 jam 14:00 + 5 jam - keduanya akan menunjukkan 7:00.
Kenapa? Kita cukup menambahkan 5 ke 2 sisa yang keduanya miliki dan mereka maju dengan cara yang sama. Untuk semua bilangan kongruen (2 dan 14), penjumlahan dan pengurangan hasilnya sama.
Lebih sulit untuk mengetahui apakah perkalian tetap sama. Jika 14 2 (mod 12), dapatkah kita mengalikan kedua angka dan mendapatkan hasil yang sama? Mari kita lihat apa yang terjadi jika kita mengalikan dengan 3.
Yah, 2:003 × 6:00. Tapi apa itu 14:003?
Ingat, 14=12 + 2. Jadi kita bisa mengatakan
143=(12 + 2)3=(123) + (23)
Bagian pertama (123) dapat diabaikan! Luapan 12 jam yang membawa 14 hanya berulang beberapa kali. Tapi siapa peduli? Kami tetap mengabaikan overflow.
Perkalian
Saat mengalikan, hanya sisanya yang penting, yaitu 2 jam yang sama untuk 14:00 dan 2:00. Secara intuitif, beginilah cara saya melihat perkalian tidak mengubah hubungan dengan matematika modular (Anda dapat mengalikan kedua sisi dari hubungan modular dan mendapatkan hasil yang sama).
Kami melakukannya secara intuitif, tetapi memberi nama itu bagus. Anda memiliki penerbangan yang tiba pukul 3 sore. Diatertunda 14 jam. Pukul berapa ia akan mendarat?
14 2 mod 12. Jadi, anggap saja jam 2, jadi pesawat akan mendarat jam 5 pagi. Solusinya sederhana: 3 + 2=5 pagi. Ini sedikit lebih rumit daripada operasi modulo sederhana, tetapi prinsipnya sama.
