Matematikada modulli arifmetika butun sonlar uchun hisoblash tizimi boʻlib, ular yordamida ular maʼlum bir qiymatga – modulga (yoki ularning koʻpligiga) yetganda “aylanadi”. Ushbu turdagi fanga zamonaviy yondashuv Karl Fridrix Gauss tomonidan 1801 yilda nashr etilgan Disquisitiones Arithmeticae asarida ishlab chiqilgan. Kompyuter olimlari bu usuldan foydalanishni juda yaxshi ko'radilar, chunki u juda qiziqarli va raqamlar bilan ishlashda ma'lum yangi imkoniyatlarni ochadi.
Essensiya
Chunki soatlar soni 12 ga yetgandan keyin yana boshlanadi, bu arifmetik modul 12. Quyidagi ta'rifga ko'ra, 12 nafaqat 12 ga, balki 0 ga ham to'g'ri keladi, shuning uchun "" deb nomlangan vaqtni ham nomlash mumkin. 12:00". "0:00". Axir, 12 0 moduli 12 bilan bir xil.
Modulli arifmetika butun sonlar ustida amallar bilan mos keluvchi butun sonlarga kongruent munosabatni kiritish orqali matematik tarzda qayta ishlanishi mumkin.raqamlar: qo'shish, ayirish va ko'paytirish. Musbat n butun soni uchun ikkita a va b sonlar, agar ularning ayirmasi a - b n ga karrali bo'lsa (ya'ni, a - b=kn bo'lgan k butun soni mavjud bo'lsa) modulli n deb nomlanadi.
chegirmalar
Nazariy matematikada modulli arifmetika sonlar nazariyasi asoslaridan biri boʻlib, uni oʻrganishning deyarli barcha jihatlariga taʼsir koʻrsatadi, shuningdek, guruhlar, halqalar, tugunlar va mavhum algebra nazariyasida keng qoʻllaniladi. Amaliy matematika sohasida u kompyuter algebrasi, kriptografiya, informatika, kimyo, tasviriy sanʼat va musiqa fanlarida qoʻllaniladi.
Mashq
Serial raqamlari identifikatorlarida nazorat summalarini hisoblash juda amaliy dastur hisoblanadi. Misol uchun, ba'zi umumiy kitob standartlarida arifmetik modul 11 (agar 2007 yil 1 yanvargacha chiqarilgan bo'lsa) yoki modul 10 (agar 2007 yil 1 yanvardan oldin yoki keyin chiqarilgan bo'lsa) qo'llaniladi. Xuddi shunday, masalan, Xalqaro bank hisob raqamlarida (IBAN). Bu bank hisob raqamlaridagi foydalanuvchi kiritish xatolarini aniqlash uchun modul 97 arifmetikasidan foydalanadi.
Kimyoda CAS ro'yxatga olish raqamining oxirgi raqami (har bir kimyoviy birikma uchun noyob identifikatsiya raqami) tekshirish raqamidir. U CAS ro'yxatga olish raqamining dastlabki ikki qismining oxirgi raqamini 1 ga ko'paytirish, oldingi raqamni 2 marta, oldingi raqamni 3 marta va hokazolarni olib, barchasini qo'shib, 10 modul yig'indisini hisoblash orqali hisoblanadi.
Kriptografiya nima? Gap shundakimuhokama qilinayotgan mavzu bilan juda kuchli aloqaga ega. Kriptografiyada modulli arifmetika qonunlari bevosita RSA va Diffie-Hellman kabi ochiq kalitli tizimlar asosida yotadi. Bu erda u elliptik egri chiziqlar ostida yotuvchi chekli maydonlarni taqdim etadi. Turli simmetrik kalit algoritmlarida, jumladan Kengaytirilgan shifrlash standarti (AES), Xalqaro maʼlumotlarni shifrlash algoritmi va RC4 da qoʻllaniladi.
Ilova
Bu usul raqamlarni oʻqish kerak boʻlgan joylarda qoʻllaniladi. U matematiklar tomonidan ishlab chiqilgan va undan hamma foydalanadi, ayniqsa kompyuter olimlari. Bu Dummies uchun modul arifmetika kabi kitoblarda yaxshi hujjatlashtirilgan. Biroq, bir qator ekspertlar bunday adabiyotlarni jiddiy qabul qilmaslikni tavsiya qiladi.
Informatika fanida modulli arifmetika koʻpincha bitli va belgilangan kenglikdagi aylana maʼlumotlar tuzilmalari bilan bogʻliq boshqa operatsiyalarda qoʻllaniladi. Tahlilchilar undan foydalanishni yaxshi ko'radilar. Moduli operatsiya ko'plab dasturlash tillarida va kalkulyatorlarda amalga oshiriladi. Bunday holda, bu bunday dasturning bir misolidir. Dasturlashda modullarni taqqoslash, qoldiq bilan bo'lish va boshqa fokuslar ham qo'llaniladi.
Musiqada oktava va engarmonik ekvivalent boʻlgan oʻn ikki tonli teng temperament tizimini koʻrib chiqishda arifmetik modul 12 qoʻllaniladi. Boshqacha qilib aytganda, 1-2 yoki 2-1 nisbatidagi kalitlar ekvivalentdir. Musiqa va boshqa gumanitar fanlarda arifmetika juda muhim rol o'ynaydi, ammo darsliklardaKompyuter olimlari odatda bu haqda yozmaydilar.
To'qqiztani kamaytirish usuli
9s oʻtkazish usuli qoʻlda oʻnlik arifmetik hisoblarni tezkor tekshirishni taklif qiladi. U modulli arifmetik modul 9 va xususan, 10 10 1 hal qiluvchi xususiyatga asoslangan.
boshqa misollar ham bor. Arifmetik modul 7 ma'lum bir sana uchun haftaning kunini aniqlaydigan algoritmlarda qo'llaniladi. Xususan, Zeller muvofiqligi va Qiyomat algoritmi 7 arifmetik moduldan ko'p foydalanadi.
Boshqa ilovalar
Kriptografiyada modulli arifmetika haqida allaqachon aytilgan edi. Bu sohada u shunchaki almashtirib bo'lmaydigan narsadir. Umuman olganda, modulli arifmetika huquq, iqtisod (masalan, o'yin nazariyasi) va ijtimoiy fanlarning boshqa sohalari kabi fanlarda qo'llanilishini topadi. Boshqacha qilib aytganda, resurslarni mutanosib taqsimlash va taqsimlash katta rol o'ynaydi.
Modulli arifmetika juda keng qoʻllanish doirasiga ega boʻlgani uchun taqqoslash tizimini yechish qanchalik qiyinligini bilish muhimdir. Chiziqli muvofiqlik tizimini ko'pnomli vaqtda Gauss bartaraf qilish shaklida echish mumkin. Bu chiziqli muvofiqlik teoremasi bilan batafsilroq tavsiflanadi. Oddiy arifmetik operatsiyalarni samarali bajarishga imkon beradigan Montgomery reduksiyasi kabi algoritmlar ham mavjud. Masalan, katta sonlar uchun ko'paytirish va daraja ko'rsatish moduli n. Bu nimani tushunish uchun bilish juda muhimdirkriptografiya. Axir, u xuddi shunday operatsiyalar bilan ishlaydi.
Muvofiqlik
Diskret logarifm yoki kvadratik moslikni topish kabi ba'zi operatsiyalar butun son faktorizatsiyasi kabi murakkab ko'rinadi va shuning uchun kriptografik algoritmlar va shifrlash uchun boshlang'ich nuqtadir. Bu muammolar NP-intermediate bo'lishi mumkin.
Misollar
Quyidagilar uchta juda tez C funksiyasi: ikkitasi modulli koʻpaytirishni amalga oshirish uchun va biri 63 bitgacha boʻlgan belgisiz butun sonlar uchun modulli raqamlarga koʻtarish uchun, vaqtinchalik toʻlib ketishsiz.
Butun sonlar (1, 2, 3, 4, 5…) topilganidan koʻp oʻtmay ular ikki guruhga boʻlinganligi maʼlum boʻladi:
- Juft: 2 ga boʻlinadi (0, 2, 4, 6..).
- Toq: 2 ga boʻlinmaydi (1, 3, 5, 7…).
Bu farq nima uchun muhim? Bu abstraktsiyaning boshlanishi. Biz raqamning o'ziga ("37") emas, balki uning xususiyatlarini (masalan, juft yoki toq) sezamiz.
Bu bizga matematikani chuqurroq oʻrganish va aniq raqamlar emas, balki raqamlar turlari oʻrtasidagi munosabatlarni topish imkonini beradi.
Raqamning xossalari
“Uchlik” boʻlish raqamning yana bir xususiyatidir. Balki darhol juft/toq kabi foydali emas, lekin u bor. Biz "o'n uch x uch tomir=o'n uch" va shunga o'xshash qoidalarni yaratishimiz mumkin. Lekin bu aqldan ozgan. Biz har doim yangi so‘z yasay olmaymiz.
Moduli operatsiya (qisqartirilgan mod yoki ko'p dasturlash tillarida "%") qolganidabo'linish. Masalan, "5 mod 3=2", ya'ni 5 ni 3 ga bo'lganingizda 2 qoldiq bo'ladi.
Kundalik atamalarni matematikaga aylantirganda, "juft raqam" bu erda "0 mod 2", ya'ni 2 ga bo'linganda qolgan 0 bo'ladi. Toq son "1 mod 2" (qoldig'i bor) 1).
Juft va toq raqamlar
Juft x juft x toq x toq nima? Bu 0 x 0 x 1 x 1=0. Aslida, juft son istalgan joyda koʻpaytirilmaganligini koʻrishingiz mumkin, bu yerda butun natija nolga teng boʻladi.
Modulli matematikaning hiylasi shundaki, biz undan vaqtni saqlash uchun allaqachon foydalanganmiz - ba'zan "soat arifmetikasi" deb ham ataladi.
Masalan: ertalab 7:00 (am/pm - muhim emas). 7 soatdan keyin soat strelkasi qayerda bo'ladi?
Modulyatsiyalar
(7 + 7) mod 12=(14) mod 12=2 mod 12 [2 14 12 ga boʻlinganda qoldiq. 12 soatlik soatda ham xuddi shunday. Ular mos keladi, uch barobar teng belgisi bilan belgilanadi: 14 ≡ 2 mod 12.
Yana bir misol: soat 8:00. 25 soatdan keyin katta qo'l qayerda bo'ladi?
8 ga 25 qo'shish o'rniga 25 soat shunchaki "1 kun + 1 soat" ekanligini tushunishingiz mumkin. Javob oddiy. Shunday qilib, soat 1 soat oldin - 9:00da tugaydi.
(8 + 25) mod 12 ≡ (8) mod 12 + (25) mod 12 ≡ (8) mod 12 + (1) mod 12 ≡ 9 mod 12. Siz intuitiv ravishda 25 ni 1 ga aylantirdingiz va buni qo‘shdingiz 8.
gacha
Soatni analogiya sifatida ishlatib, biz buni aniqlashimiz mumkinmodulli arifmetika qoidalari va ular ishlaydi.
Qoʻshish/ayirish
Aytaylik, ikki marta bizning soatimizda bir xil ko'rinadi ("2:00" va "14:00"). Ikkalasiga ham bir xil x soat qo'shsak, nima bo'ladi? Xo'sh, ular soat bo'yicha bir xil miqdorda o'zgaradi! 2:00 + 5 soat ≡ 14:00 + 5 soat - ikkalasida ham 7:00 ko'rsatiladi.
Nega? Biz ikkala qoldiqga 5 ni qo'shishimiz mumkin va ular bir xil tarzda oldinga siljiydi. Barcha mos raqamlar (2 va 14) uchun qo‘shish va ayirish bir xil natijaga ega.
Koʻpaytirish oʻzgarmasligini bilish qiyinroq. Agar 14 ≡ 2 (mod 12) bo'lsa, ikkala raqamni ko'paytirib, bir xil natijaga erisha olamizmi? Keling, 3 ga ko'paytirsak nima bo'lishini ko'raylik.
Yaxshi, 2:003 × 6:00. Lekin 14:003 nima?
Yodda tuting, 14=12 + 2. Demak, 143=(12 + 2)3=(123) + (23)
Birinchi qismga (123) e'tibor bermaslik mumkin! 14 soatni o'z ichiga olgan 12 soatlik to'lib-toshish bir necha marta takrorlanadi. Lekin kimga g'amxo'rlik qiladi? Biz baribir to'lib ketishga e'tibor bermaymiz.
Ko'paytirish
Ko'paytirishda faqat qolganlari muhim, ya'ni 14:00 va 2:00 uchun bir xil 2 soat. Intuitiv ravishda, koʻpaytirish modulli matematika bilan bogʻliqlikni oʻzgartirmasligini shunday koʻraman (modulli munosabatlarning ikkala tomonini koʻpaytirib, bir xil natijani olishingiz mumkin).
Biz buni intuitiv tarzda qilamiz, lekin unga nom berish yoqimli. Soat 15:00 da parvozingiz bor. U14 soatga kechiktirildi. U soat nechada qo'nadi?
14 ≡ 2 mod 12. Demak, uni soat 2 deb tasavvur qiling, shunda samolyot ertalab soat 5 da qo‘nadi. Yechim oddiy: 3 + 2=ertalab 5. Bu oddiy modul operatsiyasidan biroz murakkabroq, lekin printsip bir xil.
