\[ 1

bo‘lgan tub ko‘paytuvchi \(P\) ni berishi mumkin.

Demak, Pollard P-1ning asosiy muammosi \(P-1\) tub ko‘paytuvchilarini qamrab oladigan darajada boy, ammo keragidan ortiq katta bo‘lmagan \(z\) darajani yaratishdir.

Manbaning asosiy notatsiyasi

\(P-1\) har doim juft bo‘lgani uchun manba avval toq qismini:

sifatida ajratadi.

\(\gamma\), tub son nomzodlari ro‘yxatining global yuqori chegarasidir. Nomzodlar to‘plami:

ko‘rinishida aniqlanadi.

\(P_{\mathrm{div}}\) ichidagi haqiqiy tub ko‘paytuvchilar:

ko‘rinishida yoziladi.

• \(p_{\sigma_i}\): haqiqatan \(P_{\mathrm{div}}\) ni bo‘ladigan tub son.
• \(u_{\sigma_i}\): o‘sha tub sonning haqiqiy darajasi.
• \(\sigma_1<\sigma_2<\cdots<\sigma_s\): bu tub sonlarning global tub sonlar ro‘yxatidagi tartib raqamlari.
• \(u_{\max}\): haqiqiy tub son darajalari orasidagi maksimal qiymat.

Manba, shuningdek, eng katta tub-daraja komponentini:

sifatida belgilaydi.

Bir \(p_i\) tub sonining mumkin bo‘lgan maksimal darajasi uchun manba:

yuqori chegarasidan foydalanadi. Buning sababi:

bo‘lgani uchun har qanday tub son darajasi ham bu kattalikdan oshmasligidir.

DSP tub son nomzodlarini qanday ajratadi?

Manba tub son nomzodlari to‘plamini kattaligiga qarab \(k_0\) ta quyi to‘plamga bo‘ladi:

va:

ko‘rinishidagi oraliqlardan foydalanadi.

Bu double-exponential chegaralar dastlab g‘ayrioddiy ko‘rinishi mumkin. Maqsad tub son kattalashgani sari u \(P-1\) ichida ega bo‘lishi mumkin bo‘lgan maksimal daraja soni tez kamayishini algoritmik tuzilishga aks ettirishdir.

DSP haqiqatan ham hech qanday Smoothness Bound ishlatmaydimi?

Yo‘q; Algorithm 4 kirishlaridan biri \(\gamma\) deb ataladigan global tub-sonlar-ro‘yxati yuqori chegarasidir. DSPning afzalligi klassik Pollard P-1 yoki IPP1dagi kabi ish muvaffaqiyati uchun tor \(B\) chegarani oldindan to‘g‘ri taxmin qilishga bog‘liq emasligidir: \(\gamma\) nazariy maksimumga o‘rnatilishi va algoritm tub son/daraja makonini dinamik skan qilishi mumkin; oldindan ma’lumot bo‘lsa kichikroq \(\gamma\) faqat tezlashtirish uchun ishlatilishi mumkin.

Tub-son ko‘paytmasi bit uzunligining kutilgan qiymati

Manba FM va NM xarajatini tahlil qilish uchun \(L(p,n_1,n_2)\) nomli ro‘yxat modelini quradi. Ro‘yxatdagi har bir:

element mustaqil ravishda \(p\) ehtimol bilan tanlanadi.

Ro‘yxatdagi barcha sonlar ko‘paytmasining kutilgan strukturaviy bit uzunligi:

sifatida beriladi.

Bu formula vaqtni o‘lchamaydi. U keyingi katta-butun-son ko‘paytirish va modulli darajaga ko‘tarish xarajatlarida operand kattaligini taxmin qilish uchun ishlatiladigan matematik oraliq natijadir.

Asosiy amal xarajati modellari

Manba butun DSP/IPP1 xarajat tahlilini to‘rtta asosiy amal turiga ajratadi.

1. Katta butun sonlarni ko‘paytirish:

Bu yerda \(n\) operand bit uzunligi; \(C_1\) implementation-dependent doimiydir. Manba asimptotik tahlil uchun katta butun sonlarni ko‘paytirishni \(O(n\log n)\) deb modellashtiradi.

2. Modulli darajaga ko‘tarish:

\(l\) exponent bit uzunligi; \(n\) base/modulus bit kattaligi; \(w\) sliding-window kengligi bo‘lsin:

ko‘rinishida modellashtiriladi.

Manba optimal oyna tanlovini Lambert W funksiyasining asimptotik yaqinlashuvi orqali yechib:

yaqinlashuvini oladi.

Ko‘rib chiqilgan exponent-o‘lcham oralig‘ida bu xarajat exponent bit uzunligi \(l\) bilan taxminan chiziqli o‘zgaradi. DSPning oraliq tub son ko‘paytmalarini qayta ishlatish g‘oyasining muhim matematik asoslaridan biri shu.

3. Oddiy darajaga ko‘tarish:

manbada oddiy binary exponentiation uchun ishlatiladigan yuqori xarajat modelidir.

4. Eng katta umumiy bo‘luvchi:

ko‘rinishida modellashtiriladi. \(C_2\), GCD implementationiga bog‘liq doimiydir.

Asl Pollard P-1 algoritmi

Manba Pollardning asl yondashuvini ikki bosqichli tuzilma sifatida tushuntiradi. \(1<B_1<B_2\) bo‘lganda algoritm muvaffaqiyatli bo‘lishi mumkin bo‘lgan ikki asosiy holat:

1. \(P-1\), \(B_1\)-smoothdir.
2. \(P-1=Ap\), bu yerda \(A\) \(B_1\)-smooth va \(B_1<p<B_2\) tub sondir.

Birinchi bosqichda har bir tub son uchun:

kabi yetarli darajalar tanlanib:

hosil qilinadi.

Bishopning trivial varianti

Bishopning manba taqqoslaydigan oddiy variantida avval tasodifiy:

tanlanadi va:

amallari ketma-ket bajariladi. Har bir bosqichda:

hisoblanadi. Bu yondashuv oldindan smoothness bound tanlashni talab qilmasa-da, exponentni bittadan oshirgani uchun manbada amaliy bo‘lmagan darajada qimmat deb hisoblanadi.

IPP1 qanday ishlaydi?

IPP1 avval ma’lum tub sonlar ro‘yxatining barcha elementlarini bitta ko‘paytmada birlashtiradi:

va so‘ng:

amalini takrorlab, barcha tub sonlarni bir xil iteration soni davomida birgalikda darajaga ko‘taradi.

Bu usul tub son darajalari bir-biriga yaqin bo‘lsa foydali bo‘lishi mumkin. Ammo bitta tub sonning haqiqiy darajasi yuqori bo‘lsa, boshqa barcha tub son nomzodlari ham xuddi shu takrorlar soniga duch keladi. DSP nishonga oladigan asosiy keraksiz xarajat shu.

IPP1 nazariy xarajat modeli

Manba Theorem 1da \(p_t\ge p_{\sigma_s}\) sharti ostida:

yuqori xarajatni beradi.

Agar \(p_t=p_{\sigma_s}\) tanlansa:

hosil bo‘ladi.

Birinchi had tub-sonlar-ro‘yxati ko‘paytmasi xarajatini; ikkinchi had takroriy GCD xarajatini; uchinchi had esa takroriy modular exponentiationning ustun xarajatini ifodalaydi.

DSPning asosiy algoritmi

DSP kirishlari:

• \(N\): ko‘paytuvchilarga ajratiladigan ikki-tub-sonli modul.
• \(\gamma\): tub son nomzodlari ro‘yxatining global yuqori chegarasi.

chiqish esa topilgan tub ko‘paytuvchi yoki muvaffaqiyatsizlikni ko‘rsatuvchi \(\perp\) dir.

Dastlab:

va:

hisoblanadi.

Agar birinchi GCD non-trivial ko‘paytuvchi bermasa:

bilan dynamic scaling boshlanadi.

\(j<k_0\) uchun tegishli tub son quyi to‘plami:

hosil qilinadi.

Bu oraliqdagi tub sonlar ko‘paytmasi:

sifatida hisoblanadi.

Dinamik exponent:

va keyingi bosqich accumulatiori:

bo‘ladi.

Har bir aylanishda:

va undan keyin:

hisoblanadi.

Non-trivial \(d\) topilsa algoritm ko‘paytuvchini qaytaradi. Topilmasa keyingi tub son/daraja miqyosiga o‘tadi.

DSPning ikkinchi fazasi nega boshqacha?

Manbada so‘nggi tub son quyi to‘plami \(\mathcal{P}_{k_0}\) uchun maxsus kuzatuv beriladi. Bu oraliqdagi tub sonlar shunchalik kattaki, \(P_{\mathrm{div}}\) ichida ulardan bir vaqtning o‘zida ikkitasining mavjud bo‘lishi kattalik chegarasiga zid bo‘ladi. Shu sababli so‘nggi quyi to‘plamda barcha tub sonlarni yuqori darajalarga ko‘taradigan qimmat amal o‘rniga Pollardning shift modular exponentiation yondashuvi qo‘llanadi.

Ketma-ket tub son nomzodlari orasidagi yarim farq uchun:

hisoblanadi va:

oldindan hisoblanadi. Shunday qilib, ketma-ket tub son nomzodlariga o‘tishda exponentiation boshidan bajarilish o‘rniga tub sonlar oralig‘idagi farqlardan foydalaniladi.

DSPda oraliq natijani qayta ishlatish nega ishlaydi?

Manbaning Example 1 misoli ikki tub son \(p_1,p_2\) uchun:

ifodani ikki xil usulda hisoblashni taqqoslaydi.

Birinchi usulda:

bir marta hisoblanadi va:

so‘ng:

hisoblanadi.

Ikkinchi usulda exponent avval bevosita:

sifatida tuziladi va bitta modulli darajaga ko‘tarish bajariladi.

Modular exponentiation xarajati exponent bit uzunligiga taxminan chiziqli bog‘liq bo‘lgani uchun ikki usulning modular exponentiation xarajatlari bir-biriga yaqin bo‘lishi mumkin; biroq ikkinchi usul qo‘shimcha ravishda katta exponentning kvadratini yaratishi kerak. Manbaning xulosasi oraliq ko‘paytmani qayta ishlatish exponent yaratish xarajatini kamaytirishi mumkinligidir.

DSP nazariy xarajat modeli

Manba Theorem 2da tegishli holat uchun DSP xarajatini:

ko‘rinishida beradi.

Bu yerda:

• \(p_{\sigma_s}\): \(P_{\mathrm{div}}\) dagi eng katta haqiqiy tub ko‘paytuvchi.
• \(p_{\sigma_x}^{u_{\sigma_x}}\): eng katta tub-daraja komponenti.
• \(n_N\): modul bit uzunligi.
• \(C_1\): katta butun sonlarni ko‘paytirish xarajat doimiysi.
• \(C_2\): GCD xarajat doimiysi.
• \(o(\cdot)\): ustun hadlarga qaraganda sekinroq o‘sadigan quyi tartibli hadlarni ko‘rsatadi.

Bu teorema manbada muvaffaqiyatli faktorizatsiya qilinadigan holat uchun tuzilgan. Muvaffaqiyatsizlik ssenariysining to‘liq xarajati bu ifodaga kiritilmagan.

DSP nega IPP1dan kamroq keraksiz daraja hisoblay oladi?

IPP1 tanlangan tub sonlar ro‘yxatidagi barcha tub son nomzodlarini bir xil \(u_{\max}\) takrorlar sonigacha birgalikda ko‘targan holda, DSP tub son kattalashgani sari mumkin bo‘lgan daraja chegarasi pasayishini hisobga olib turli tub son oraliqlarini turli tezlikda masshtablaydi; shuning uchun bitta kichik tub sonning yuqori darajaga ega bo‘lishi boshqa barcha nomzodlarni ham xuddi shu yuqori darajaga keraksiz ravishda ko‘tarishga olib kelmaydi.

%95 natija qanday olinadi?

Manba Theorem 1 va Theorem 2 xarajatlarini taqqoslaganda DSP arzonroq bo‘lishi mumkin bo‘lgan tengsizlikni oladi. Keyin \(P-1\) ning largest-prime-factor taqsimoti uchun Riesel ta’riflagan \(\rho_1\) funksiyasiga murojaat qiladi.

\(p_{\sigma_s}\ge64\) bo‘lganda:

va manba foydalangan natijadan:

bo‘lishini keltiradi. \(\rho_1\) monoton kamayuvchi bo‘lgani uchun tegishli hodisa uchun:

natijaga erishiladi.

Shuning uchun maqoladagi “%95 dan ko‘proq” ifodasi nazariy xarajat-taqqoslash ehtimolidir. Bu RSA kalitini buzish muvaffaqiyat darajasi, xavfsizlik darajasi yoki tajribadagi 100 namunaning 95 tasi buzilgan degani emas.

DSP umuman RSAni buzadigan algoritmmi?

Yo‘q; DSP Pollard P-1 oilasining maxsus maqsadli faktorizatsiya usuli bo‘lib, samarali ishlashi uchun \(P-1\) yoki \(Q-1\) kichik tub ko‘paytuvchilardan tashkil topgan mos smooth tuzilishga ega bo‘lishi kerak; tadqiqotning 1024-bit test modullari ham shu tuzilma mavjud bo‘lishini ta’minlash uchun maxsus yaratilgan.

Fast Multiplication muammosi nima?

DSP va IPP1 ko‘p sonli tub son nomzodlari ko‘paytmasini hisoblashga majbur. Oddiy Normal Multiplication (NM) usulida:

ro‘yxat uchun birinchi element doimiy o‘suvchi akkumulyator sifatida ishlatiladi:

Bu holda har bir yangi ko‘paytirish avvalgisidan ancha katta butun son bilan bajariladi.

FM qanday ishlaydi?

Fast Multiplication ro‘yxatdagi eng kichik bilan eng katta, ikkinchi kichik bilan ikkinchi katta elementni juftlaydi:

va:

qilib, ro‘yxatni har aylanishda taxminan yarmiga kamaytiradi.

Agar ro‘yxat elementlari soni toq bo‘lsa, boshiga ko‘paytirishga ta’sir qilmaydigan 1 qo‘shiladi. Amal bitta ko‘paytma qolguncha takrorlanadi.

Fast Multiplication nega Normal Multiplicationdan arzonroq bo‘lishi mumkin?

Normal Multiplication doimiy kattalashadigan bitta akkumulyatorni yangi elementlarga ko‘paytirgani uchun juda nomutanosib operand o‘lchamlarini hosil qiladi; FM esa katta va kichik elementlarni simmetrik juftlab, muvozanatli ko‘paytirish daraxtini quradi. Manbaning katta-butun-son xarajat modelida bu tuzilma tub-sonlar-ro‘yxati ko‘paytmasidagi taxminan \(4^n\) miqyosli NM xarajatini taxminan \(2^n n^2\) miqyosli FM xarajatiga tushiradi.

Normal Multiplication murakkabligi

Theorem 3da:

ifoda beriladi.

Agar \(p=1\) bo‘lsa:

bo‘ladi.

Tub sonlarning taxminiy zichligi Prime Number Theorem orqali hisobga olinganda, barcha \(n\)-bit chegaradan past tub sonlar ko‘paytmasining NM bilan xarajati manbada:

ko‘rinishida beriladi.

Fast Multiplication murakkabligi

Theorem 4:

natijani beradi.

\(p=1\) uchun:

bo‘ladi.

Tub sonlar ro‘yxati uchun Corollary 2da:

hosil qilinadi.

\(n_1=0,n_2=n\) deb olinsa, asosiy miqyos:

bo‘ladi, NM tomoni esa \(4^n\) bilan o‘sadi. Manba 4-rasmda maksimal tub ko‘paytuvchi kattaligi 21-26 bit bo‘lgan holatlar uchun nazariy egri chiziqlar haqiqiy o‘lchovlarga yaxshi mos kelishini ko‘rsatadi. Xom o‘lchov jadvali berilmagani sabab Verianla grafikdan aniq vaqt qiymatini chiqarmaydi.

Tadqiqot Usuli va Natijalari

Tajriba 1: Pollard P-1ning to‘rtta variantini taqqoslash

Manba to‘rtta implementationni taqqoslaydi:

1. DSP + Fast Multiplication.
2. IPP1 + Fast Multiplication.
3. Asl Pollard P-1.
4. Bishopning trivial Pollard P-1 varianti.

Tajriba kod repozitori manbada quyidagicha berilgan:

https://github.com/Summwer/expemeriment_of_pollardpm1

Manba havola uchun 1 Avgust 2026 kirish sanasini beradi.

1024-bit test modullari qanday yaratildi?

Mualliflar avval \(P\) ni shunday yaratganlarki, \(P-1\) qiymati bir nechta tasodifiy hosil qilingan 30-bit sonning ko‘paytmasi bo‘ladi. Shu tariqa \(P-1\) ning eng katta tub ko‘paytuvchisi:

bo‘ladi va test namunalarini Pollard P-1 oilasi orqali yechish mumkin bo‘lishi maqsad qilinadi.

Keyin \(P\) bilan bir xil bit uzunligidagi tasodifiy tub son \(Q\) hosil qilinadi va:

hisoblanadi.

Manba matni bu usul bilan **10 ta 1024-bit \(N\)** yaratilganini aytadi. Bunga qarshi ravishda manba 7-rasmning ko‘rinadigan x o‘qida faqat instance 1-8 joylashgan. Manba bu farqni izohlamaydi.

Tajriba apparati

1-tajribaning asosiy tezlik natijasi

Manba yuqori tub-darajalar mavjud bo‘lgan instance 2, 3, 4, 5 va 8 bu xatti-harakatni yaqqol ko‘rsatishini bildiradi. Instance 2, 3, 4 va 8da IPP1 hatto asl Pollard P-1dan ham sekinroq bo‘lgani, shunga qaramay DSP asl algoritmdan tezroq qolganligi xabar qilingan.

Mualliflar talqiniga ko‘ra, DSP xarajati tub ko‘paytuvchilar soni yoki tub sonning tartib indeksidan ko‘ra ko‘proq eng katta tub ko‘paytuvchining kattaligiga sezgir. Bu manbaning o‘z eksperimental va nazariy talqinidir; uni boshqa taqsimotlardagi barcha \(P-1\) tuzilmalari uchun yangi universal natija sifatida kengaytirish kerak emas.

Tajriba 2: Bitta yuqori daraja nazoratli ravishda oshiriladi

Ikkinchi tajribada 512-bit \(P\) quyidagi tuzilmada yaratiladi:

va:

ishlatiladi.

Bu dizaynning maqsadi boshqa shartlarni nazorat ostida ushlagan holda 3 tub sonining darajasini oshirish va IPP1 bilan DSP orasidagi farqni tizimli kuzatishdir.

Har bir \(P\) uchun tasodifiy 512-bit \(Q\) tanlanadi va:

hosil qilinadi.

DSP uchun:

• Algorithm 4 haqiqiy implementation,
• Algorithm 6 DSPEst estimator,
• Theorem 2 nazariy xarajat

taqqoslanadi.

IPP1 uchun esa:

• Algorithm 3 haqiqiy implementation,
• Algorithm 5 IPP1Est estimator,
• Theorem 1 nazariy xarajat

taqqoslanadi.

8-rasmda nazariy xarajat chiziqlari, estimator nuqtalari va haqiqiy tajriba nuqtalari bir xil o‘sish tendensiyasini yaqindan kuzatadi. Bu natija tadqiqot xarajat modellari sinovdan o‘tkazilgan shu konfiguratsiyalarda implementation xatti-harakatini yaxshi ifodalashini qo‘llab-quvvatlaydi. Manba xom nuqta qiymatlarini jadval sifatida bermagani uchun yangi oraliq qiymatlar yaratilmaydi.

Nazariy %95 taqqoslashining to‘g‘ri talqini

Manbaning nazariy natijasi:

• \(p_{\sigma_s}\ge64\) shartini,
• Rieselning \(\rho_1\) funksiyasini,
• Theorem 1 va Theorem 2 xarajat modellarini

birgalikda ishlatadi.

Shuning uchun “DSP %95 muvaffaqiyat darajasiga ega” deyish noto‘g‘ri. Manba aytayotgani muayyan shartlar ostida DSPning IPP1ga qaraganda pastroq nazariy hisoblash xarajatiga ega bo‘lishini qo‘llab-quvvatlovchi hodisaning ehtimoli kamida 0,95 ekanidir.

Tadqiqot qo‘llab-quvvatlaydigan natijalar

• DSP Pollard P-1 tub son nomzodlari va zarur darajalarni bir xil dinamik skanlash tartibida ko‘rib chiqadigan yangi variantdir.
• Oldin hisoblangan tub son ko‘paytmalarini qayta ishlatish yuqori exponent yaratish xarajatini kamaytirishi mumkin.
• DSP tub son kattaligiga qarab exponent taqsimotini o‘zgartirib, IPP1 barcha nomzodlarni \(u_{\max}\) gacha ko‘tarishidan kelib chiqadigan keraksiz hisoblarni kamaytiradi.
• Fast Multiplication muvozanatli ko‘paytirish daraxtidan foydalanib, manba xarajat modelida Normal Multiplicationga qaraganda yaxshiroq asimptotik xatti-harakat ko‘rsatadi.
• Manba 4-rasmda NM/FM nazariy xarajat modellari va tajriba xarajatlari yaxshi mos kelishini ko‘rsatadi.
• Manbaning nazariy shartlarida \(p_{\sigma_s}\ge64\) bo‘lganda DSP xarajati IPP1 xarajatidan past bo‘lishi uchun ishlatilgan ehtimol kamida 0,95 dir.
• Manbaning tuzilgan 1024-bit tajribalarida DSP taqqoslangan uchta eski variantdan tezroq.
• Manba yuqori tub-darajalar mavjud bo‘lganda DSP ustunligi yanada yaqqol bo‘lishini bildiradi.
• Nazoratli \(u_x\) tajribasida Theorem 1/2, estimatorlar va implementation xarajatlarining tendensiyalari bir-biriga yaqin.

Tadqiqot qo‘llab-quvvatlamaydigan natijalar

• DSP umumiy 1024-bit RSA modullarini samarali faktorizatsiya qiladi degan xulosa chiqarib bo‘lmaydi.
• 23,5×, 16,4× va 35,6× tezlik nisbatlarini barcha RSA kalitlariga umumlashtirish mumkin emas.
• %95 qiymati umumiy RSA faktorizatsiya muvaffaqiyat darajasi emas.
• DSP Number Field Sieve kabi umumiy maqsadli faktorizatsiya usullaridan umuman tezroq ekanligi sinovdan o‘tkazilmagan.
• Tadqiqot tajribalari quantum factoring taqqoslashi emas.
• Murakkablik teoremalari muvaffaqiyatsiz faktorizatsiya ssenariysining to‘liq xarajat tahlilini o‘z ichiga olmaydi.
• Ko‘p yadroli yoki GPU tezlashtirilgan performance sinovdan o‘tkazilmagan.
• Boshqa CPU, arbitrary-precision library yoki implementation muhitida xuddi shu tezlik nisbatlari saqlanishi isbotlanmagan.
• 7-rasmda ko‘rinmaydigan instance 9 va 10 uchun vaqt qiymatlarini manbadan chiqarib bo‘lmaydi.

Asosiy uslubiy va qayta ishlab chiqarish cheklovlari

• Tajriba namunalari Pollard P-1 bilan yechiladigan smooth tuzilma maxsus ta’minlanib yaratilgan.
• Taqqoslash bitta shaxsiy kompyuterda va single-threadda bajarilgan.
• Manba matni birinchi tajriba uchun 10 ta 1024-bit modul deyilgan bo‘lsa-da, 7-rasm faqat sakkizta instanceni ko‘rsatadi.
• 7-rasmdagi barcha bar balandliklari jadval sifatida berilmagan.
• 8-rasmdagi xom tajriba, estimator va nazariy qiymatlar jadval ko‘rinishida e’lon qilinmagan.
• DSP/IPP1 nazariy murakkablik bo‘limi aniq ravishda solvable situation bilan cheklangan va failure scenario chiqarib tashlangan.
• Manbada tajribalarda ishlatilgan arbitrary-precision arithmetic library versiyasi batafsil bildirilmagan.
• Maqola klassik sonlar nazariyasi va klassik hisoblash kontekstidadir; quantum factoring natijasini taqdim etmaydi.

Tadqiqotning kriptografik ma’nosi

Pollard P-1 algoritmlari RSAdagi asosiy integer-factorization muammosining umumiy qiyinligini yo‘q qilmaydi. Buning o‘rniga prime generation paytida yuzaga kelishi mumkin bo‘lgan muayyan algebraic weaknesslarni nishonga oladi. Maqolaning hissasi ham shu maxsus zaiflik mavjud bo‘lganda faktorizatsiya jarayonini kamroq keraksiz hisoblash bilan olib borishga qaratilgan.

Shuning uchun tadqiqotning to‘g‘ri xulosasi “RSA endi buzildi” emas. To‘g‘riroq ifoda, smooth \(P-1\) yoki \(Q-1\) tuzilishiga ega maxsus kompozitlarda Pollard P-1 faktorizatsiyasini tezlashtirishni maqsad qilgan yangi traversal/exponent-scaling strategiyasi nazariy va eksperimental ravishda o‘rganilganidir.

Manba va Usul Haqida Izoh

Asl sarlavha: Dynamic Scaling Pollard’s P-1 Algorithm

Mualliflar: Wenwen Xia; Geng Wang; Dawu Gu.

Mualliflar tartibi: Wenwen Xia birinchi; Geng Wang ikkinchi; Dawu Gu uchinchi muallif.

Mas’ul mualliflar: Geng Wang va Dawu Gu.

Muassasa: School of Cyber Science and Engineering, Shanghai Jiao Tong University, Shanghai 200240, China.

Teng hissa: Manbada teng birinchi mualliflik yoki teng hissa bayonoti mavjud emas.

Jurnal: Cryptography.

Nashriyotchi: MDPI.

Jild / son / maqola: 10(4), Article 57.

Sahifalar soni: 26.

DOI: 10.3390/cryptography10040057.

Academic Editor: Josef Pieprzyk.

Yuborilgan: 14 Iyun 2026.

Tahrir: 23 Iyul 2026.

Qabul: 29 Iyul 2026.

Nashr: 13 Avgust 2026.

Version of Record izohi: Rasmiy MDPI Version Notes qaydida dastlabki Version of Record PDF 13 Avgust 2026 da, yangilangan PDF/HTML versiyasi esa 17 Avgust 2026 da nashr qilingan.

Manba turi: Taqrizli tadqiqot maqolasi; sonlar nazariyasi, klassik kriptotahlil, algoritm dizayni, asimptotik murakkablik tahlili va nazoratli kompyuter tajribasini birlashtiradi.

Taqrizdan o‘tish: Cryptography taqrizli MDPI jurnalidir. Jurnal submission materiallarida single-anonymized peer review jarayoni bildiriladi.

Preprint holati: Ishlangan manba nashr etilgan Version of Recorddir; ushbu maqolada alohida preprint asos qilib olinmagan.

Litsenziya: Creative Commons Attribution 4.0 International (CC BY 4.0).

Rasmiy havola: https://doi.org/10.3390/cryptography10040057

Kalit so‘zlar: cryptanalysis; RSA; integer factorization; Pollard’s P-1.

Asosiy ilmiy hissa: Dynamic Scaling Pollard’s P-1 (DSP) va Fast Multiplication (FM).

Taqqoslangan algoritmlar: DSP; IPP1; asl Pollard P-1; Bishopning trivial Pollard P-1 varianti.

Nazariy modellar: Katta butun son multiplication, sliding-window modular powering, binary normal powering va GCD xarajatlari birikmasidan DSP/IPP1 cost estimatorlari tuzilgan.

DSPning asosiy xususiyati: Tub son nomzodlarini double-exponential kattalik oraliqlariga ajratish, kichikroq tub sonlarni yuqoriroq daraja bosqichlariga asta-sekin ko‘tarish va ilgari hisoblangan tub son ko‘paytmalarini qayta ishlatish.

FM xususiyati: O‘suvchi ro‘yxatdagi simmetrik chekka elementlarni pairwise ko‘paytirib, har aylanishda ro‘yxatni taxminan yarmiga kamaytiradigan muvozanatli multiplication tree.

Birinchi tajriba: \(P-1\) bir nechta tasodifiy 30-bit son ko‘paytmasi bo‘ladigan qilib yaratilgan 512-bit \(P\) va taxminan bir xil kattalikdagi tasodifiy \(Q\) dan 1024-bit \(N=PQ\) test modullari.

Birinchi tajriba muhiti: Ubuntu 20.04.1; x86-64; Intel Core i5-9500 @ 3.00 GHz; 16 GB RAM; single thread.

Birinchi tajribaning asosiy natijasi: Manba DSP taxminan IPP1dan 23,5×, asl Pollard P-1dan 16,4× va trivial variantdan 35,6× tezroq ekanini bildiradi.

Birinchi tajribadagi manba-ichki nomuvofiqlik: Matn 10 ta 1024-bit test instance haqida xabar bergan bo‘lsa, manba 7-rasmning ko‘rinadigan x o‘qida faqat 1-8 instancelar bor. Manba bu farqni izohlamaydi.

Ikkinchi tajriba: \(P=2\times3^{u_x}\times1073741789\times z+1\), \(u_x\in\{0,20,40,60,80,100\}\); tasodifiy 512-bit \(Q\); DSP va IPP1 uchun nazariya-estimator-tajriba taqqoslanishi.

Nazariy %95 natijasi: \(p_{\sigma_s}\ge64\) shartida Rieselning \(\rho_1\) funksiyasiga asoslangan chiqarishda DSP foydasiga ishlatilgan xarajat sharti uchun kamida 0,95 ehtimol olinadi. Bu RSA buzish muvaffaqiyat darajasi emas.

Kod repozitori: https://github.com/Summwer/expemeriment_of_pollardpm1 — manbada kirish sanasi 1 Avgust 2026 deb berilgan.

Moliyalashtirish: National Cryptologic Science Fund of China, No. 2025NCSF02017.

Ma’lumotlarning mavjudligi: Mualliflar natijalarni qo‘llab-quvvatlovchi xom ma’lumotlar so‘rov bo‘yicha taqdim etilishini bildiradilar.

Manfaatlar to‘qnashuvi: Mualliflar manfaatlar to‘qnashuvi yo‘qligini bildiradilar.

Muallif hissalari: Conceptualization, methodology, software, validation, formal analysis, investigation, data curation va original draft: Wenwen Xia; resources: Dawu Gu; visualization: Wenwen Xia va Geng Wang; supervision va project administration: Geng Wang va Dawu Gu; funding acquisition: Geng Wang va Dawu Gu.

Etika kengashi / xabardor rozilik: Manbada alohida etika kengashi yoki informed-consent bayonoti mavjud emas; tadqiqot matematik algoritm va sintetik/hisoblash faktorizatsiya tajribasidir.

Asosiy uslubiy cheklovlar: Nazariy cost analysis muvaffaqiyatsizlik ssenariysini chiqarib tashlaydi; tajriba modullari Pollard P-1ga mos smooth tuzilma ta’minlanib yaratilgan; taqqoslash bitta mashina va single-threadda; birinchi tajribada matn-grafik instance soni nomuvofiqligi bor; 7-8-rasmlarning xom raqamli ma’lumotlari jadval sifatida berilmagan.

Umumiy talqin chegarasi: Tadqiqot mos smooth \(P-1\) yoki \(Q-1\) tuzilishga ega modullarda Pollard P-1 faktorizatsiyasini DSP va FM bilan tezlashtirish mumkinligini qo‘llab-quvvatlaydi; arbitrary RSA modulus, umumiy NFS taqqoslashi yoki barcha zamonaviy RSA kalitlarini amalda buzish mumkin degan xulosani qo‘llab-quvvatlamaydi.