Kalkulator Modulo

Apakah Operasi Modulo?

Operasi modulo (mod, atau %) mengembalikan baki selepas membahagikan satu nombor dengan yang lain. Untuk mod b: membahagikan a dengan b, dan hasilnya adalah baki. Sebagai contoh, 17 mod 5 = 2 (kerana 17 = 3x5 + 2). Hasilnya sentiasa dalam julat [0, b-1] untuk nilai positif.

Hubungan asas:a = qxb + r, di mana q adalah quotient (floor ((a/b)) dan r adalah baki (0 <= r < b). Modulo adalah operasi pendamping kepada pembahagian bilangan bulat - jika ÷ b = q dengan baki r, maka mod b = r. Kalkulator ini menggunakan definisi modulo matematik yang benar (selalu bukan negatif untuk pembahagi positif), dan bukannya baki yang ditandatangani yang digunakan oleh beberapa bahasa pengaturcaraan.

Aritmetik modular - aritmetik dengan modulus tetap di mana nombor "bungkus" - membentuk asas aritmetik jam. Jam pada jam dikira mod 12 atau mod 24. Jika pukul 10 pagi dan anda menambah 5 jam: (10 + 5) mod 12 = 3 (PM). Kelakuan bungkus ini adalah pusat kepada banyak algoritma dalam sains komputer, kriptografi, dan teori nombor.

Contoh Modulo dan Penyelesaian Langkah demi Langkah

Untuk setiap pengiraan di bawah, formula adalah: baki = a - lantai (a ÷ b) x b.

Perhatikan 365 mod 7 = 1: ini memberitahu kita bahawa tahun bukan lompat mempunyai 52 minggu lengkap ditambah 1 hari tambahan, itulah sebabnya hari minggu bergeser 1 setiap tahun bukan lompat. Tahun lompat (366 hari) mod 7 = 2, menggeser hari sebanyak 2.

Aplikasi Aritmetik Modular

Modulo muncul sepanjang pengaturcaraan dan matematik.Pemeriksaan genap / ganjil:jika n % 2 == 0, n adalah genap.Array bulatan dan penampan cincin:index = (current_index + 1) % array_size berputar ke permulaan.Jadual hash:bucket = hash(key) % num_buckets memetakan sebarang nilai hash ke indeks bucket yang sah, memastikan tiada akses luar batas.

In pengiraan kalendar, aritmetik hari-minggu menggunakan mod 7. Formula Zeller dan algoritma Doomsday kedua-duanya bergantung pada aritmetik modular untuk menentukan hari dalam seminggu untuk mana-mana tarikh. Ini berfungsi kerana terdapat tepat 7 hari dalam seminggu - modulus tetap. Penyesuaian zon waktu menggunakan mod 24 untuk membungkus nilai jam dengan betul melintasi sempadan tengah malam.

In sistem digital, modulo digunakan di mana-mana alamat memori yang terlibat. Entri jadual halaman, pemilihan set cache, dan I / O memetakan memori semuanya bergantung pada pengindeksan modular. Set arahan CPU biasanya merangkumi arahan sisa (seperti modul) di samping pembahagian, dan arahan vektor SIMD menggunakan modulo untuk pembungkusan jalur dalam pergaulan.

In pengesanan kesilapanNombor kad kredit lulus algoritma Luhn (centang modulo-10). Nombor buku ISBN-10 menggunakan mod 11.

Modulo dalam Kriptografi

Aritmetik modular adalah asas matematik kriptografi kunci awam moden. Tiga algoritma kriptografi yang paling penting - RSA, Diffie-Hellman, dan Kriptografi Kurva Elips - semuanya bergantung pada operasi yang dilakukan modulo nombor perdana atau komposit yang besar.

Penyulitan RSAmenggunakan eksponen modular: untuk menyulitkan mesej M dengan kunci awam (e, n), mengira C = M^e mod n. Untuk menyahsulitkan, mengira M = C^d mod n di mana d adalah kunci peribadi. Keselamatan bergantung pada kesukaran pemfaktoran n (semiprime besar) - mengetahui hanya n, memulihkan p dan q secara komputasi tidak mungkin untuk saiz kunci di atas 2048 bit.

Pertukaran kunci Diffie-Hellmanmembolehkan dua pihak untuk mewujudkan rahsia bersama melalui saluran yang tidak selamat: Alice menghantar A = g ^ a mod p, Bob menghantar B = g ^ b mod p. Setiap pihak mengira rahsia bersama: Alice mengira B ^ a mod p = g ^ ((ab) mod p, Bob mengira A ^ b mod p = g ^ ((ab) mod p. Seorang penyadap yang mencegat g ^ a mod p dan g ^ b mod p tidak dapat memulihkan g ^ ((ab) mod p tanpa menyelesaikan masalah logaritma diskret.

Keselamatan sistem ini bergantung pada sifat satu arah eksponen modular: pengiraan g ^ a mod p adalah cepat (menggunakan penggandaan kuadrat berulang, O ((log a)), tetapi membalikkannya - mencari g ^ a mod p yang diberikan - dipercayai memerlukan masa eksponen untuk bilangan prima besar p.

Modulo dengan nombor negatif dan kes tepi

Tingkah laku modul dengan nombor negatif berbeza mengikut bahasa pengaturcaraan, yang menyebabkan banyak bug yang sukar ditemui. Memahami perbezaannya sangat penting bagi pemaju perisian.

Dalam matematik, modulo sentiasa mengembalikan hasil bukan negatif: -7 mod 3 = 2 (kerana -7 = -3x3 + 2, dan 0 <= 2 < 3). Kalkulator ini menggunakan definisi matematik.

Cara yang selamat untuk memastikan hasil yang tidak negatif dalam mana-mana bahasa:((a % b) + b) % b. Ini mengendalikan input negatif dengan betul dan digunakan secara dalaman oleh kalkulator kami. Corak ini penting apabila menggunakan modulo untuk pengindeksan array atau pengiraan hari kalendar di mana hasil negatif akan menyebabkan kesilapan.

Kes tepi untuk diingat:(1) Mana-mana nombor mod 1 = 0 - membahagikan dengan 1 tidak meninggalkan baki. (2) Mana-mana nombor mod itu sendiri = 0. (3) 0 mod mana-mana nombor bukan sifar = 0. (4) Bahagian (dan modulo) dengan sifar tidak ditentukan - sentiasa mengesahkan pembahagi sebelum mengira modulo. Kalkulator kami memaparkan mesej ralat yang jelas untuk modulo dengan sifar.

Ujian Modulo dan Kebolehbahagian

Salah satu kegunaan modulo yang paling praktikal ialah menguji pembahagian tanpa melakukan pembahagian penuh. Bilangan a boleh dibahagikan dengan b jika dan hanya jika mod b = 0.

Peraturan pembahagian ini adalah jalan pintas yang berasal dari sifat aritmetik modular. Peraturan jumlah digit untuk 3 dan 9 berfungsi kerana 10 1 (mod 3) dan 10 1 (mod 9), yang bermaksud nilai posisi setiap digit tidak relevan untuk pembahagian oleh 3 atau 9.

Eksponensi Modular: Mod Kuasa Cepat

Mengira a^b mod n secara langsung dengan mengira a^b, kemudian mengambil mod n, tidak praktikal untuk eksponen yang besar - a^100 boleh mempunyai ribuan digit. Eksponensi modular menggunakan identiti (axb) mod n = ((a mod n) x (b mod n)) mod n untuk memastikan hasil pertengahan kecil.

Algoritma cepat menggunakan kuadrat berulang (eksponensi binari):

• Tulis b dalam binari: contohnya, b=13 = 11012
• Hitung a, a2, a4, a8 masing-masing diambil mod n
• Kalikan kuasa yang sepadan dengan 1 bit: a13 = a8 x a4 x a1 (mod n)

Ini mengurangkan bilangan penggandaan dari b kepada O ((log2 b). Untuk b = 2048-bit eksponen RSA (~ 10 ^ 600), ini adalah perbezaan antara trilion penggandaan dan hanya ~ 2000. Tanpa pengoptimuman ini, penyulitan RSA akan menjadi tidak praktikal.

Modulo dalam Kehidupan Harian: Contoh Praktikal

Aritmetik modular muncul lebih kerap dalam kehidupan seharian daripada kebanyakan orang sedar. Pada masa anda membaca jam, mengira apabila peristiwa mingguan berulang, semak sama ada nombor boleh dibahagikan dengan 9, atau melihat digit terakhir tahun untuk menentukan hari apa minggu ulang tahun jatuh pada, anda melakukan aritmetik modular -- walaupun anda tidak menggunakan nama itu untuk itu.

Penjadualan dan pengulangan:Jika suatu peristiwa berlaku setiap 7 hari dan hari ini adalah hari Selasa (hari 2, indeks sifar dari Ahad = 0), maka 30 hari dari sekarang adalah (2 + 30) mod 7 = 32 mod 7 = 4, yang merupakan hari Khamis. Pengiraan langsung ini lebih cepat daripada mengira minggu dan hari secara berasingan. Begitu juga, jika langganan diperbaharui pada 28 setiap bulan dan ia kini ke-15, hari-hari sehingga pembaharuan adalah (28-15) mod 31 = 13 hari.

Digit pemeriksaan digital:Standar kod bar ISBN-13 menggunakan modulo 10. Digit terakhir dari mana-mana ISBN-13 dipilih supaya jumlah tertimbang semua 13 digit boleh dibahagikan dengan 10. Jika anda salah menaip satu digit semasa memasukkan ISBN buku, pemeriksaan akan gagal (mod 10 ≠ 0) dan ralat ditandai. Nombor kad kredit menggunakan algoritma Luhn - pemeriksaan mod-10 - untuk tujuan yang sama. Standard ISBN-10 menggunakan mod 11, yang membolehkan pengesanan transposisi tunggal.

Memori dan alamat komputer:RAM biasanya ditangani dalam kuasa 2 (1024, 2048, 4096 bait setiap halaman). Apabila program mengakses memori, OS menggunakan modulo untuk mengira halaman memori mana alamat jatuh dalam: page_number = alamat mod page_size. Pemilihan baris cache dalam cache CPU menggunakan modulo sama. Buffer wrap-around dalam pemprosesan audio, antrian paket rangkaian, dan streaming video semua menggunakan matematik buffer bulat: write_position = (write_position + 1) % buffer_size.

Seni dan corak muzik:Pola irama dalam teori muzik dianalisis menggunakan aritmetik modular. Tanda masa 4/4 mempunyai ketukan 0, 1, 2, 3 berulang - kitaran mod-4. Polyrhythms berlaku apabila dua irama bebas dengan tempoh m dan n bermain secara serentak; mereka menyelaraskan setiap lcmm (((, n) ketukan. Corak visual seperti tessellations jubin berulang dengan tempoh modular dalam dua dimensi.

Pengiraan zon geografi dan masa:Pemindahan UTC berkisar antara -12 hingga +14. penukaran antara zon masa: diberikan masa T dalam UTC, masa tempatan = (T + offset) mod 24. nilai yang dihasilkan mungkin kelihatan tidak intuitif (contohnya, 23 + 5 = 28, mod 24 = 4, yang bermaksud 4:00 pagi keesokan harinya), tetapi operasi mod mengendalikan sempadan tengah malam dengan betul. persimpangan garisan tarikh antarabangsa menggunakan mod 24 dalam kombinasi dengan pengiraan hari minggu menggunakan mod 7.

Memahami modulo menjadikan pengiraan seharian ini lebih jelas, lebih cepat, dan kurang terdedah kepada kesilapan. Sebaik sahaja anda melihat corak, anda akan melihat aritmetik modular dalam pengoptimuman penyusun, algoritma putaran dalam permainan video, penjadualan kejohanan pusingan, dan penyeimbangan beban di seluruh kluster pelayan - semuanya bergantung pada konsep yang mudah tetapi kuat baki selepas pembahagian.