Бүх нийтлэлүүд
2026.05.145 min read#математикбаcsонол#modular arithmetic#Модулийн арифметик#үлдэгдэл#үлдэгдэлтэй хуваах#crypto#крипто#mathematic#математик
Модулийн арифметик Бүгд (Үлдэгдлийн Математик ба Криптографийн Үндэс)
М.Энх
Багш
М.Энх
Багш
Модулийн арифметик бол хуваах үйлдлийн зөвхөн үлдэгдлийг нь тоодог арга юм. 17-г 5-т хуваагаад 3.4 гарахад энэний 3 нь байна уу 2 байна уу огт хамаагүй. Таслалаас хойших тоо л гол нь гэсэн үг.
a гэсэн тоог n гэсэн тоонд хуваахад гарах үлдэгдлийг олох үйлдлийг mod гэж тэмдэглэдэг. Энд n-ийг модуль гэж нэрлэнэ. Жишээлбэл, 17÷5 = 3.4 буюу 3 бүхэл, 2 үлдэнэ. Үүнийг математикт дараах байдлаар бичнэ:
17 mod 5 = 2
17-н 5 модуль нь 2 гэсэн үг юм.. Эсвэл өөрөөр “төсөөтэй” (congruent) гэсэн ойлголтыг ашиглан:
17 ≡ 2 (mod 5)
Энэ нь “17 нь 5 модулиар 2-той төсөөтэй” гэж уншигдах юм. 17 ба 2 гэсэн хоёр тоог 5-д хуваахад ижил үлдэгдэл өгдөг гэсэн утгатай.
Модулийн арифметикийг ойлгох хамгийн хялбар жишээ бол цаг юм. Бид 12 цагийн систем ашигладаг. Хэрэв одоо цаг өглөөний 9 цаг болж байвал 5 цагийн дараа хэдэн цаг болох вэ?
9 + 5 = 14
Гэвч бид “14 цаг” гэж хэлдэггүй, харин өдрийн “2 цаг” гэж хэлдэг. Энэ нь үнэндээ модуль 12-той арифметик юм.
14 mod 12 = 2 буюу 14 ≡ 2 (mod 12)
Цаг 12-т хүрээд дахин 1-ээс эхэлдэг шиг модуляр арифметикт тоонууд модульдаа хүрээд “шинээр эхэлдэг”. За дараахыг нэг бодох гээд үз. 59 mod 12 = ?
Модулийн арифметикт стандарт арифметикийн нэмэх, хасах, үржих үйлдлүүдийг хийж болно.
m модуль өгөгдсөн гэж үзье.
1. Модулийн нэмэх үйлдэл:
(a + b) mod m = ((a mod m) + (b mod m)) mod m
Жишээ: (15 + 17) mod 7 үйлдлийг бодъё.
15 mod 7 = 1
17 mod 7 = 3
(1 + 3) mod 7 = 4 mod 7 = 4
Шалгая:
15 + 17 = 32
32 mod 7 = 4 (32-ыг 7-д хуваахад 4 үлдэнэ).
2. Модулийн үржих үйлдэл:
(a b) mod m = ((a mod m) (b mod m)) mod m
Жишээ: (12 * 13) mod 5 үйлдлийг бодъё.
12 mod 5 = 2
13 mod 5 = 3
(2 * 3) mod 5 = 6 mod 5 = 1
Шалгая:
12 * 13 = 156
156 mod 5 = 1 (156-г 5-д хуваахад 1 үлдэнэ).
3. Модулийн зэрэг дэвшүүлэх (Modular Exponentiation):
a^b mod m – Энэ нь a-г b зэрэгт дэвшүүлээд m модуль авах үйлдэл юм. Криптографид маш том тоонууд дээр энэ үйлдлийг хийдэг тул үр дүнг алхам алхмаар бодох нь илүү үр дүнтэй байдаг.
Жишээ: 5^3 mod 6 үйлдлийг бодъё.
5^3 = 125
125 mod 6 = 5 (125-ыг 6-д хуваахад 5 үлдэнэ).
Өөр арга:
5^1 mod 6 = 5
5^2 mod 6 = 25 mod 6 = 1 (5-н 1, 2 зэргийн үлдэгдлийг хооронд нь үржүүлэн 6-р хуваахад үлдэгдэлийн хувьд адил байх ёстой).
5^3 mod 6 = (5^2 5^1) mod 6 = ((5^2 mod 6) (5^1 mod 6)) mod 6 = (1 * 5) mod 6 = 5
4. Модулийн урвуу (Modular Inverse):
Модуляр хуваах үйлдэл нь шууд тодорхойлогддоггүй. Үүний оронд “модулийн урвуу”-г ашигладаг. a тооны m модулиарх урвуу нь a' гэсэн тоо байх бөгөөд дараах нөхцөлийг хангана:
(a * a') mod m = 1 буюу a * a' ≡ 1 (mod m)
Модулийн урвуу нь зөвхөн a ба m хоёр харилцан анхны тоо (ХИЕХ(a, m) = 1) байх үед л оршин байна. Энэ нь криптографд нууц түлхүүр бодож олох зэрэгт чухал үүрэгтэй.
Жишээ: 3-ын mod 7-оорх урвууг олъё.
Бид 3 * a' ≡ 1 (mod 7) байх a'-г олох хэрэгтэй.
3 * 1 = 3 ≡ 3 (mod 7)
3 * 2 = 6 ≡ 6 (mod 7)
3 * 3 = 9 ≡ 2 (mod 7)
3 * 4 = 12 ≡ 5 (mod 7)
3 * 5 = 15 ≡ 1 (mod 7)
Иймд 3-ын mod 7 урвуу нь 5 байна. 15-г 7-р хуваахад 1 үлдэх бөгөөд энэ нь өөрөө 3 5 гэсэн тоог үржигдэхүүн болон задардаг.
Модулийн арифметик гэх сүртэй нэр ашиглаж буй боловч бидний өдөр тутамдаа ашигладаг цаг маань л байгаа. Тиймээс үндсэн томъёо зэрэгт нь төөрөгдөлгүй цагаа л бодоход болно.
“Нэг чигийн функц” (One-Way Function) үүсгэх боломж: Криптографийн гол тулгуур зарчмуудын нэг бол “нэг чигтээ бодоход хялбар, харин буцааж бодоход маш хэцүү” байдаг математик үйлдлүүд юм. Модуляр арифметик нь ийм функцийг бий болгоход төгс тохирдог.
Тооцооллын хязгаарыг тогтоож өгдөг: Криптографийн үйлдлүүд маш том тоонууд дээр хийгддэг. Хэрэв модуляр арифметик ашиглахгүй бол зэрэг дэвшүүлэх үйлдэл хийхэд үр дүн нь санах ойд багтахааргүй, удирдахад бэрх асар том тоо болж хувирна. Жишээлбэл, 314^159 гэдэг бол олон зуун оронтой тоо. Харин 314^159 mod 1013 гэсэн үйлдлийн үр дүн нь үргэлж 0-с 1012-ын хооронд л байна. Модуляр арифметик нь үйлдлийн үр дүнг тодорхой, удирдах боломжтой хүрээнд барьж, тооцооллыг үр ашигтай болгодог.
Цикл үүсгэдэг шинж чанар: Модуляр арифметикт тоонууд тодорхой модуль дотор “эргэлдэж” байдаг. Энэхүү цикл шинж чанарыг ашиглан тодорхой математик бүтэц, групп үүсгэж болдог. Криптографийн протоколууд нь эдгээр математик бүтцийн найдвартай, батлагдсан шинж чанарууд дээр тулгуурлан зохиогддог.
Ийнхүү бид “үлдэгдлийн математик” буюу модулийн арифметикийн ертөнцөөр хамтдаа аяллаа. Энэ нь зүгээр нэг тооны онолын хийсвэр ойлголт биш, харин бидний өдөр тутмын дижитал амьдралын аюулгүй байдлыг хамгаалж байдаг технологийн зүрх нь юм.
Таны банкны нууц үг, зурвас, онлайн худалдан авалт гээд энэ бүхний цаана модулийн арифметикийн “нэг зүгтээ хялбар, буцаагаад бодоход бараг боломжгүй” гэх гайхамшигт шинж чанар нуугдаж байдаг. Дараагийн удаа та https:// гэсэн хамгаалалттай вэбсайт руу орохдоо энэхүү ухаалаг математикийн ачаар таны мэдээлэл хэрхэн хамгаалагдаж байгааг санаарай.
Тооны ертөнцөд зөвхөн нэмэх, хасах үйлдлээс хавьгүй илүү гүн гүнзгий, сонирхолтой нууцууд оршдог бөгөөд модуляр арифметик бол түүний зөвхөн нэгээхэн хэсэг нь билээ.