Kriptografik usullar

5.2. Chegirmalar sinfi. m natural songa bo’linganda bir xil r qoldiq qoladigan barcha butun sonlar to’plami m modul bo’yicha sonlar sinfini tashkil qiladi. Bu sinfning har bir soni umumiy holda mk+r, k∈Z ko’rinishda yoziladi. Barcha sinflar soni m ga teng.
Sinfning ixtiyoriy soni m modul bo’yicha chegirma deyiladi (shu sinfning boshqa sonlariga nisbatan).
Har bir sinfdan ixtiyoriy ravishda bittadan olingan sonlar to’plami berilgan m modul bo’yicha chegirmalarning to’la sinfi deyiladi.
Odatda chegirmalarning to’la sinfi sifatida berilgan m bo’yicha eng kichik manfiy bo’lmagan chegirmalar, ya’ni 0, 1, 2,..., m - 1 sistema olinadi.
Ba’zan berilgan m modul bo’yicha chegirmalardan absolyut qiymati bo’yicha eng kichik musbat bo’lmagan chegirmalarning to’la sistemasi ham qaraladi: -(m-1), -(m-2),..., -2, -1, 0. m modul bo’yicha absolyut qiymati jihatidan eng kichik chegirmalarning to’la sinfi ham ishlatiladi. Masalan, m = 7 bo’lganda bu sistema -3, - 2, -1, 0, 1, 2, 3 chegirmalardan iborat bo’ladi; m = 8 bo’lganda esa -3, -2, -1, 0, 1, 2, 3, 4 yoki –4, -3, -2, -1, 0, 1, 2, 3 chegirmalardan tashkil topadi.
Chegirmalarning to’la sistemasidan olingan va m modul bilan o’zaro tub bo’lgan chegirmalar m modul bo’yicha chegirmalarning keltirilgan sistemasi deyiladi. Kelitirilgan sistemada chegirmalar soni φ(m)- Eyler funksiyasining qiymatiga teng.
Chegirmalarning to’la sistemasidagi kabi keltirilgan sistemaning ham uch turi ishlatiladi: eng kichik musbat chegirmalarning keltirilgan sistemasi, absolyut qiymati bo’yicha eng kichik manfiy chegirmalarning keltirilgan sistemasi va absolyut qiymati bo’yicha eng kichik chegirmalarning keltirilgan sistemasi.
x₁, x₂,..., x_s butun sonlar sistemasi s =φ (m) va i ≠j,( x_i,m)=1 da x_i ≡x_j (mod m) bo’lganda va faqat shu holda m modul bo’yicha chegirmalarning to’la sistemasidan iborat bo’ladi.
(a, m) = 1 bo’lganda ax + b chiziqli formaning qiymatlari m modul bo’yicha chegirmalarning to’la sistemasidan iborat bo’lishi uchun x qabul qiladigan qiymatlar ham chegirmalarning to’la sistemasidan iborat bo’lishi zarur va yetarlidir.
x₁, x₂,..., x_s butun sonlar sistemasi s =φ (m) va i ≠j,( x_i,m)=1 da x_i ≡x_j (mod m) bo’lganda va faqat shu holda m modul bo’yicha chegirmalarning keltirilgan sistemasidan iborat bo’ladi.
(a, m) = 1 bo’lganda ax chiziqli formaning qiymatlari m modul bo’yicha chegirmalarning keltirilgan sistemasidan iborat bo’lishi uchun x qabul qiladigan qiymatlar ham chegirmalarning keltirilgan sistemasidan iborat bo’lishi zarur va yetarlidir.
m > 1 va (m, a) = 1 bo’lganda quyidagi taqqoslama o’rinli:
a ^{φ (m)} ≡1 (mod m),
bu yerda φ (m) –Eyler funksiyasi (Eyler te oremasi).
p tub son va (a, p) = 1 bo’lganda quyidagi taqqoslama o’rinli:
a^p-1 ≡1 (mod m), (Ferma teoremasi).
a butun sonni o’zida saqlaydigan m bo’yicha chegirmalar sinfini a mod m bilan belgilaymiz. Demak,
a mod m = a + mZ = {a + km k ∈Z}.
Z/mZ bilan m modul bo’yicha barcha chegirmalar sinflari to’plamini belgilaymiz:
Z/mZ = {0 mod m, 1 mod m,..., (m-1) mod m}.
Bu to’plamda qo’shish va ko’paytirish amallarini quyidagi tengliklar orqali kiritiladi:
a mod m + b mod m = (a + b) mod m,
(a mod m) ⋅(b mod m) = ab mod m.
(Z/mZ, +) – abel gruppasidan, hamda Z gruppaning mZ qism gruppa bo’yicha faktor gruppasidan iborat bo’lib, m modul bo’yicha chegirmalar sinfining additive gruppasi deyiladi.
(Z/mZ, +, ⋅) – birlik elementli kommutativ xalqadan iborat bo’lib, m modul bo’yicha chegirmalar sinfinig xalqasi deyiladi.
Agar (m, a) = 1 bo’lsa, m mod a sinf a modul bilan o’zaro tub bo’lgan chegirmalar sinfi deyiladi.
m modul bilan o’zaro tub bo’lgan chegirmalar sinflari to’plami ko’paytirishga nisbatan abel gruppasi tashkil etadi va u m modul bilan o’zaro tub bo’lgan chegirmalar sinflarining multiplikativ gruppasi deyiladi.
Agar ab ≡1 (mod m) bo’lsa, a chegirma b chegirmaga m modul bo’yicha
teskari deyiladi.