Модулярлық арифметиканың артықшылығы
Модулярлық арифметикаға кіріспе
Модулярлық арифметика көп жағдайда жай арифметикаға ұқсайды: ол коммутативті, ассоциативті және дистрибутивті заңдарға бағынады. Нақтырақ айтқанда, қосу мен көбейту операциялары бойынша n модулі арқылы алынған бүтін сандар коммутативтік сақина құрайды.
Негізгі жазылуы
a ≡ b (mod n) — “a және b сандары n модулі бойынша салыстырмалы” деп оқылады.
Салыстырмалылық шарты және модуль бойынша келтіру
Бұл қатынас бүтін a, b және n ≠ 0 үшін, егер a = b + k·n (мұндағы k — бүтін сан) болса, орындалады. Бұдан n | (a − b) екені шығады, яғни a − b саны n-ге қалдықсыз бөлінеді.
Анықтама 1
Егер a − b айырымы n-ге қалдықсыз бөлінсе, онда a және b бүтін сандары n модулі бойынша салыстырмалы деп аталады.
Модуль бойынша келтіру
Егер салыстырмалылық орындалса, b саны a-ның n модулі бойынша келтірілген мәні (қалдық класының өкілі) ретінде қарастырылады. Келтірілген мәнді табу операциясы модуль бойынша келтіру деп аталады.
Толық қалдықтар жиыны
0-ден n − 1-ге дейінгі бүтін сандар жиыны n модулі бойынша толық қалдықтар (өкілдер) жиыны деп аталады.
Мысал
n = 7 үшін: {0, 1, …, 6}
Мысал
n = 100 үшін: {0, 1, …, 99}
Негізгі қасиеттер және есептеу ережелері
Есептеулерді екі тәсілмен орындауға болады: алдымен сандарды n модулі бойынша келтіріп алып, содан кейін амалдарды қолдану; немесе алдымен амалдарды орындап, нәтижені соңында модуль бойынша келтіру. Екі жағдайда да нәтиже бірдей болады.
Формулалар
(a + b) mod n = ((a mod n) + (b mod n)) mod n
(a − b) mod n = ((a mod n) − (b mod n)) mod n
(a · b) mod n = ((a mod n) · (b mod n)) mod n
(a · (b + c)) mod n = (((a · b) mod n) + ((a · c) mod n)) mod n
Криптографиядағы маңызы және тиімділігі
Дискреттік логарифмді табу және квадрат түбірді есептеу сияқты есептердің қиындығына байланысты криптографияда n модулі бойынша көптеген әдістер қолданылады. Сонымен бірге модульдік есептеулер тиімді, өйткені олар аралық мәндер мен нәтижелердің диапазонын шектеп, есептеулерді ықшам әрі тұрақты етеді.
Қалдық класы және бағдарламалауға қатысты ескерту
Анықтама 2
Белгілі бір a санына n модулі бойынша салыстырмалы сандардың жиыны қалдық класы (сынып) деп аталады. Әдетте компьютерлік есептеулерде осы кластың ең кіші оң өкілімен жұмыс істеу ыңғайлы. Сандар теориясында мұндай өкілдің бар екені және оның a-ны n-ге бөлгендегі қалдыққа тең екені дәлелденген.
Ескерту
Кейбір бағдарламалау тілдерінде mod (немесе %) операциясы теріс сандар үшін әртүрлі анықталуы мүмкін. Сондықтан теріс мәндермен жұмыс істегенде нақты тілдің ережесін тексеру маңызды.
Артықшылықтары және қысқа мысалдар
Модулярлық арифметиканың артықшылықтары
- Есептеулер бүтін сандармен жүргізіледі.
- Нәтижелер шектеулі диапазонда қалады (0…n−1 аралығы).
Мысалдар (n = 7)
Ескерту: Кейбір тілдерде −1 mod 7 нәтижесі басқаша шығуы мүмкін; бұл нақты mod анықтамасына байланысты.