Математикийн хувьд модульчлагдсан арифметик нь бүхэл тоонуудын тооцооллын систем бөгөөд тэдгээрийн тусламжтайгаар модуль (эсвэл тэдгээрийн олон тоо) тодорхой утгад хүрэх үед "эргэдэг". Энэ төрлийн шинжлэх ухааны орчин үеийн хандлагыг Карл Фридрих Гаусс 1801 онд хэвлүүлсэн Disquisitiones Arithmeticae номдоо боловсруулсан. Энэ нь маш сонирхолтой бөгөөд тоонуудтай ажиллахад тодорхой шинэ боломжуудыг нээж өгдөг тул компьютерийн эрдэмтэд энэ аргыг ашиглах дуртай.
Эссенс
Цагийн тоо 12 болсны дараа дахин эхэлдэг тул энэ нь арифметик модуль 12. Доорх тодорхойлолтоор 12 нь зөвхөн 12 биш, 0-тэй тохирч байгаа тул " гэж нэрлэх цагийг бас нэрлэж болно. 12:00". "0:00". Эцсийн эцэст 12 нь 0 модуль 12-той ижил байна.
Модульчлагдсан арифметикийг бүхэл тоон дээрх үйлдлүүдтэй нийцтэй бүхэл тоонуудын конгруент хамаарлыг оруулснаар математикийн аргаар боловсруулж болно.тоо: нэмэх, хасах, үржүүлэх. Эерэг n бүхэл тооны хувьд a ба b хоёр тоо нь тэдгээрийн ялгаа a - b нь n-ийн үржвэр бол (өөрөөр хэлбэл a - b=kn гэсэн бүхэл k тоо байвал) модуль n гэж тохирно.
Суутгал
Онолын математикийн хувьд модульчлагдсан арифметик нь тооны онолын нэг үндэс бөгөөд түүний судалгааны бараг бүх тал дээр нөлөөлдөг бөгөөд бүлэг, цагираг, зангилаа, хийсвэр алгебрийн онолд өргөн хэрэглэгддэг. Хэрэглээний математикийн салбарт үүнийг компьютерийн алгебр, криптограф, компьютерийн шинжлэх ухаан, хими, дүрслэх урлаг, хөгжимд ашигладаг.
Дасгал
Маш практик хэрэглээ бол серийн дугаар тодорхойлогч дахь хяналтын нийлбэрийг тооцоолох явдал юм. Жишээлбэл, зарим нийтлэг номын стандартууд арифметик модуль 11 (2007 оны 1-р сарын 1-ээс өмнө гарсан бол) эсвэл модуль 10 (2007 оны 1-р сарын 1-нээс өмнө эсвэл дараа гарсан бол) ашигладаг. Үүнтэй адилаар, жишээлбэл, Олон улсын банкны дансны дугаар (IBAN). Энэ нь банкны дансны дугаарт хэрэглэгчийн оруулсан алдааг илрүүлэхийн тулд модуль 97 арифметикийг ашигладаг.
Химид CAS бүртгэлийн дугаарын сүүлчийн орон (химийн нэгдэл бүрийн өвөрмөц таних дугаар) нь шалгах орон юм. Энэ нь CAS регистрийн дугаарын эхний хоёр хэсгийн сүүлийн цифрийг 1-ээр, өмнөх цифрийг 2 дахин, өмнөх цифрийг 3 дахин үржүүлж, бүгдийг нь нэмж, модуль 10-ын нийлбэрийг тооцоолох замаар тооцоолно.
Криптограф гэж юу вэ? Бодит байдал ийм л байнаэнэ нь хэлэлцэж буй сэдэвтэй маш хүчтэй холбоотой. Криптографийн хувьд модульчлагдсан арифметикийн хуулиуд нь RSA, Diffie-Hellman зэрэг нийтийн түлхүүрийн системүүдийн шууд үндэс суурь болдог. Энд зууван муруйн суурь болох хязгаарлагдмал талбаруудыг өгдөг. Нарийвчилсан шифрлэлтийн стандарт (AES), Олон улсын өгөгдлийн шифрлэлтийн алгоритм, RC4 зэрэг тэгш хэмтэй түлхүүрийн алгоритмуудад ашиглагддаг.
Програм
Энэ аргыг тоо унших шаардлагатай газруудад ашигладаг. Үүнийг математикчид бүтээсэн бөгөөд хүн бүр, ялангуяа компьютерийн эрдэмтэд үүнийг ашигладаг. Үүнийг Dummies-д зориулсан модуль арифметик гэх мэт номуудад сайн баримтжуулсан байдаг. Гэсэн хэдий ч олон мэргэжилтнүүд ийм ном зохиолыг нухацтай авч үзэхгүй байхыг зөвлөж байна.
Компьютерийн шинжлэх ухаанд модульчлагдсан арифметикийг ихэвчлэн битийн болон тогтмол өргөнтэй дугуй өгөгдлийн бүтэцтэй холбоотой бусад үйлдлүүдэд ашигладаг. Шинжээчид үүнийг ашиглах дуртай. Модулийн ажиллагааг олон програмчлалын хэл, тооцоолуур дээр хэрэгжүүлдэг. Энэ тохиолдолд энэ нь ийм хэрэглээний нэг жишээ юм. Програмчлалд модулийг харьцуулах, үлдэгдэлтэй хуваах болон бусад заль мэхийг мөн ашигладаг.
Хөгжимд арифметик модуль 12-ыг арав хоёр тоннын тэгш хэмийн системийг авч үзэхэд ашигладаг бөгөөд үүнд октава ба ангармони нь тэнцүү байна. Өөрөөр хэлбэл 1-2 эсвэл 2-1 харьцаатай түлхүүрүүд нь тэнцүү байна. Хөгжим болон бусад хүмүүнлэгийн чиглэлээр арифметик нь нэлээд чухал үүрэг гүйцэтгэдэг боловч сурах бичигт байдагКомпьютерийн эрдэмтэд ихэвчлэн энэ тухай бичдэггүй.
Есөн багасгах арга
9s хувиргах арга нь аравтын бутархайн арифметик тооцоог гар аргаар хурдан шалгах боломжийг олгодог. Энэ нь модульчлагдсан арифметик модуль 9, ялангуяа шийдвэрлэх шинж чанар 10 10 1 дээр суурилдаг.
өөр жишээнүүд байна. Арифметик модуль 7 нь тодорхой огнооны долоо хоногийн өдрийг тодорхойлдог алгоритмд ашиглагддаг. Ялангуяа, Зеллерийн конгруэнц болон сүйрлийн алгоритм нь арифметик модуль 7-г их хэмжээгээр ашигладаг.
Бусад програм
Криптограф дахь модульчлагдсан арифметикийн талаар аль хэдийн хэлсэн. Энэ салбарт тэр зүгээр л орлуулшгүй юм. Ерөнхийдөө модульчлагдсан арифметик нь хууль, эдийн засаг (тоглоомын онол гэх мэт) болон нийгмийн шинжлэх ухааны бусад салбарт хэрэглээг олдог. Өөрөөр хэлбэл, нөөцийн пропорциональ хуваарилалт, хуваарилалт гол үүрэг гүйцэтгэдэг.
Модульчлагдсан арифметик нь маш өргөн хүрээний хэрэглээтэй байдаг тул харьцуулалтын системийг шийдвэрлэх нь ямар хэцүү болохыг мэдэх нь чухал юм. Шугаман конгруэнцын системийг олон гишүүнт хугацаанд Гауссын арилгах хэлбэрээр шийдэж болно. Үүнийг шугаман конгруентийн теоремоор илүү дэлгэрэнгүй тайлбарласан болно. Мөн энгийн арифметик үйлдлүүдийг үр дүнтэй гүйцэтгэх боломжийг олгодог Монтгомеригийн бууралт зэрэг алгоритмууд байдаг. Жишээлбэл, олон тооны хувьд үржүүлэх, нэмэгдүүлэх модуль n. Юу болохыг ойлгохын тулд үүнийг мэдэх нь маш чухал юмкриптограф. Эцсийн эцэст энэ нь ижил төстэй үйлдлүүдтэй ажилладаг.
Тохиролт
Дискрет логарифм эсвэл квадрат конгруэнцийг олох зэрэг зарим үйлдлүүд нь бүхэл тоон хүчин зүйлчлэлтэй адил төвөгтэй мэт санагддаг тул криптограф алгоритм болон шифрлэлтийн эхлэлийн цэг болдог. Эдгээр асуудал нь NP-intermediate байж болно.
Жишээ
Дараах нь маш хурдан гурван C функц юм - хоёр нь модульчлагдсан үржүүлэх, нэг нь түр зуурын халихгүйгээр 63 бит хүртэлх тэмдэггүй бүхэл тоонуудад модульчлагдсан тоо руу өсгөх зориулалттай.
Бүхэл тоонуудыг (1, 2, 3, 4, 5…) нээсний дараа удалгүй тэдгээр нь хоёр бүлэгт хуваагдсан нь тодорхой болсон:
- Тэгш: 2-т хуваагддаг (0, 2, 4, 6..).
- Сондгой: 2-т хуваагдахгүй (1, 3, 5, 7…).
Энэ ялгаа яагаад чухал вэ? Энэ бол хийсвэрлэлийн эхлэл юм. Бид зөвхөн тоог нь биш ("37") тооны шинж чанарыг (жишээ нь, тэгш эсвэл сондгой) анзаардаг.
Энэ нь бидэнд математикийг илүү гүнзгийрүүлэн судлах, тодорхой тоонуудаас илүү тооны төрлүүдийн хоорондын хамаарлыг олох боломжийг олгодог.
Тооны шинж чанарууд
"Гурав" байх нь тооны өөр нэг шинж чанар юм. Магадгүй тэр даруй тэгш/сондгой шиг ашигтай биш, гэхдээ энэ нь тэнд байна. Бид "арван гурав х гурван судал=арван гурав" гэх мэт дүрмийг бий болгож чадна. Гэхдээ галзуу юм. Бид байнга шинэ үг хийж чадахгүй.
Модуль үйлдэл (олон програмчлалын хэлэнд товчилсон mod буюу "%") нь дараах үед үлддэг.хэлтэс. Жишээлбэл, "5 mod 3=2" нь 5-ыг 3-т хуваахад 2 нь үлдэгдэл болно гэсэн үг.
Өдөр тутмын нэр томъёог математикт хөрвүүлэх үед "тэгш тоо" нь "0 mod 2" байх бөгөөд 2-т хуваагдахад үлдэгдэл нь 0 байна. Сондгой тоо нь "1 mod 2" (үлдэгдэлтэй байна) 1).
Тэгш ба сондгой тоо
Тэгш x тэгш x сондгой x хэд вэ? Энэ нь 0 x 0 x 1 x 1=0 байна. Үнэндээ тэгш тоог хаана ч үржүүлбэл бүх үр дүн нь тэг болохыг харж болно.
Модульчлагдсан математикийн заль мэ
Жишээ нь: өглөөний 7:00 цаг (цаг/цаг - хамаагүй). 7 цагийн дараа цагийн зүү хаана байх вэ?
Модуляци
(7 + 7) mod 12=(14) mod 12=2 mod 12 [2 нь 14-ийг 12-т хуваасны үлдэгдэл юм. Тэгшитгэл 14 mod 12=2 mod 12 нь 14 цаг, 2 цагийг харна гэсэн үг. 12 цагийн цаг дээр ч мөн адил. Тэдгээр нь хоорондоо уялдаатай, гурвалсан тэнцүү тэмдгээр тэмдэглэгдсэн: 14 ≡ 2 mod 12.
Өөр нэг жишээ: өглөөний 8:00 болж байна. 25 цагийн дараа том гар хаана байх вэ?
8 дээр 25 нэмэхийн оронд 25 цаг гэдэг зүгээр л "1 өдөр + 1 цаг" гэж ойлгож болно. Хариулт нь энгийн. Тиймээс цаг 1 цагийн өмнө буюу 9:00 цагт дуусна.
(8 + 25) mod 12 ≡ (8) mod 12 + (25) mod 12 ≡ (8) mod 12 + (1) mod 12 ≡ 9 mod 12. Та 25-ыг 1 болгон хувиргаж, үүнийг нэмсэн. 8.
хүртэл
Цаг зүйрлэвэл бид цаг байгаа эсэхийг олж мэдэх боломжтоймодульчлагдсан арифметикийн дүрмүүд бөгөөд тэдгээр нь ажилладаг.
Нэмэх/Хасах
Өөрийнхөө цаг дээр хоёр удаа адилхан харагдаж байна гэж хэлье ("2:00" ба "14:00"). Хэрэв бид хоёуланд нь ижил x цагийг нэмбэл юу болох вэ? За, тэд цаг дээр ижил хэмжээгээр өөрчлөгддөг! 2:00 + 5 цаг ≡ 14:00 + 5 цаг - хоёуланд нь 7:00 харагдана.
Яагаад? Бид хоёуланд нь байгаа 2 үлдэгдэл дээр 5-ыг нэмэх боломжтой бөгөөд тэдгээр нь адилхан урагшилдаг. Бүх нийцтэй тоонуудын хувьд (2 ба 14) нэмэх хасах үр дүн ижил байна.
Үржүүлэг хэвээр үлдэх эсэхийг мэдэхэд хэцүү. Хэрэв 14 ≡ 2 (mod 12) бол бид хоёр тоог үржүүлээд ижил үр дүнд хүрч чадах уу? 3-аар үржүүлэхэд юу болохыг харцгаая.
За, 2:003 × 6:00. Гэхдээ 14:003 гэж юу вэ?
Санаач, 14=12 + 2. Тиймээс бид
гэж хэлж болно.
143=(12 + 2)3=(123) + (23)
Эхний хэсгийг (123) үл тоомсорлож болно! 14 цагийг авч явдаг 12 цагийн халилт нь хэд хэдэн удаа давтагддаг. Гэхдээ хэнд хамаатай юм бэ? Бид ямар ч байсан хэт их ачааллыг үл тоомсорлодог.
Үржүүлэх
Үржүүлэхэд зөвхөн үлдэгдэл нь чухал, өөрөөр хэлбэл 14:00 ба 2:00 цагуудад ижил 2 цаг байна. Би үржүүлэх нь модульчлагдсан математикийн хамаарлыг өөрчилдөггүйг зөн совингоор ингэж харж байна (та модуль харилцааны хоёр талыг үржүүлээд ижил үр дүнд хүрч болно).
Бид үүнийг зөн совингоор хийдэг ч нэр өгөхөд таатай байна. Та 15:00 цагт нисэх онгоцтой. Тэр14 цагаар хойшилсон. Энэ хэдэн цагт газардах вэ?
14 ≡ 2 mod 12. Тэгэхээр 2 цаг гэж бодоод үз, тэгвэл онгоц өглөөний 5 цагт газардана. Шийдэл нь энгийн: 3 + 2=5 цаг. Энэ нь энгийн модулийн үйлдлээс арай илүү төвөгтэй боловч зарчим нь адилхан.
