Zbekiston respublikasi raqamli texnologiyalar vazirligi muhammad al-xorazmiy nomidagi

O'ZBEKISTON RESPUBLIKASI RAQAMLI TEXNOLOGIYALAR VAZIRLIGI
MUHAMMAD AL-XORAZMIY NOMIDAGI
TOSHKENT AXBOROT TEXNOLOGIYALARI UNIVERSITETI

Loyiha ishi
Guruh: 715-20
Bajardi: Baxshilloyev Bobir ,
Bekmurodov Anvar,
Qodirov Diyorbek,
Saidov Nozim
Tekshirdi: Mardiyev Ulug’bek


Variant - 14
Topshiriq : Quyidagi qitmatni “p-1 Pollard” usuli yordamida faktorlarga
ajrating (to‘rt kishi uchun).
Pollard's p-1 algoritmi
Pollard's p-1 algoritmi, sonning tubligini tekshirishda ishlatiladigan bir faktorizatsiya algoritmidir. Bu algoritmda son N ning tubligi tekshirilmoqchi bo'lgan sonni hisoblash uchun a va B ni tanlash kerak. Bu qiymatlar algoritmaning effektivligini ta'minlashda muhim rol o'ynayadi.Algoritmda, a soni 1 dan katta bo'lishi lozim, aks holda algoritm to'g'ri natija bermaydi. B esa hisoblash uchun belgilangan chegaradagi bir butun son. Odatda, B sonining katta bo'lishi yuqori natija uchun yordam beradi, lekin juda katta qiymatlar kompyuter resurslarini kengaytirishi mumkin.
1. va B sonlarini tanlang .
2. ni hisoblang, bu yerda p sonlari B dan kichik yoki teng bo'lgan barcha tub sonlardir. ​ esa shartni qanoatlantiradigan eng katta eksponent sifatida tanlanadi.
3. ni hisoblang
4. ni hisoblang . b-1 va N orasidagi eng katta umumiy bo’luvchini ifodalaydi.
5.Agar bo’lsa , N soni tub emas va d N ning Nontrivial bo’luvchisidir. d ni natijaga qaytaring.
6. Agar d=1 yoki d=N bo'lsa, bu erda berilgan B orqali birorta bir bo'luvchi topilmaganligi ma'nosini beradi. B qiymatini oshiring va 3-5 bosqichlarni takrorlang.
Algoritmda a va B ni qanday tanlash mumkinligi kerakli sonning xossalari va algoritmdan kutilayotgan natijalarga bog'liqdir. Agar a va B to'g'ri tanlansa, algoritm to'g'ri faktor topishi mumkin. Lekin tub sonning katta bo'lishini topish muammo bo'lsa, boshqa faktorizatsiya usullari yoki o'zgartirilgan Pollard's p-1 algoritmalari ham ishlatilishi mumkin.
Sonni tublikka tekshirish uchun yana quyidagi algoritmlar qo'llaniladi: