2-ma’ruza Mavzu: Faktorlash muammosi va uni hisoblash; Qoldiq haqidagi Xitoy teoremasi; Sonni tub ko‘paytuvchilarga ajratish

Mashqlar
Ferma adgoritmidan foydalanib, quyidagi sonlarning tub yoki tub emasligi aniqlansin. Agar tub bo‘lmasa ko‘paytuvchilarga yoyilsin.

1. 1001
   

2. 1349
   

3. 4851
   

4. 1079
   

5. 8051
   

6. 567
   

7. 7931
   

Pollard usuli
Aytaylik , n - juft bo‘lmagan murakkab son, bo‘luvchisi katta bo‘lmagan. R – orqali n –sonning eng kichik tub bo‘luvchisini belgilasak. Pollard usulining mohiyati shu bo‘luvchini topishdan iborat.

Algoritm bajarilish ketma-ketligi quyidagidan iborat :

1. Aytaylik,

   
   

z = [ n^{1 / 4}] +1 , y = z² > n^1/2.

2. n va u! sonlarining eng kichik umumiy karralisini topamiz:
EKUK( n , u! ) = n* u! / EKUB ( n , u! ) .
3. Malumki u! soni berilgan n sonining eng kichik tub bo‘luvchisi R –ga bo‘linadi,
chunki R n^1/2 < y .
4. U holda berilgan sonning eng kichik tub bo‘luvchisi P -ekanligi javob qilib beriladi.


Misol 2. Quyidagi sonni Pollard usulidan foydalinib ko‘paytuvchilarga ajrating.
n = 527
Yechish. Bevosita Ferma usulidan foydalinib ko‘rsatish mumkinki:
527 = (24)² – ( 7)² = 17*31.
Maqsad shu sonni tub ko‘paytuvchilarga yoyilmasini Pollard usuli yordamida amalga oshirishdan iborat. Har bir qadamni ketma-ket bajarib chiqamiz.
z = [ n^{1 / 4}] +1 = 4+1=5 , y = z² > n^1/2 = 25.
EKUB( 527, 25!) =17,
EKUK (527, 25!) = 527*25!/ 17 = 31*25!
Demak, 25! Sonining bo‘linuvchisi 17 bor. U holda
R = 17 , javob esa 527 = 17*v, v = 31, yani 527 = 17*31.


Pollardning usuli
Pollardning usuli 1975 yilda Dj. Pollard tomonidan topilgan bo‘lib,

F₈ = 2²⁵⁶ +1 Ferma sonining tub ko‘paytuvchilari aniqlanilgan.

Aytaylik, n N bizdan shu sonni tub ko‘paytuvchilarga ajratish masalasi so‘ralayotgan bo‘lsin. Bu usulning mohiyati quyidagidan iborat:
1)f(x) – ko‘pxad darajasi ikki yoki undan katta bo‘lgan, masalan f(x)=x² +1 deb olinadi.
2) Tasodifiy x₀ ZnZ tanlanadi.
3) Qandaydir fiksirlangan (malum bo‘lgan) j, k –nomerlar uchun quyidagi shartlarning bajarishligi tekshiriladi:
1 < EKUB (x_j –x_k ; n) < n
toki, n –sonining tub ko‘paytuvchilari topilmaguncha.
Bu yerda, agar j –soni
2^h j < 2^h+1, h N
bo‘lsa, u holda k = 2^h -1 ko‘rinishda olish maqsadga muvofiq..