|
Faktorizatsiyalash muammosini tahlili
|
| bet | 5/6 | | Sana | 11.10.2022 | | Hajmi | 227.1 Kb. | | #27035 |
Bog'liq 1. Nosimetrik shifrlash algoritmlari Assimetrik shifrlash algori cybersecurity-artificial-intelligence 11111 (1) (1), 402-guruh onlayn kurslar, Elektron ta\'limni boshqaruv vositalari 191 Begbo\'tayeva Sadoqat-fayllar.org, 4-labaratoriya mashg\'ulot topshirig\'i, Pythonda turtle kutubxonasi bilan ishlash (1), 1-mavzu. Zamonaviy axborot texnologiyalari va ularni qoʻllanilishii, Презентация Microsoft PowerPoint (4), Usmon, 9, SANOAT, 1427572, Matematika va informatika ta, 619-guruh dasturlash tillari oraliq nazorat 22.10.2022, Sanoat korxonalarida mehnat gigienasi va ishlab chiqarish sanitariyasi14. Faktorizatsiyalash muammosini tahlili.
Sonni tub ko‘paytuvchilarga ajratish
Quyidagi teorema tub ko‘paytuvchilarga ajratish algoritmini ifodalaydi hamda berilgan sonning tub ekanligini aniqlash imkonini beradi.
Teorema. Aytaylik, n >1 toq son. Bu son murakkab son bo‘ladi faqat va faqat
p,q z+ bulib, n = p2 – q2 bo‘lsa. Bu yerda p- q >1 .
Ferma usulining mohiyati shundan iboratki, teorema natijasiga ko‘ra p,q z+ sonlar topish kerakki,
n = p 2 – q 2 ; p 2 = n+ q 2 yoki q 2 = n + p 2
bajarilsin.
Agar p 2 = n+ q 2 , q =1,2,3…….
qiymatlar uchun n+ q 2 -son biror sonning to‘la kvadratidan iborat bo‘lmasa, u xolda
q = (n -1)/2 qiymat uchun n+ q 2 -ni tekshirib ko‘ramiz va biror sonning kvadratidan iborat bo‘lsa. U holda n – tub son bo‘ladi.
Misol. n =527 soni tub yoki tub emasligi aniqlansin.
q
|
n+ q 2
|
1
|
527+1=528
|
2
|
527+4=531
|
3
|
527+9=536
|
4
|
527+16=543
|
5
|
627+25=552
|
6
|
527+36=563
|
7
|
527+49=576=242
|
Demak, q = 7 uchun
n+ q 2 =242
to‘liq kvadratidan iborat. Bu esa tub ko‘paytuvchilarga yoyilmasi bor degani, yani
527=242 -72 =(24-7)*(24+7) = 17*31.
Natija. Umuman olganda
q =1,2,3……. (n -1)/2 =(527-1)/2 =263
qiymatgacha yetib borishi har doim ham shart emas ekan.
Yuqorida bayon etilgan usulni quyidagi ikkinchi tenglama ko‘rinishda ham olish mumkin edi, yani q 2 = p 2 - n , r = m, m+1,..........
bu yerda m, soni sifatida quyidagi m2 n shartni kanoatlantiruvchi eng kichik butun sonni olamiz. Shu tartibda (p 2 - n) –soni, r = m, m+1,..........
qiymatlar uchun hisoblaymiz, toki (p 2 - n) –son qandaydir sonning to‘lik kvadrati bo‘lmaguncha . Agar r= (n +1)/2 qiymatgacha (p 2 - n) –son biror sonning to‘liq kvadratidan iborat bo‘lmasa, u holda n – tub son bo‘ladi.
Shuni alohida takidlash joizki, bunday holda tekshirish yuqorigi holdagi tekshirishimizdan kamiroq mikdordagi (sondagi) hisoblashlarni talab etadi.
5.Xulosa.
Xulosa qilib shuni aytishim mumkinki faktorlash muammosiga asoslangan
algoritmlar deyarli har kuni ishlatamiz. Faktorlashga asoslangan algoritmlar yordamida misol qilib aytsam, tub sonning kvadratini osongina topishimiz mumkin.
|
| |
