64
bo‘lgandagi qoldiq
𝑟 ga teng bo‘lsa, u quyidagicha belgilanadi:
𝑎𝑚𝑜𝑑𝑏 ≡ 𝑟. Dasturlash tillarida esa 𝑎%𝑏 kabi belgilanadi.
Quyida qoldiq arifmetikasiga oid bir qancha misollar keltirilgan:
− 7𝑚𝑜𝑑3 ≡ (3 ∗ 2)𝑚𝑜𝑑3 + 1𝑚𝑜𝑑3 ≡ 0 + 1 ≡ 1;
− 14𝑚𝑜𝑑3 ≡ (3 ∗ 4)𝑚𝑜𝑑3 + 2𝑚𝑜𝑑3 ≡ 0 + 2 ≡ 2;
− 2𝑚𝑜𝑑3 ≡ (0 ∗ 3)𝑚𝑜𝑑3 + 2𝑚𝑜𝑑3 ≡ 2;
− 5𝑚𝑜𝑑7 ≡ 5;
− −2𝑚𝑜𝑑5 ≡ (−2 + 5)𝑚𝑜𝑑5 ≡ 3𝑚𝑜𝑑5 ≡ 3;
− −7𝑚𝑜𝑑3 ≡ (−7 + 3)𝑚𝑜𝑑3 ≡ −4𝑚𝑜𝑑3 ≡ (−4 +
3)𝑚𝑜𝑑3 ≡ −1𝑚𝑜𝑑3 ≡ (−1 + 3)𝑚𝑜𝑑3 ≡ 2
Bundan tashqari ochiq kalitli kriptografiyada sonning modul
bo‘yicha teskarisini hisoblash muhim hisoblanadi. Masalan, odatiy
matematikada
𝑎
sonining teskarisi
1
𝑎
ga teng bo‘lsa, modul
arifmetikasida esa
𝑎 sonining 𝑛 modul bo‘yicha teskarisi 𝑎
−1
𝑚𝑜𝑑𝑛
ko‘rinishida belgilanadi. Odatiy matematikada sonni uning teskarisiga
ko‘paytmasi birga teng bo‘lgani kabi, modul
arifmetikasida ham sonning
uning teskarisiga moduldagi ko‘paytmasi birga teng bo‘ladi. Ya’ni,
𝑎
−1
𝑚𝑜𝑑𝑛 ≡ 𝑏 bo‘lsa, u holda (𝑎 ∗ 𝑏)𝑚𝑜𝑑𝑛 ≡ 1 tenglik o‘rinli bo‘ladi.
Izoh. Kriptografiyada modul sifatida (ya’ni, bo‘luvchi) faqat tub
sonlardan foydalanish talab etiladi. Ya’ni,
amodn tenglikdagi n har
doim tub bo‘lishi lozim.
Aytaylik, 3 sonining 7 moduldagi teskarisini topish talab etilsin.
Ya’ni,
𝑥 ni topish talab etilsin: 3
−1
𝑚𝑜𝑑7 ≡ 𝑥. Yuqoridagi
tenglik
(3 ∗ 𝑥)𝑚𝑜𝑑7 ≡ 1 dan foydalanib, 𝑥 ning o‘rniga son qo‘yib natijani
hisoblash mumkin. Lekin ushbu jarayon ko‘p vaqt talab etadi (ayniqsa
katta sonlarda).
