1-amaliy mashg‘ulot
Mavzu: Kriptografiyaning matematik asosi.
Ishning maqsadi: Kriptografiyaning matematik asoslarini tashkil etuvchi amallar
bilan ishlash
. Sonning eng katta bo‘luvchisini topish uchun Yevklid algoritmidan
foydalnishni o‘rganish, hamda ushbu algoritm dasturini tuzish.
Nazariy qism
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.
Berilgan a va b 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=bq
1
+r
1
, 0 r
1
b=r
1
q
2
+r
2
, 0 r
2
1
,
…………, …………,
r
n-2
=r
n-1
q
n
+r
n
, 0 r
n
n-1
,
r
n-1
=r
n
q
n+1.
Ishning bajarilish tartibi. Quyida Yevklid algoritmi blok sxemasini ko‘rib
chiqamiz. Quyidagi misolni ko‘rib o‘tamiz.
1.
48 va 17 sonlarini EKUB ini hisoblang.
Yevklid algoritmidan foydalanib quyi dagi jadvalda masalani yechamiz.
R1
R2
q
r
48
17
2
14
17
14
1
3
14
3
4
2
3
2
1
1