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, ⁵ = 2 ∗ 2 + 1 bo‘lib, unda qoldiq 1 ga va
2
butun qism 2 ga teng bo‘ladi. Kriptografiyada 𝑎 sonni 𝑏 songa
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 ¹ ga teng bo‘lsa, modul arifmetikasida
𝑎
esa 𝑎 sonining 𝑛 modul bo‘yicha teskarisi 𝑎⁻¹𝑚𝑜𝑑𝑛 ko‘rinishida
belgilanadi. Odatiy matematikada sonni uning teskarisiga ko‘paytmasi birga teng bo‘lgani kabi, modul arifmetikasida ham soning uning teskarisiga moduldagi ko‘paytmasi birga teng bo‘ladi. Ya’ni,
𝑎⁻¹𝑚𝑜𝑑𝑛 ≡ 𝑏 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⁻¹𝑚𝑜𝑑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).