1-amaliy mashg’ulot Mavzu: Kriptografiyaning matematik asosi. Ishning maqsadi



Download 0,58 Mb.
bet4/8
Sana30.04.2022
Hajmi0,58 Mb.
#595358
1   2   3   4   5   6   7   8
Bog'liq
1-6 amaliy ishlar.

Topshiriqlar.

  1. Kengaytirilgan Yevklid algoritmi yordamida quyidagilarni yeching.

  1. 4 va 7

  2. 291 va 42

  3. 54 va 321

  4. 400 va 60

  5. 21 va 14

  6. 88 va 220

  7. 401 va 700

  8. 300 va 42

  1. Quyidagi chiziqli diofant tenglamani yeching

  1. 25x+10y=15

  2. 19x+13y=20

  3. 14x+21y=77

  4. 40x+16y=88

  1. Har bir talaba chiziqli diofant teglamani ixtiyoriy dasturlash tilida dasturini tuzadi.

Hisobot tarkibi
Hisobot quyidagi ma’lumotlardan tarkib topgan bo‘lishi lozim:
Nazariy qismda keltirilgan algoritmning dasturiy ta’minotidan foydalanish jarayonidagi olingan rasmlari va ularga izoh.
Yaratilgan dasturiy ta’minotning dasturiy kodi.
Nazorat savollari
Yevklid algoritmi
Kengaytirilgan Yevklid algoritmi
Chiziqli diofant tenglamalar
Chiziqli diofant tenglama xususiy va umumiy yechimlari.
3-amaliy mashg’ulot
Mavzu: Modul arifmetikasi xossalari. Modul arifmetikasi ustida amallar bajarish.
Sonlar nazariyasi elementlari
Sonlar nazariyasi kriptografik masalalarning tadqiq qilinishi hamda ularning yechimlarida muhim rol o‘ynaydi.
Natural sonlar to‘plamini N ={1, 2,3, … } va butun sonlar to‘plamini Z={0, 1, 2, 3, … } ko‘rinishda belgilaymiz.
Noldan farqli bo‘lgan a soni va b sonlar Z –to‘plamga tegishli, ya’ni
a, b Z bo‘lib, a 0 bo‘lsin, agarda shunday s soni mavjud bo‘lib, b =as tenglik bajarilsa, u holda a soni b sonini bo‘ladi, deyiladi.
3.8.1. Eng katta umumiy bo‘luvchi
Berilgan a va v sonlarni bo‘luvchi butun son, ularning umumiy bo‘luvchisi deyiladi. Umumiy bo‘luvchilar ichida eng kattasi eng katta umumiy bo‘luvchi (EKUB) deyiladi va EKUB(a, b) ko‘rinishda belgilanadi. Agarda a va b sonlarning eng katta umumiy bo‘luvchisi 1, EKUB (a, b)=1 bo‘lsa, a va b sonlar o‘zaro tub deyiladi. Eng katta umumiy bo‘luvchilarni topishga oid tasdiqlarni keltiramiz.
1-lemma. Agar b soni a sonini bo‘lsa, u holda bu sonlarning eng katta umumiy bo‘luvchisi EKUB (a, b)= b, ya’ni a sonining umumiy bo‘luvchilari to‘plami b sonining umumiy bo‘luvchilari to‘plami bilan ustma-ust tushadi.
2-lemma. Agar a=bq+c bo‘lsa, u holda a va b sonlarining eng katta umumiy bo‘luvchisi b va s sonlarining eng katta umumiy bo‘luvchisi bilan ustma-ust tushadi, ya’ni EKUB (a, b)= EKUB (b, c): a va b sonlarining umumiy bo‘luvchilari to‘plami b va s sonlarining umumiy bo‘luvchilari to‘plami bilan ustma-ust tushadi.
Yuqorida keltirilgan lemmalardan EKUBni topish – Yevklid algoritmi kelib chiqadi.
Haqiqatan ham quyidagi bo‘lish amallarini bajaramiz:
a=bq1+r1, 0 r1b=r1q2+r2, 0 r2…………, …………,
rn-2=rn-1 qn+rn, 0 rnrn-1 =rnqn+1.
U holda EKUB (a, b)= EKUB (b, r1)=…=(rn-2, rn-1)= rn .
Modulli arifmetikada biz faqat bitta chiqish natijasiga qiziqamiz - qolgan . Biz qoldiq haqida qayg‘urmaymiz. Boshqacha qilib aytganda, ni ga bo‘lganda, biz faqat qoldiq qiymati kanligiga qiziqamiz. Bu yuqoridagi tenglama tasvirini ikkita va a va n chiqishlari bilan bitta chiqish r bilan ikkilik operator sifatida ifodalashimiz mumkinligini anglatadi.
Modul bo‘yicha amallar
Yuqorida aytilgan binary amallar modul operatori deb ataladi va mod sifatida belgilanadi. Ikkinchi kirish modul deb ataladi. Chiqish qoldiq deyiladi. 2.9-rasmda modulo operatori bilan taqqoslash nisbati ko‘rsatilgan.

