Mavzu: Faktorlash muammosini bartaraf etuvchi dasturiy vositani ishlab chiqish Faktorlash muammosini bartaraf etuvchi algoritmlar. Ishdan maqsad

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=24^2

Demak, q = 7 uchun
n+ q ² =24²
soni tub yoki tub emasligi aniqlansin
527=24² -7² =(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, ya'ni q ² = p ² - n , p = m, m+1,.......... bu yerda m, soni sifatida quyidagi m² n shartni kanoatlantiruvchi eng kichik butun sonni olamiz. Shu tartibda (p ² - n) –soni,
p = m, m+1,...qiymatlar uchun hisoblaymiz, toki (p ² - n) –son qandaydir sonning to‘lik kvadrati bo‘lmaguncha. Agar p= (n +1)/2 qiymatgacha (p ² - n) – son biror sonning to‘liq kvadratidan iborat bo‘lmasa, u holda n – tub son bo’ladi.
Pollard usuli. Ushbu usul Ro-algoritm yoki –algoritm nomlari bilan ham keng tarqalgan. Faktorlash muammosini yechishda takrorlanuvchi funksiya ketma-ketligidagi sikllarga va tugʼilgan kun paradoksiga asoslanadi. U ikki sonning koʼpaytmasidan tashkil topgan sonlarning faktorlash muammosini yechishda samarali. Uning murakkabligi orqali baholanadi – algoritm sonlardan iborat ketma-ketlikni tashkil etadi va qaysidir sonidan boshlab siklni hosil qiladi. Hosil boʼlgan sikl koʼrinishida boʼlganligi uchun – algoritm deb nomlanadi.


2.1-rasm. –algoritm ko’rinishi
Misol. 8051 sonini –algoritm asosida faktorlash muammosini yechish.
asosida

, ,
i
1.	5	26	1
2.	26	7474	1
3.	677	871	97

asosida

, ,
I
1.	7	52	1
2.	52	1442	1
3.	2707	778	1
4.	1442	3932	83

Demak, va sonlari 8051 sonining umumiy bo’luvchilari;-Algoritm ni hisoblaydi, agar uning qiymati tub son bo’lmasa, hisoblash davom etadi.
Subeksponent algoritmlar belgili murakkablikka asoslangan.
.
Bu yerda, – fatorlash talab etiladigan son, va – konstanta. Misol sifatida Dikson algoritmini keltirish mumkin. Ushbu algoritm tenglikdan va sonlarini hisoblashga qaratilgan. Bu yerda, .
Kvadrat elak usuli (QSA) ham katta sonlarni faktorlash muammosini yechishga qaratilgan. U katta sonini gacha bo’lgan oraliqda tub kupaytuvchilarga ajratishda qoʼllaniladigan va 100 ta oʼnlik sonlardan iborat katta sonlar uchun eng tezkor usul sanaladi. Algoritm ikki bosqichda amalga oshiriladi:1- bosqich. Maʼlumotlarni toʼplash. Ikki sonning kvadrati koʼrinishiga keltiriladigan sonlarni ajratib oladi. 2- bosqich. Maʼlumotlarni qayta ishlash. Barcha sonlarni matritsaga joylashtiradi va ikki sonning kvadrati koʼrinishidagi sonlarni olish uchun qayta ishlaydi.
Birinchi bosqichni parallel hisoblash elementlari asosida oson hisoblashga erishish mumkin. Ammo, ikkinchi bosqichni parallel hisoblashga keltirish murakkab. Shuning uchun uni hisoblash uchun koʼp xotira talab etiladi.
Shunday ixtiyoriy sonni topish kerakki, uni kvadratini hisoblaganimizda va soniga boʼlganimizdagi qoldiq yana qaysidir sonning kvadrati koʼrinishida shakllanishi lozim. . Uning davomi quyidagi koʼrinishda ifodalanadi: .
Bu yerda, – fakotrlash muammosi yechiladigan son.