Texnologiyalari va kommunikatsiyalarini rivojlantirish vazirligi muhammad al-xorazmiy nomidagi toshkent

Modul arifmetikasi. 
Ochiq kalitli kriptotizimlar, asosan modul 
arifmetikasiga asoslangani bois, dastlab unga to‘xtalib o‘tiladi. 
Har qanday butun sonni
𝑚
∈
𝑧
ga bo‘lsak, bu songa tayin bir
qoldiq to‘g‘ri keladi. Masalan, 
5
2
= 2
∗
2 + 1
bo‘lib, unda qoldiq 1 ga va 
butun qism 2 ga teng bo‘ladi. Kriptografiyada 
𝑎
sonni 
𝑏
songa 

---

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).