Dalam matematik, aritmetik modular ialah sistem pengiraan untuk integer, dengan bantuannya mereka "terbalik" apabila mencapai nilai tertentu - modul (atau jamaknya). Pendekatan moden untuk jenis sains ini telah dibangunkan oleh Carl Friedrich Gauss dalam Disquisitiones Arithmeticae yang diterbitkan pada tahun 1801. Para saintis komputer sangat gemar menggunakan kaedah ini, kerana ia sangat menarik dan membuka kemungkinan baharu tertentu dalam operasi dengan nombor.
Esen
Oleh kerana bilangan jam bermula semula selepas ia mencapai 12, ia adalah modulo aritmetik 12. Menurut definisi di bawah, 12 sepadan bukan sahaja dengan 12, tetapi juga dengan 0, jadi seseorang juga boleh menamakan masa yang dipanggil " 12:00". "0:00". Lagipun, 12 adalah sama dengan 0 modulo 12.
Aritmetik modular boleh diproses secara matematik dengan memperkenalkan hubungan kongruen kepada integer yang serasi dengan operasi pada integernombor: penambahan, penolakan dan pendaraban. Untuk integer positif n, dua nombor a dan b dikatakan sebagai modulo n kongruen jika perbezaannya a - b ialah gandaan n (iaitu, jika wujud integer k supaya a - b=kn).
Potongan
Dalam matematik teori, aritmetik modular ialah salah satu asas teori nombor, yang mempengaruhi hampir semua aspek kajiannya, dan juga digunakan secara meluas dalam teori kumpulan, gelang, simpulan dan algebra abstrak. Dalam bidang matematik gunaan, ia digunakan dalam algebra komputer, kriptografi, sains komputer, kimia, seni visual dan muzik.
Latihan
Aplikasi yang sangat praktikal ialah pengiraan jumlah semak dalam pengecam nombor siri. Contohnya, sesetengah piawaian buku biasa menggunakan modulo 11 aritmetik (jika dikeluarkan sebelum 1 Januari 2007) atau modulo 10 (jika dikeluarkan sebelum atau selepas 1 Januari 2007). Begitu juga, sebagai contoh, dalam Nombor Akaun Bank Antarabangsa (IBAN). Ini menggunakan aritmetik modulo 97 untuk mengesan ralat input pengguna dalam nombor akaun bank.
Dalam kimia, digit terakhir nombor pendaftaran CAS (nombor pengenalan unik untuk setiap sebatian kimia) ialah digit semakan. Ia dikira dengan mengambil digit terakhir daripada dua bahagian pertama nombor pendaftaran CAS didarab dengan 1, digit sebelumnya 2 kali, digit sebelumnya 3 kali, dsb., menambah semuanya dan mengira jumlah modulo 10.
Apakah itu kriptografi? Hakikatnya ialahia mempunyai perkaitan yang sangat kuat dengan topik yang dibincangkan. Dalam kriptografi, undang-undang aritmetik modular secara langsung mendasari sistem kunci awam seperti RSA dan Diffie-Hellman. Di sini ia menyediakan medan terhingga yang mendasari lengkung elips. Digunakan dalam pelbagai algoritma kunci simetri, termasuk Standard Penyulitan Lanjutan (AES), Algoritma Penyulitan Data Antarabangsa dan RC4.
Permohonan
Kaedah ini digunakan di kawasan yang anda perlu membaca nombor. Ia dibangunkan oleh ahli matematik, dan semua orang menggunakannya, terutamanya saintis komputer. Ini didokumentasikan dengan baik dalam buku seperti Aritmetik Modular untuk Dummies. Walau bagaimanapun, sebilangan pakar mengesyorkan agar tidak mengambil serius kesusasteraan tersebut.
Dalam sains komputer, aritmetik modular sering digunakan dalam bitwise dan operasi lain yang melibatkan struktur data bulatan lebar tetap. Penganalisis suka menggunakannya. Operasi modulo dilaksanakan dalam banyak bahasa pengaturcaraan dan kalkulator. Dalam kes ini, ia adalah salah satu contoh aplikasi sedemikian. Perbandingan modul, pembahagian dengan baki dan helah lain juga digunakan dalam pengaturcaraan.
Dalam muzik, modulo aritmetik 12 digunakan apabila mempertimbangkan sistem perangai sama dua belas nada, di mana oktaf dan enharmonik adalah setara. Dalam erti kata lain, kunci dalam nisbah 1-2 atau 2-1 adalah setara. Dalam muzik dan kemanusiaan lain, aritmetik memainkan peranan yang agak penting, tetapi dalam buku tekssaintis komputer biasanya tidak menulis mengenainya.
Kaedah mengurangkan sembilan
Kaedah penukaran 9s menawarkan semakan pantas pengiraan aritmetik perpuluhan manual. Ia berdasarkan modul aritmetik modular 9 dan khususnya pada sifat penentu 10 10 1.
ada contoh lain. Modulo aritmetik 7 digunakan dalam algoritma yang menentukan hari dalam seminggu untuk tarikh tertentu. Khususnya, kesesuaian Zeller dan algoritma Doomsday menggunakan banyak modulo aritmetik 7.
Aplikasi lain
Telah dikatakan mengenai aritmetik modular dalam kriptografi. Di kawasan ini, dia tidak boleh ditukar ganti. Secara umumnya, aritmetik modular juga menemui aplikasi dalam disiplin seperti undang-undang, ekonomi (seperti teori permainan), dan bidang lain dalam sains sosial. Dalam erti kata lain, di mana pembahagian berkadar dan pengagihan sumber memainkan peranan utama.
Oleh kerana aritmetik modular mempunyai pelbagai kegunaan, adalah penting untuk mengetahui betapa sukarnya untuk menyelesaikan sistem perbandingan. Sistem kekongruenan linear boleh diselesaikan dalam masa polinomial dalam bentuk penyingkiran Gauss. Ini diterangkan dengan lebih terperinci oleh teorem kongruen linear. Algoritma seperti pengurangan Montgomery juga wujud untuk membolehkan operasi aritmetik mudah dilakukan dengan cekap. Contohnya, modulo darab dan eksponen, untuk nombor yang besar. Ini sangat penting untuk diketahui untuk memahami apakriptografi. Lagipun, ia hanya berfungsi dengan operasi yang serupa.
Kekongruenan
Sesetengah operasi, seperti mencari logaritma diskret atau kongruen kuadratik, nampaknya sekompleks seperti pemfaktoran integer dan dengan itu merupakan titik permulaan untuk algoritma kriptografi dan penyulitan. Masalah ini mungkin NP-perantaraan.
Contoh
Berikut ialah tiga fungsi C yang agak pantas - dua untuk melakukan pendaraban modular dan satu untuk menaikkan kepada nombor modular untuk integer tidak bertanda sehingga 63 bit, tanpa limpahan sementara.
Sejurus selepas penemuan integer (1, 2, 3, 4, 5…) menjadi jelas bahawa mereka dibahagikan kepada dua kumpulan:
- Genap: boleh dibahagi dengan 2 (0, 2, 4, 6..).
- Gajil: tidak boleh dibahagikan dengan 2 (1, 3, 5, 7…).
Mengapa perbezaan ini penting? Ini adalah permulaan abstraksi. Kami melihat sifat nombor (cth., genap atau ganjil) dan bukan hanya nombor itu sendiri ("37").
Ini membolehkan kami meneroka matematik pada tahap yang lebih mendalam dan mencari hubungan antara jenis nombor dan bukannya yang khusus.
Sifat nombor
Menjadi "tiga" hanyalah satu lagi sifat nombor. Mungkin tidak segera berguna seperti genap/ganjil, tetapi ia ada. Kita boleh membuat peraturan seperti "tiga belas x tiga urat=tiga belas" dan seterusnya. Tapi memang gila. Kami tidak boleh membuat perkataan baharu sepanjang masa.
Operasi modulo (disingkat mod atau "%" dalam banyak bahasa pengaturcaraan) ialah baki apabilapembahagian. Contohnya, "5 mod 3=2", yang bermaksud 2 ialah baki apabila anda membahagikan 5 dengan 3.
Apabila menukar istilah harian kepada matematik, "nombor genap" ialah "0 mod 2", bermakna bakinya ialah 0 apabila dibahagikan dengan 2. Nombor ganjil ialah "1 mod 2" (mempunyai baki daripada 1).
Nombor genap dan ganjil
Apakah genap x genap x ganjil x ganjil? Nah, ini ialah 0 x 0 x 1 x 1=0. Sebenarnya, anda boleh melihat sama ada nombor genap didarab di mana-mana sahaja, di mana keseluruhan hasil akan menjadi sifar.
Helah dengan matematik modular ialah kita telah menggunakannya untuk menyimpan masa - kadangkala dipanggil "aritmetik jam".
Contohnya: 7:00 pagi (pg/ptg - tidak mengapa). Di manakah jarum jam dalam 7 jam?
Modulasi
(7 + 7) mod 12=(14) mod 12=2 mod 12 [2 ialah baki apabila 14 dibahagikan dengan 12. Persamaan 14 mod 12=2 mod 12 bermaksud 14 jam dan 2 jam lihat sama pada jam 12 jam. Ia adalah kongruen, ditunjukkan oleh tanda sama tiga: 14 ≡ 2 mod 12.
Contoh lain: jam 8:00 pagi. Di manakah tangan besar akan berada dalam masa 25 jam?
Daripada menambah 25 kepada 8, anda boleh memahami bahawa 25 jam hanyalah "1 hari + 1 jam". Jawapannya mudah sahaja. Jadi, jam akan tamat 1 jam lebih awal - pada pukul 9:00.
(8 + 25) mod 12 ≡ (8) mod 12 + (25) mod 12 ≡ (8) mod 12 + (1) mod 12 ≡ 9 mod 12. Anda secara intuitif menukar 25 kepada 1 dan menambah ini hingga 8.
Menggunakan jam sebagai analogi, kita boleh mengetahui sama adaperaturan aritmetik modular, dan ia berfungsi.
Tambahan/Penolakan
Katakan dua kali kelihatan sama pada jam kita ("2:00" dan "14:00"). Jika kita menambah x jam yang sama kepada kedua-duanya, apakah yang berlaku? Nah, mereka berubah untuk jumlah yang sama pada jam! 2:00 + 5 jam ≡ 14:00 + 5 jam - kedua-duanya akan menunjukkan 7:00.
Kenapa? Kita hanya boleh menambah 5 kepada 2 baki yang kedua-duanya ada dan mereka maju dengan cara yang sama. Untuk semua nombor kongruen (2 dan 14), penambahan dan penolakan mempunyai keputusan yang sama.
Lebih sukar untuk mengetahui sama ada pendaraban kekal sama. Jika 14 ≡ 2 (mod 12), bolehkah kita mendarab kedua-dua nombor dan mendapat keputusan yang sama? Mari lihat apa yang berlaku apabila kita darab dengan 3.
Nah, 2:003 × 6:00. Tetapi apakah 14:003?
Ingat, 14=12 + 2. Jadi kita boleh katakan
143=(12 + 2)3=(123) + (23)
Bahagian pertama (123) boleh diabaikan! Limpahan 12 jam yang membawa 14 hanya berulang beberapa kali. Tetapi siapa yang peduli? Kami tetap mengabaikan limpahan itu.
Pendaraban
Apabila mendarab, hanya baki yang penting, iaitu, 2 jam yang sama untuk 14:00 dan 2:00. Secara intuitif, beginilah saya melihat pendaraban tidak mengubah hubungan dengan matematik modular (anda boleh mendarab kedua-dua belah perhubungan modular dan mendapatkan hasil yang sama).
Kami melakukannya secara intuitif, tetapi bagus untuk memberi nama. Anda mempunyai penerbangan yang tiba pada pukul 3 petang. Diaditangguhkan selama 14 jam. Pukul berapa ia akan mendarat?
14 ≡ 2 mod 12. Jadi, anggap sebagai pukul 2, jadi kapal terbang akan mendarat pada pukul 5 pagi. Penyelesaiannya mudah: 3 + 2=5 pagi. Ini sedikit lebih rumit daripada operasi modulo ringkas, tetapi prinsipnya adalah sama.
