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



Download 199,73 Kb.
bet2/4
Sana16.12.2022
Hajmi199,73 Kb.
#888374
1   2   3   4
Bog'liq
kiber maruzaCHF1

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.

Download 199,73 Kb.

Do'stlaringiz bilan baham:
1   2   3   4




Ma'lumotlar bazasi mualliflik huquqi bilan himoyalangan ©hozir.org 2024
ma'muriyatiga murojaat qiling

kiriting | ro'yxatdan o'tish
    Bosh sahifa
юртда тантана
Боғда битган
Бугун юртда
Эшитганлар жилманглар
Эшитмадим деманглар
битган бодомлар
Yangiariq tumani
qitish marakazi
Raqamli texnologiyalar
ilishida muhokamadan
tasdiqqa tavsiya
tavsiya etilgan
iqtisodiyot kafedrasi
steiermarkischen landesregierung
asarlaringizni yuboring
o'zingizning asarlaringizni
Iltimos faqat
faqat o'zingizning
steierm rkischen
landesregierung fachabteilung
rkischen landesregierung
hamshira loyihasi
loyihasi mavsum
faolyatining oqibatlari
asosiy adabiyotlar
fakulteti ahborot
ahborot havfsizligi
havfsizligi kafedrasi
fanidan bo’yicha
fakulteti iqtisodiyot
boshqaruv fakulteti
chiqarishda boshqaruv
ishlab chiqarishda
iqtisodiyot fakultet
multiservis tarmoqlari
fanidan asosiy
Uzbek fanidan
mavzulari potok
asosidagi multiservis
'aliyyil a'ziym
billahil 'aliyyil
illaa billahil
quvvata illaa
falah' deganida
Kompyuter savodxonligi
bo’yicha mustaqil
'alal falah'
Hayya 'alal
'alas soloh
Hayya 'alas
mavsum boyicha


yuklab olish