Bajardi: 414-21 guruh talabasi Choriyev Fazliddin Tekshirdi: Safoyev Nuriddin Toshkent – 2022

Soat arifmetikasi

Ikki butun son x va n uchun, “x mod n” tushunchasi qoldigʻini hisoblashni anglatadi, yaʼni x n boʻlgandagi qoldiq
Shuningdek biz buni “x modulo n” deb ham atashimiz mumkin.
7 mod 6 = 1
33 mod 5 = 3
33 mod 6 = 3
51 mod 17 = 0
17 mod 6 = 5
Modul boʻyicha qoʻshish
Belgilashlar va faktlar

• 
  7 mod 6 = 1
  
• 
  7 = 13 = 1 mod 6
  
• 
  ((a mod n) + (b mod n)) mod n = (a + b) mod n
  

((a mod n)(b mod n)) mod n = ab mod n
Qoʻshish xossasi

• 
  3 + 5 = 2 mod 6
  
• 
  2+ 4 = 0 mod 6
  
• 
  3+ 3 = 0 mod 6
  
• 
  (7 + 12) mod 6 = 19 mod 6 = 1 mod 6
  
• 
  (7 + 12) mod 6 = (1 + 0) mod 6 = 1 mod 6
  

Modul boʻyicha koʻpaytirish
Koʻpaytirish xossalari

• 
  3 * 4 = 0 (mod 6)
  
• 
  2 * 4 = 2 (mod 6)
  
• 
  5 * 5 = 1 (mod 6)
  
• 
  (7 * 4) mod 6 = 28 mod 6 = 4 mod 6
  

Teskari tartibdagi modul

• 
  Manfiy sonning moduli x mod n, quyidagicha belgilanadi : x mod n-2 mod 6 = 4
  
• 
  Multiplikativ teskari x mod n, quyidagicha belgilanadi: x-1 mod n3-1 mod 7 = 5, sababi 3 5 = 1 mod 7
  

Kengaytirilgan Yevklid algoritmi
Kengaytirlgan Yevklid algoritmi. Kengaytirlgan Yevklid algoritmi RSA kriptotizimi ochiq kaliti «ye» - ni topishda d*e=1(modφ(n)) tenglamaga duch kelinib, uni yechish bevosita ax + by = d , d = EKUB(a,b) tenglamaning butun yechimlarini topish masalasiga ekvivalent hamda bu algoritmga ko’ra berilgan a-soniga modn bo’yicha teskari elementni topish imkonini beradi. Shuning uchun ham bu algoritm ishlash prinsiplarini keltirish muhim.
Teorema: Aytaylik, a va b natural sonlar, d = EKUB(a,b) bo’lsin. U holda shunday α va β butun sonlar topiladiki

tenglik o’rinli bo’ladi.
Demak, bu algoritm nafaqat ikkita natural sonning EKUB ini, balki yoyilmadagi α va β koeffisentlarni ham topish imkonini berar ekan. Shunisi bilan ham aslida Yevklid algoritmidan farqlanadi.
Kengaytirilgan Yevklid algoritmiga muvofiq topiladigan α va β butun sonlar, quyidagi Diafant tenglamasining

butun yechimlari hisoblanadi. Bundan RSA algoritmining ochiq kalitiga ko’ra maxfiy kalitini hisoblashda foydalanish mumkin. Shu sababli bu algoritm ishlash qadamlari bilan yaqindan tanishib chiqiladi.
Faraz qilaylik, a va b sonlarning EKUBni topishda quyidagi ketma-ketlik qaralayotgan bo’lsin:

Bu yerda,
x1, x2,….x n-1 va u1, u2……yn -1
sonlarini topish kerak bo’lsin. Bu sonlar quyidagi formula yordamida topiladi:
xj = x j-2 – q j x j-1 va uj = y j - 2 - qj yj-1
bu yerda,
x -1=1 , u -1 =0 , x0 =0 , u0 =1.
Kerakli ma’lumotlarni quyidagi jadval orqali aniqlash mumkin:

Jadvalning oxirgi ustunida keltirilgan ikki qiymat izlanayotgan alfa va beta koeffisentlar, yani α= x n-1 , β= un-1 bo’ladi.


Misol. Yevklid algoritmini qo’llab EKUB (6188,4709) va α,β- qiymatlar topilsin.
Yevklid algoritmi qadamlariga muvofiq:

demak,
r5=17
soni 6188 va 4709 sonlarining EKUBi deb e’lon kilinadi, ya’ni:
EKUB (6188, 4709)=17 .
Kengaytirilgan Yevklid algoritmiga ko’ra:
6188*α + 4709*β=17.
α=?, β=? topilsin:
yuqorida keltirilgan ifodani quyidagicha yozish mumkin:
yoki:

Ya’ni:
6188*121+4709* (- 159)=17; demak, α=121; β= -159
Javob: α=121, β= -159


Misol: 3^-1 (mod7)=x ni topish talab etilgan bo’lsin. Yuqorida keltirilgan algoritmga ko’ra
7=3∗2+1
3=1∗3+0
Qoldig’i nolga teng bo’lgan tenglikdan oldingi tenglikdan boshlab quyidagicha teskari yozish amalga oshiriladi:
1 = 7 −(3∗2) = 7 + (−2∗3)=7∗1 + (−2∗3)
Yuqoridagi tenglikni ikki tomonini modulga (mod7) olinsa quyidagi tenglikga ega bo’linadi:
((7*1)mod7 + (-2*3)mod7)mod7 = 1mod7
yoki
(-2*3)mod7)mod7=1mod7 = 1.
Ushbu tenglikni (3*x)mod7 =1 taqqoslash orqali 𝑥= −2 ga tengligini yoki -2mod7=5 ligini toppish mumkin. Ya’ni (3*5)mod7 = 1 tenglikni qanoatlantiradi.