Модулярлық арифметиканы есептеу туралы қазақша реферат
Модулярлық арифметика көбінде жай арифметикаға ұқсас: ол коммутативті, қауымдастықты, дистрибутивті. Толығырақ айтатын болсақ, қосу мен көбейту операцияларын қолданатын n модулі бойынша бүтін сандар коммутативті, қауымдастықты, дистрибутивті заңдарын қолдай отырып, коммутативтік сақина құрайды.
Негізінен модулярлық арифметиканың жазылуы төмендегідей түрде:
а ≡ b (mod n), бұл «n модулі бойынша а және b сандары салыстырмалы» деп оқылады.
Бұл ара қатынас бүтін мәндер а,b және n ≠ 0, егер а = b + k*n (кейбір к бүтін сандарына) үшін тура.
Бұдан шығатыны n | (a-b), бұл «n (a-b)-ға бөлінеді» деп оқылады.
Егер бұл қатынас орындалса, онда b санын n модулі бойынша а-ның шегеру саны деп аталады. Шегеру санын табу операциясын модуль бойынша келтіру деп аталады.
Анықтама 1 Егер a-b айырымы n-ге қалдықсыз бөлінетін болса а және b бүтін сандарын n модулі бойынша салыстырмалы деп аталады.
0-ден n — 1-ге дейінгі бүтін сандардың жиынтығын n бойынша модулін шегеруінің толық жиынтығы деп атайды.
n = 7, { 0, 1, … , 6 }
n = 100, { 0, 1, … , 99 }.
Дұрысы біз алдымен n модулі бойынша шығарып алып, содан операцияны орындауымызға болады немесе алдымен операцияны, содан кейін 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
Дискреттiк логарифм және түбiр квадратын есептеу қиын болғандықтан, криптография n модулi бойынша көптеген есептер қолданылады. Сонымен қатар, модуль бойынша есептеулермен жұмыс iстеу тиiмдiрек, өйткенi олар барлық аралық өлшем мен нәтиженiң диапазоның шектейдi.
Анықтама 2 Модулі бойынша белгілі бір а санымен салыстырмалы сандардың жиыны сынып деп аталады. Ол деп белгіленеді.
Мысал: 6 модулі бойынша сыныбы:
Модулярлық арифметиканы компьютерлік есептеулерге қолдану үшін біз тек қана шектелген мәндер диапазонын қарастыруымыз керек. Сондықтан негізінен сыныбындағы ең кіші оң санымен жұмыс істейді. Сандар теориясында мұндай санның бар екендігі және де ол а-ны n-ге бөлгендегі қалдыққа тең екендігі дәлелденген.
Ескерту. Программалау тілдерінде mod функциясы басқаша анықталуы мүмкін.
Модулярлық арифметиканың артықшылығы:
1) Бүтін сандармен жұмыс істейміз;
2) Есептердің барлық нәтижелері супер өрісте орналасқан.
Мысалы. 13 mod 7 = 6, 0≤n≤n-1
7 mod 7 = 0, 4 mod 7 = 4, -1 mod 7 = 6.