8-amaliy mashg’ulot Mavzu: Faktorlash muammosini bartaraf etuvchi dasturiy vositani ishlab chiqish

8-amaliy mashg’ulot
Mavzu: Faktorlash muammosini bartaraf etuvchi dasturiy vositani ishlab chiqish. Faktorlash muammosini bartaraf etuvchi Pollard usuli
Sonni tub ko‘paytuvchilarga ajratish
Quyidagi teorema tub ko‘paytuvchilarga ajratish algoritmini ifodalaydi hamda berilgan sonning tub ekanligini aniqlash imkonini beradi.
Teorema. Aytaylik, 0020n >1 toq son. Bu son murakkab son bo‘ladi faqat va faqat
p,q z⁺ bulib, n = p² – q² bo‘lsa. Bu yerda p- q >1 .
Ferma usulining mohiyati shundan iboratki, teorema natijasiga ko‘ra p,q z⁺ sonlar topish kerakki,
n = p ² – q ² ; p ² = n+ q ² yoki q ² = n + p ²
bajarilsin.
Agar p ² = n+ q ² , q =1,2,3…….
qiymatlar uchun n+ q ² -son biror sonning to‘la kvadratidan iborat bo‘lmasa, u xolda
q = (n -1)/2 qiymat uchun n+ q ² -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=24^2

Demak, q = 7 uchun
n+ q ² =24²
to‘liq kvadratidan iborat. Bu esa tub ko‘paytuvchilarga yoyilmasi bor degani, yani
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, yani q ² = p ² - n , r = m, m+1,..........
bu yerda m, soni sifatida quyidagi m² n shartni kanoatlantiruvchi eng kichik butun sonni olamiz. Shu tartibda (p ² - n) –soni, r = m, m+1,..........
qiymatlar uchun hisoblaymiz, toki (p ² - n) –son qandaydir sonning to‘lik kvadrati bo‘lmaguncha . Agar r= (n +1)/2 qiymatgacha (p ² - 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.