Международная научно-техническая конференция «Практическое применение технических и цифровых технологий и их инновационных решений», татуфф, Фергана, 4 мая 2023 г

Download 6,64 Mb. Pdf ko'rish
bet	250/312
Sana	22.05.2024
Hajmi	6,64 Mb.
	#249488

1 ... 246 247 248 249 250 251 252 253 ... 312

Bog'liq
3 tom

Asosiy qism
Axborot xavfsizligini taminlashning RSA shifrlash algoritmida ko'rsatilganidek, va
boshqa ko'plab ilovalarda tub sonlardan foydalaniladi [2,3,4]. Tub sonlar bilan ishlashda
asosiy vazifa sonning tubligini tekshirish va berilgan diapazondagi barcha tub sonlarni
topishdir. Qandaydir natural son
N
berilgan bo'lsin va 2 dan
N
gacha bo'lgan oraliqdagi barcha
tub sonlarni topish talab qilinsin. Bu muammoning eng oddiy yechimi 2 dan
N
gacha bo'lgan
barcha raqamlarni tekshirib o'tishdir va ularning har birini alohida-alohida tublik tarifi
bo’yicha tekshiriladi. Misol uchun agar k raqami tub bo’lishini tekshirilsa ushbu sonni 2 dan

gacha

oraliqda yotgan barcha bo'luvchilarga tekshirib chiqish talab etiladi. Agar bunday
bo'luvchi bo'lmasa, u holda
k
soni tubdir.
Yetarlicha katta
N
soni uchun tavsiflangan usul juda sekin amalga oshadi,
u
O( N
)
ning

asimptotik murakkabligiga ega
.
Yunon matematigi Kirenalik
Eratosfen (miloddan avvalgi 275-194) tez bajarilishi mumkin bolgan boshqa
algoritmni taklif qildi (murakkablik O(Nlog(log N)) [1]. Algoritm quyidagicha
bajariladi:
4.
2 dan N gacha bo'lgan barcha raqamlarni ajratiladi;
5.
k = 2 birinchi qadam;
6.
k ga karrali barcha sonlarni ( 2k, 3k, 4k va boshqalar) olib
tashlaymiz;
7.
o’chirilmay qolgan raqamni topib k o'zgaruvchisiga o’zlashtiramiz;
8.
3 va 4-bosqichlarni k < N ga qadar takrorlanadi.
N = 23 uchun algoritm quyidagi natijani beradi:
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
Birinchi chizilmagan raqam 2, shuning uchun barcha juft raqamlarni olib
tashlanadi va qolganlarini yoziladi:
2 3

Download 6,64 Mb.

1 ... 246 247 248 249 250 251 252 253 ... 312

Download 6,64 Mb.

Pdf ko'rish