2.9- rasm. Bo‘lish tenglamasi va modul arifmetikasi o‘rtasidagi munosabat.
Shaklda ko‘rsatilgandek. 2.9, modulo operatori to‘plamidan butun sonni va musbat modulni tanlaydi. Operator salbiy bo‘lmagan qoldiqni aniqlaydi . Aytishimiz mumkinki
Chekli maydonda amallar bajarish
Modul amalining natijasi har doim 0 dan n gacha bo‘lgan butun sondir. Boshqa so‘zlar bilan aytganda, mod n ning natijasi har doim n dan katta bo‘lmagan butun son. Aytishimiz mumkinki, modulli operatsiya modulli arifmetikada n yoki qoldiqlari tizimi sifatida tushunilishi mumkin bo‘lgan to‘plamni yaratadi. Ammo shuni esda tutishimiz kerakki, bitta butun sonlar to‘plami mavjud bo‘lsa ham, cheksiz ko‘p sonli qoldiqlar to‘plami bor, lekin n ning har bir qiymati uchun bittadan. 2.10-rasmda va , va to‘plamlari ko‘rsatilgan.

2.10 rasm to‘plamga misollar
Aslida, ikkita operatorlar to‘plami ishlatiladi: birinchi to‘plam ikkilik operatorlardan biri; ikkinchisi - modulo operatorlari. Biz ish tartibini ta’kidlash uchun qavslardan foydalanishimiz kerak. Ko‘rsatilganidek, kirishlar ( va ) yoki a’zolari bo‘lishi mumkin.
Xossalari
Yuqorida biz uchta ikkilik operatorlar uchun ikkita kirish, taqqoslaganda yoki ma’lumotlarini modulda ishlatishi mumkinligini aytib o‘tdik. Quyidagi xususiyatlar uchta uchta ikkilik operatorlarni bajarishdan oldin -ga ikkita kirishni xaritalashga imkon beradi.

