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


Download 72.77 Kb.
bet2/7
Sana03.12.2023
Hajmi72.77 Kb.
#1797942
1   2   3   4   5   6   7
Bog'liq
2-ma’ruza Mavzu Faktorlash muammosi va uni hisoblash; Qoldiq ha-www.fayllar.org

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 = [ n1 / 4] +1 , y = z2 > n1/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 n1/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)2 – ( 7)2 = 17*31.
Maqsad shu sonni tub ko‘paytuvchilarga yoyilmasini Pollard usuli yordamida amalga oshirishdan iborat. Har bir qadamni ketma-ket bajarib chiqamiz.
z = [ n1 / 4] +1 = 4+1=5 , y = z2 > n1/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,

F8 = 2256 +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)=x2 +1 deb olinadi.
2) Tasodifiy x0 ZnZ tanlanadi.
3) Qandaydir fiksirlangan (malum bo‘lgan) j, k –nomerlar uchun quyidagi shartlarning bajarishligi tekshiriladi:
1 < EKUB (xj –xk ; n) < n
toki, n –sonining tub ko‘paytuvchilari topilmaguncha.
Bu yerda, agar j –soni
2h j < 2h+1, h N
bo‘lsa, u holda k = 2h -1 ko‘rinishda olish maqsadga muvofiq..

Download 72.77 Kb.

Do'stlaringiz bilan baham:
1   2   3   4   5   6   7




Ma'lumotlar bazasi mualliflik huquqi bilan himoyalangan ©fayllar.org 2024
ma'muriyatiga murojaat qiling