Zbekiston respublikasi raqamli texnologiyalar vazirligi muhammad al-xorazmiy nomidagi

Javoblari:

1-rasm
Yuqoridagi N soni p va q tub ko’paytuvchilarga ajraldi bular quyidagilar :
p-son: 158822251136794944865323124199145317148993195697175575250620030834076269158370217730447422132291840359498307037951292219724248353952878182870794591411565869012281621591404559808567040937104513168558997436378361254840857304689282003972439950411832326518827485842928202470808822700781566552547057732045518407103;
q-son:
158822251136794944865323124199145317148993195697175575250620030834076269158370217730447422132291840359498307037951292219724248353952878182870794591411565869012281621591404559808567040937104513168558997436378361254840857304689282003972439950411832326518827485842928202470808822700781566552547057732045518407241;
Xulosa:
Pollard p-1 algoritmi, faktorlarga ajratish uchun ishlatiladigan bir metoddur. Bu algoritm sonni "p-1" formula orqali faktorlarga ajratishga harakat qiladi, bu yerda "p" tub sonlardan biri bo'ladi.
Boshlanish qiymati sifatida "a" va "N" soni beriladi, "N" soni faktorlarga ajratish kerak bo'lgan son.
"a" soni "N" soni bilan ko'prik darajasiga oshiriladi va olish natijasi "x" ga teng bo'ladi: x = a^M mod N, M > 1
"x" soni N ga kengaytirilgan bo'luvchi bo'lishi tekshiriladi. Agar x != 1 bo'lsa, "x" soni N ga bo'luvchi sifatida faktorga hisoblanadi.
Agar x = 1 bo'lsa, M qiymati oshiriladi va 2-qadamdan boshlanadi.
2-qadamdan davom etish uchun "a" qiymati "x" qiymati bilan almashtiriladi va 2-qadamdan boshlanadi.
Algoritmning jarayoni M qiymatini oshirib ketadi va har qadamda "x" qiymati tekshiriladi. M qiymati katta bo'lganligicha, faktorlarni topish imkoniyati oshadi. Ammo algoritm hamma sonlar uchun samarali bo'lmaydi va eng yaxshi natijalar osonlik bilan topilmaydi.
Shu sababli, agar Pollard p-1 algoritmi muvaffaqiyatsiz bo'lsa, boshqa faktorlarga ajratish usullarini (masalan, kvadrat bo'luvchilarni topish, ECM, ya'ni elliptik krivkalar metodi, yoki sanoq sistemalari usullari) ishlatish mumkin.
Keyinchalik, usuldan usulga farq qiladi, ammo Pollard p-1 algoritmi ko'p sonlar uchun samarali bo'lishi bilan bilinadi va butun sonlarda ishlay oladi. Lekin bu algoritmning qo'llanish chegarasi ham mavjud va hamma sonlar uchun yuqori samaradorlik ta'minlay olmaydi. Bunday holatda, boshqa faktorlarga ajratish usullari yordamida sonlarni faktorlarga ajratish muhim bo'ladi.