Mod amali xossalari
xossa 
xossa
xossa
Butun a va b sonlari modul n bo‘ycha taqqoslanadigan deyiladi, agarda ularni n ga bo‘lganda qoladigan qoldiqlari teng bo‘lsa, hamda, a b(mod n) deb yoziladi. Bundan esa a va b sonlar ayirmasining n ga qoldiqsiz bo‘linishi kelib chiqadi.
Qoldiqni ifodalash uchun ushbu b=a mod n tenglikdan foydalaniladi, hamda b=a mod n tenglikni qanoatlantiruvchi b sonini topish a sonini modul n bo‘yicha keltirish deyiladi.
Biror n modul bo‘yicha qo‘shish, ayirish va ko‘paytirish amallariga nisbatan quyidagi kommutativlik, assotsiativlik va distributivlik munosabatlari o‘rinli:
(a+b)mod n=((a mod n)+(b mod n))mod n,
(a-b)mod n=((a mod n)-(b mod n))mod n,
(a·b)mod n=((a mod n) · (b mod n))mod n,
(a· (b+c)mod n=(((a·b) mod n)+(a·c) mod n))mod n.
Quyida modul amallari bilan bog‘liq bir nechta misollar keltirib o‘tilgan:
b=a mod n tenglikda a>n>0 bo‘lgan holda, natijani hisoblash uchun a ni n ga bo‘lib, qoldig‘i olinadi. Masalan, 12mod5=2; 15mod6=3;
b=a mod n tenglikda n>0 va a<0 bo‘lgan holda, a ga toki yig‘inda noldan katta bo‘lgunga qadar n qo‘shiladi. Masalan, -5mod6=1; -12mod5=3;
b=a mod n tenglikda a kasr son bo‘lgan holda, tenglik quyidagi (b*c)modn=1 tenglikka keltiriladi. a=1/c ga teng bo‘lsa, s butun son bo‘ladi. Olingan tenglikdan b ning o‘rniga qiymat berish orqali tenglik bajaralishi tekshiriladi. Tenglik bajarilsa, unda b ga o‘zlashtiriladi. Bu usul ko‘p vaqt talab etadi. Shuning uchun amalda Evklidning kengaytirilgan aalgoritmining xususiy holidan foydalaniladi. Ushbu algoritmning ketma-ketligi quyidagicha:
(e*d)modn=1 tenglikda e va n ma’lum bo‘lib, d ni topish talab etilsin. Buning uchun quyidagi belgilanishlar kiritiladi a=n va b=e. Uchta elementdan iborat bo‘lgan, uchta to‘plam quyidagicha tuziladi:
U={a, 1, 0}, V={b, 0, 1}, T={U[1]modV[1], U[2]-[U[1]/V[1]]*V[2], U[3]-[U[1]/V[1]]*V[3]}. Bu yerda dastlabki qiymatlardan U va V to‘plamlar hosil qilinadi va ular asosida T to‘plam hisoblanadi. Agar T to‘plamning birinchi elementi T[1]=1 ga teng bo‘lganda hisoblanishlar to‘xtatiladi va d=T[3] ga teng bo‘ladi. Aks holda, V to‘plamning qiymatlari U to‘plamga, T to‘plamning qiymatlari V to‘plamga o‘zlashtiriladi (U=V, V=T) va ular asosida yangidan T to‘plam hisoblanadi va yana T[1]=1 tengiligi tekshiriladi. Ushbu ketma-ketlik T[1]=1 tenglik bajarrilgunga qadar amalga oshiriladi va teng bo‘lgan holda d=T[3] deb olinadi va hisoblashlar to‘xtatiladi.


T.J.R

Modulning xususiyatlari

n>0 va a<0 holda
b=a mod n ni toping ?

(e*d)modn=1
u va n berilgan holda d ni toping ?




a=3; b=-4; c=5; n=8;

a=-45; n=7;

n=17; e=2;




a=6; b=-7; c=8; n=8;

a=-54; n=8;

n=19; e=4;




a=12; b=-21; c=13; n=8;

a=-5; n=60;

n=17; e=3;




a=14; b=-12; c=13; n=8;

a=-55; n=21;

n=23; e=4;




a=15; b=-16; c=17; n=8;

a=-56; n=50;

n=23; e=6;




a=51; b=-21; c=12; n=8;

a=-52; n=105;

n=23; e=12;




a=51; b=-10; c=53; n=8;

a=-55; n=4;

n=23; e=2;




a=89; b=-10; c=56; n=8;

a=-63; n=6;

n=29; e=6;




a=11; b=-12; c=13; n=8;

a=-36; n=89;

n=29; e=5;




a=45; b=-54; c=5; n=8;

a=-65; n=56;

n=31; e=4;




a=5; b=-96; c=69; n=8;

a=-89; n=98;

n=31; e=8;




a=52; b=-5; c=5; n=8;

a=-89; n=21;

n=17; e=9;




a=9; b=-8; c=5; n=8;

a=-100; n=33;

n=50; e=17;




a=12; b=-15; c=18; n=8;

a=-102; n=25;

n=37; e=19;




a=40; b=-42; c=30; n=8;

a=-104; n=23;

n=41; e=7;




a=50; b=-9; c=61; n=8;

a=-67; n=23;

n=41; e=6;




a=8; b=-9; c=15; n=8;

a=-47; n=3;

n=43; e=4;




a=56; b=-65; c=20; n=8;

a=-89; n=12;

n=43; e=11;




a=40;b=-50; c=10; n=8;

a=-45; n=24;

n=47; e=8;




a=2; b=-3; c=5; n=8;

a=-74; n=69;

n=47; e=6;




a=52;b=-63; c=41; n=8;

a=-105; n=501;

n=61; e=31;




a=78; b=-8; c=5; n=8;

a=-91; n=19;

n=67; e=17;




a=7; b=-8; c=41; n=8;

a=-58; n=85;

n=67; e=4;




a=45; b=-81; c=51; n=8;

a=-96; n=69;

n=13; e=2;


Download 0,58 Mb.

Do'stlaringiz bilan baham:
1   2   3   4   5   6   7   8




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