\[ 1

омили содаи \(P\)-ро дода метавонад.

Пас масъалаи асосии Pollard P-1 сохтани дараҷаи \(P-1\) аст, ки барои фаро гирифтани омилҳои содаи \(z\) ба қадри кофӣ ғанӣ, вале нолозим аз ҳад калон набошад.

Нотатсияи асосии манбаъ

Азбаски \(P-1\) ҳамеша ҷуфт аст, манбаъ аввал қисми тоқро:

ҷудо мекунад.

\(\gamma\) ҳадди болоии глобалии рӯйхати номзадҳои ададҳои сода аст. Маҷмӯи номзадҳо:

чунин муайян мешавад.

Омилҳои содаи воқеӣ дар \(P_{\mathrm{div}}\):

чунин навишта мешаванд.

• \(p_{\sigma_i}\): адади содае, ки воқеан \(P_{\mathrm{div}}\)-ро тақсим мекунад.
• \(u_{\sigma_i}\): дараҷаи воқеии он адади сода.
• \(\sigma_1<\sigma_2<\cdots<\sigma_s\): мавқеи ин ададҳои сода дар рӯйхати глобалии ададҳои сода.
• \(u_{\max}\): қимати максималӣ байни дараҷаҳои воқеии ададҳои сода.

Манбаъ ҳамчунин калонтарин компоненти сода-дараҷаро:

муайян мекунад.

Барои дараҷаи максималии имконпазири як адади содаи \(p_i\), манбаъ:

ҳадди болоиро истифода мебарад. Сабаб ин аст, ки:

ва аз ин рӯ ягон қувваи адади сода низ набояд аз ин бузургӣ зиёд шавад.

DSP номзадҳои ададҳои содаро чӣ гуна ҷудо мекунад?

Манбаъ маҷмӯи номзадҳои ададҳои содаро аз рӯи бузургӣ ба \(k_0\) зермаҷмӯа ҷудо мекунад:

ва:

фосилаҳоро истифода мебарад.

Ин ҳадҳои double-exponential дар назари аввал ғайриодӣ менамоянд. Ҳадаф ин аст, ки воқеияти бо афзоиши бузургии адади сода зуд кам шудани шумораи максималии дараҷаҳое, ки он метавонад дар \(P-1\) дошта бошад, ба сохтори алгоритмӣ инъикос гардад.

Оё DSP воқеан ягон Smoothness Bound истифода намекунад?

Не; яке аз вурудҳои Algorithm 4 ҳадди болоии глобалии рӯйхати ададҳои сода бо номи \(\gamma\) мебошад. Бартарии DSP дар он аст, ки мисли Pollard P-1 ё IPP1-и классикӣ барои муваффақияти кор ба пешакӣ дуруст тахмин кардани ҳадди танги \(B\) вобаста нест: \(\gamma\)-ро метавон ба максимуми назариявӣ гузошт ва алгоритм фазои адади сода/дараҷаро динамикӣ мекобад; агар маълумоти пешакӣ бошад, \(\gamma\)-и хурдтар танҳо барои суръатбахшӣ истифода шуда метавонад.

Қимати интизории дарозии bit-и ҳосили ададҳои сода

Манбаъ барои таҳлили хароҷоти FM ва NM модели рӯйхатеро бо номи \(L(p,n_1,n_2)\) месозад. Ҳар як:

элемент мустақилона бо эҳтимоли \(p\) интихоб мешавад.

Дарозии сохтории bit-и интизории ҳосили ҳамаи ададҳои рӯйхат:

дода мешавад.

Ин формула вақтро чен намекунад. Он натиҷаи мобайнии математикӣ барои тахмини бузургии operand дар хароҷоти минбаъдаи зарби ададҳои бузург ва дараҷабардории модулӣ мебошад.

Моделҳои асосии хароҷоти амалиёт

Манбаъ тамоми таҳлили хароҷоти DSP/IPP1-ро ба чор навъи асосии амалиёт ҷудо мекунад.

1. Зарби ададҳои бутуни калон:

Дар ин ҷо \(n\) дарозии bit-и operand; \(C_1\) доимии implementation-dependent аст. Манбаъ барои таҳлили асимптотикӣ зарби ададҳои бутуни калонро ҳамчун \(O(n\log n)\) модел мекунад.

2. Дараҷабардории модулӣ:

\(l\) дарозии bit-и exponent; \(n\) бузургии bit-и base/modulus; \(w\) паҳноии sliding-window бошад:

чунин модел мешавад.

Манбаъ интихоби равзанаи оптималиро бо наздикшавии асимптотикии функсияи Lambert W ҳал карда:

наздикшавиро ба даст меорад.

Дар диапазони exponent-андозаи баррасишуда ин хароҷот бо дарозии bit-и exponent \(l\) тақрибан хаттӣ тағйир меёбад. Яке аз асосҳои муҳими математикии идеяи дубора истифода бурдани ҳосилҳои мобайнии ададҳои сода дар DSP ҳамин аст.

3. Дараҷабардории оддӣ:

модели хароҷоти болоиест, ки дар манбаъ барои binary exponentiation-и оддӣ истифода шудааст.

4. Бузургтарин тақсимкунандаи умумӣ:

чунин модел мешавад. \(C_2\) доимиест, ки ба implementation-и GCD вобаста аст.

Алгоритми аслии Pollard P-1

Манбаъ равиши аслии Pollard-ро ҳамчун сохтори думарҳилаӣ шарҳ медиҳад. Бо \(1<B_1<B_2\) ду ҳолати асосие, ки алгоритм метавонад муваффақ шавад:

1. \(P-1\), \(B_1\)-smooth аст.
2. \(P-1=Ap\), ки дар он \(A\) \(B_1\)-smooth ва \(B_1<p<B_2\) адади сода аст.

Дар марҳилаи аввал барои ҳар адади сода:

дараҷаҳои кофӣ интихоб шуда:

сохта мешавад.

Варианти trivial-и Bishop

Дар варианти оддии Bishop, ки манбаъ муқоиса мекунад, дар оғоз ба таври тасодуфӣ:

интихоб мешавад ва:

амалиёт пайдарпай иҷро мешаванд. Дар ҳар қадам:

ҳисоб карда мешавад. Гарчанде ин равиш интихоби пешакии smoothness bound-ро талаб намекунад, азбаски exponent-ро як-як зиёд мекунад, дар манбаъ аз ҷиҳати амалӣ хеле гарон ҳисоб мешавад.

IPP1 чӣ гуна кор мекунад?

IPP1 аввал ҳамаи элементҳои рӯйхати муайяни ададҳои содаро дар як ҳосил муттаҳид мекунад:

ва баъд:

амалро такрор карда, ҳамаи ададҳои содаро дар давоми як шумораи iteration якҷоя ба дараҷа мебардорад.

Ин усул агар дараҷаҳои ададҳои сода ба ҳам наздик бошанд, бартарӣ дошта метавонад. Аммо агар дараҷаи воқеии танҳо як адади сода баланд бошад, ҳамаи дигар номзадҳои ададҳои сода низ ба ҳамон шумораи такрор дучор мешаванд. Ин ҳамон хароҷоти нолозими асосиест, ки DSP ҳадаф мегирад.

Модели назариявии хароҷоти IPP1

Манбаъ дар Theorem 1 зери шарти \(p_t\ge p_{\sigma_s}\):

ҳадди болоии хароҷотро медиҳад.

Агар \(p_t=p_{\sigma_s}\) интихоб шавад:

ба даст меояд.

Ҳади аввал хароҷоти ҳосили рӯйхати ададҳои сода; ҳади дуюм хароҷоти такрории GCD; ҳади сеюм бошад хароҷоти бартаридоштаи modular exponentiation-и такрориро ифода мекунад.

Алгоритми асосии DSP

Вурудҳои DSP:

• \(N\): модули ду-адади-содае, ки бояд факторизатсия шавад.
• \(\gamma\): ҳадди болоии глобалии рӯйхати номзадҳои ададҳои сода.

баромад бошад омили содаи ёфтшуда ё \(\perp\), ки нокомиро нишон медиҳад.

Дар оғоз:

ва:

ҳисоб карда мешавад.

Агар GCD-и аввал омили non-trivial надиҳад:

бо он dynamic scaling оғоз мешавад.

Барои \(j<k_0\) зермаҷмӯи мувофиқи ададҳои сода:

сохта мешавад.

Ҳосили ададҳои сода дар ин фосила:

ҳисоб карда мешавад.

Exponent-и динамикӣ:

ва accumulator-и марҳилаи баъдӣ:

мешавад.

Дар ҳар давр:

ва баъдан:

ҳисоб карда мешавад.

Агар \(d\)-и non-trivial ёфт шавад, алгоритм омилро бармегардонад. Агар ёфт нашавад, ба миқёси навбатии адади сода/дараҷа мегузарад.

Чаро фазаи дуюми DSP фарқ мекунад?

Дар манбаъ барои зермаҷмӯи охирини ададҳои сода \(\mathcal{P}_{k_0}\) мушоҳидаи махсус оварда мешавад. Ададҳои сода дар ин фосила он қадар калонанд, ки дар \(P_{\mathrm{div}}\) ҳамзамон будани дутои онҳо бо ҳадди бузургӣ мухолиф хоҳад буд. Аз ин рӯ дар зермаҷмӯи охир ба ҷойи амалиёти гароне, ки ҳамаи ададҳои содаро ба дараҷаҳои баланд мебардорад, равиши shift modular exponentiation-и Pollard истифода мешавад.

Барои нисфи фарқи байни номзадҳои пайдарпайи ададҳои сода:

ҳисоб карда мешавад ва:

пешакӣ ҳисоб карда мешавад. Ҳамин тавр, ҳангоми гузариш ба номзадҳои пайдарпайи ададҳои сода, ба ҷойи аз нав иҷро кардани exponentiation, аз фарқҳои байни ададҳои сода истифода мешавад.

Чаро дубора истифода бурдани натиҷаҳои мобайнӣ дар DSP кор мекунад?

Example 1-и манбаъ барои ду адади содаи \(p_1,p_2\):

ҳисоб кардани ифодаро бо ду усули гуногун муқоиса мекунад.

Дар усули аввал:

як бор ҳисоб карда мешавад ва:

сипас:

ҳисоб карда мешавад.

Дар усули дуюм exponent аввал мустақиман:

сохта шуда, як дараҷабардории модулӣ иҷро мешавад.

Азбаски хароҷоти modular exponentiation ба дарозии bit-и exponent тақрибан хаттӣ аст, хароҷоти modular exponentiation-и ду усул метавонад ба ҳам наздик бошад; аммо усули дуюм бояд илова бар ин квадрати exponent-и калонро низ созад. Хулосаи манбаъ ин аст, ки дубора истифода бурдани ҳосили мобайнӣ метавонад хароҷоти сохтани exponent-ро кам кунад.

Модели назариявии хароҷоти DSP

Манбаъ дар Theorem 2 барои ҳолати дахлдор хароҷоти DSP-ро:

чунин медиҳад.

Дар ин ҷо:

• \(p_{\sigma_s}\): калонтарин омили содаи воқеӣ дар \(P_{\mathrm{div}}\).
• \(p_{\sigma_x}^{u_{\sigma_x}}\): калонтарин компоненти сода-дараҷа.
• \(n_N\): дарозии bit-и модул.
• \(C_1\): доимии хароҷоти зарби ададҳои бутуни калон.
• \(C_2\): доимии хароҷоти GCD.
• \(o(\cdot)\): ҳадҳои тартиби пастро нишон медиҳад, ки нисбат ба ҳадҳои бартаридошта сусттар меафзоянд.

Ин теорема дар манбаъ барои ҳолати бомуваффақият факторизатсияшаванда сохта шудааст. Хароҷоти пурраи сенарияи нокомӣ ба ин ифода дохил нест.

Чаро DSP метавонад нисбат ба IPP1 дараҷаҳои нолозими камтар ҳисоб кунад?

Дар ҳоле ки IPP1 ҳамаи номзадҳои ададҳои сода дар рӯйхати интихобшударо то ҳамон шумораи такрории \(u_{\max}\) якҷоя мебардорад, DSP аз воқеияти кам шудани ҳадди дараҷаи имконпазир бо калон шудани адади сода истифода карда, фосилаҳои гуногуни ададҳои содаро бо суръатҳои гуногун миқёс мекунад; бинобар ин дараҷаи баланди як адади содаи хурд боис намешавад, ки ҳамаи номзадҳои дигар низ ҳамон дараҷаи баландро нолозим гиранд.

Натиҷаи %95 чӣ гуна ба даст меояд?

Ҳангоми муқоисаи хароҷоти Theorem 1 ва Theorem 2 манбаъ нобаробарие ба даст меорад, ки DSP метавонад арзонтар бошад. Сипас барои тақсимоти largest-prime-factor-и \(P-1\) ба функсияи \(\rho_1\), ки дар Riesel муайян шудааст, муроҷиат мекунад.

Вақте \(p_{\sigma_s}\ge64\):

ва аз натиҷаи истифодашуда манбаъ:

буданашро меорад. Азбаски \(\rho_1\) монотонӣ камшаванда аст, барои рӯйдоди дахлдор:

натиҷа гирифта мешавад.

Аз ин рӯ ибораи “зиёда аз %95” дар мақола эҳтимоли назариявии муқоисаи хароҷот аст. Ин маънои сатҳи муваффақияти шикастани калиди RSA, сатҳи амният ё онро надорад, ки аз 100 намунаи таҷрибавӣ 95-тоаш шикаста шудааст.

Оё DSP умуман алгоритми шикастани RSA аст?

Не; DSP усули махсуси факторизатсияи оилаи Pollard P-1 мебошад ва барои самаранок буданаш \(P-1\) ё \(Q-1\) бояд сохтори мувофиқи smooth дошта бошад, ки аз омилҳои содаи хурд иборат аст; модулҳои санҷишии 1024-bit-и таҳқиқот низ махсус барои мавҷуд будани ҳамин сохтор сохта шудаанд.

Масъалаи Fast Multiplication чист?

DSP ва IPP1 бояд ҳосили шумораи зиёди номзадҳои ададҳои содаро ҳисоб кунанд. Дар усули оддии Normal Multiplication (NM):

барои рӯйхат элементи аввал ҳамчун accumulator-и пайваста калоншаванда истифода мешавад:

Дар ин ҳолат ҳар зарби нав бо адади бутуне анҷом дода мешавад, ки аз пешина хеле калонтар аст.

FM чӣ гуна кор мекунад?

Fast Multiplication дар рӯйхат хурдтаринро бо калонтарин, хурди дуюмро бо калони дуюм ҷуфт мекунад:

ва:

карда, рӯйхатро дар ҳар давр тақрибан ба нисф кам мекунад.

Агар шумораи элементҳои рӯйхат тоқ бошад, ба аввал 1 илова мешавад, ки ба зарб таъсир надорад. Амал то мондани як ҳосил такрор мешавад.

Чаро Fast Multiplication метавонад аз Normal Multiplication арзонтар бошад?

Normal Multiplication азбаски як accumulator-и пайваста калоншавандаро бо элементҳои нав зарб мекунад, андозаҳои хеле нобаробари operand ба вуҷуд меорад; FM бошад элементҳои калон ва хурдро симметрӣ ҷуфт карда, дарахти мутавозини зарб месозад. Дар модели хароҷоти ададҳои бутуни калони манбаъ ин сохтор хароҷоти NM-и тақрибан \(4^n\)-миқёсро дар ҳосили рӯйхати ададҳои сода ба хароҷоти FM-и тақрибан \(2^n n^2\)-миқёс кам мекунад.

Мураккабии Normal Multiplication

Дар Theorem 3:

ифода дода мешавад.

Агар \(p=1\) бошад:

мешавад.

Вақте зичии тақрибии ададҳои сода бо Prime Number Theorem ба ҳисоб гирифта мешавад, хароҷоти ҳосили ҳамаи ададҳои содаи поёнтар аз ҳадди \(n\)-bit бо NM дар манбаъ:

чунин дода мешавад.

Мураккабии Fast Multiplication

Theorem 4:

натиҷаро медиҳад.

Барои \(p=1\):

мешавад.

Барои рӯйхати ададҳои сода дар Corollary 2:

ба даст меояд.

Агар \(n_1=0,n_2=n\) гирифта шавад, миқёси асосӣ:

мешавад, дар ҳоле ки ҷониби NM бо \(4^n\) меафзояд. Манбаъ дар Шакли 4 барои андозаҳои максималии омили содаи 21-26 bit мувофиқати хуби каҷҳои назариявӣ ва ченкуниҳои воқеиро нишон медиҳад. Азбаски ҷадвали ченкуниҳои хом дода нашудааст, Verianla аз график вақти дақиқ бароварда намекунад.

Усул ва Натиҷаҳои Таҳқиқот

Таҷрибаи 1: Муқоисаи чор варианти Pollard P-1

Манбаъ чор implementation-ро муқоиса мекунад:

1. DSP + Fast Multiplication.
2. IPP1 + Fast Multiplication.
3. Pollard P-1-и аслӣ.
4. Варианти trivial-и Pollard P-1-и Bishop.

Репозитории коди таҷриба дар манбаъ чунин дода шудааст:

https://github.com/Summwer/expemeriment_of_pollardpm1

Манбаъ барои пайванд санаи дастрасии 1 Август 2026-ро медиҳад.

Модулҳои санҷишии 1024-bit чӣ гуна сохта шуданд?

Муаллифон аввал \(P\)-ро тавре сохтаанд, ки қимати \(P-1\) ҳосили чанд адади тасодуфии 30-bit бошад. Ҳамин тавр, калонтарин омили содаи \(P-1\):

мешавад ва ҳадаф ин аст, ки намунаҳои санҷишӣ аз ҷониби оилаи Pollard P-1 ҳалшаванда бошанд.

Сипас адади содаи тасодуфии \(P\) бо ҳамон дарозии bit-и \(Q\) сохта шуда:

ҳисоб карда мешавад.

Матни манбаъ мегӯяд, ки бо ин усул **10 адад 1024-bit \(N\)** сохта шудааст. Аммо дар меҳвари x-и намоёни Шакли 7-и манбаъ танҳо instance 1-8 ҷой доранд. Манбаъ ин фарқро шарҳ намедиҳад.

Таҷҳизоти таҷриба

Натиҷаи асосии суръати Таҷрибаи 1

Манбаъ мегӯяд, ки instance 2, 3, 4, 5 ва 8, ки дараҷаҳои баланди ададҳои сода доранд, ин рафторро намоён мекунанд. Гузориш шудааст, ки дар instance 2, 3, 4 ва 8 IPP1 ҳатто аз Pollard P-1-и аслӣ сусттар аст, аммо DSP аз алгоритми аслӣ тезтар мемонад.

Тибқи тафсири муаллифон, хароҷоти DSP нисбат ба шумораи омилҳои сода ё индекси тартибии адади сода бештар ба бузургии калонтарин омили сода ҳассос аст. Ин тафсири таҷрибавӣ ва назариявии худи манбаъ аст; набояд онро ҳамчун натиҷаи универсалии нав барои ҳамаи сохторҳои \(P-1\) дар тақсимоти дигар васеъ кард.

Таҷрибаи 2: Як дараҷаи баланд ба таври назоратшаванда зиёд карда мешавад

Дар таҷрибаи дуюм \(P\)-и 512-bit бо сохтори зерин сохта мешавад:

ва:

истифода мешавад.

Ҳадафи ин тарҳ ин аст, ки ҳангоми назорат кардани дигар шароит дараҷаи адади содаи 3 зиёд карда шуда, фарқи байни IPP1 ва DSP ба таври низомманд мушоҳида шавад.

Барои ҳар \(P\) як \(Q\)-и тасодуфии 512-bit интихоб шуда:

сохта мешавад.

Барои DSP:

• Algorithm 4 implementation-и воқеӣ,
• Algorithm 6 DSPEst estimator,
• Theorem 2 хароҷоти назариявӣ

муқоиса мешаванд.

Барои IPP1 бошад:

• Algorithm 3 implementation-и воқеӣ,
• Algorithm 5 IPP1Est estimator,
• Theorem 1 хароҷоти назариявӣ

муқоиса мешаванд.

Дар Шакли 8 хатҳои хароҷоти назариявӣ, нуқтаҳои estimator ва нуқтаҳои воқеии таҷриба як тамоюли афзоишро наздик пайгирӣ мекунанд. Ин натиҷа дастгирӣ мекунад, ки моделҳои хароҷоти таҳқиқот рафтори implementation-ро дар ин конфигуратсияҳои санҷидашуда хуб ифода мекунанд. Азбаски манбаъ қиматҳои хоми нуқтаҳоро ҳамчун ҷадвал надодааст, қиматҳои мобайнии нав сохта намешаванд.

Тафсири дурусти муқоисаи назариявии %95

Натиҷаи назариявии манбаъ:

• шарти \(p_{\sigma_s}\ge64\),
• функсияи \(\rho_1\)-и Riesel,
• моделҳои хароҷоти Theorem 1 ва Theorem 2-ро

якҷоя истифода мебарад.

Аз ин рӯ гуфтан, ки “DSP сатҳи муваффақияти %95 дорад”, нодуруст аст. Манбаъ мегӯяд, ки дар шароити муайян эҳтимоли рӯйдоде, ки DSP дорои хароҷоти назариявии ҳисоббарории пасттар аз IPP1 аст, ҳадди ақал 0,95 мебошад.

Натиҷаҳое, ки таҳқиқот дастгирӣ мекунад

• DSP варианти навест, ки номзадҳои ададҳои сода ва дараҷаҳои зарурии Pollard P-1-ро дар як тартиби динамикии скан баррасӣ мекунад.
• Дубора истифода бурдани ҳосилҳои қаблан ҳисобшудаи ададҳои сода метавонад хароҷоти сохтани exponent-и баландро кам кунад.
• DSP тақсимоти exponent-ро аз рӯи бузургии адади сода тағйир дода, ҳисобҳои нолозимеро, ки аз бардоштани ҳамаи номзадҳо то \(u_{\max}\) дар IPP1 ба вуҷуд меоянд, кам мекунад.
• Fast Multiplication бо истифода аз дарахти мутавозини зарб дар модели хароҷоти манбаъ нисбат ба Normal Multiplication рафтори беҳтари асимптотикӣ нишон медиҳад.
• Манбаъ дар Шакли 4 нишон медиҳад, ки моделҳои назариявии хароҷоти NM/FM бо хароҷоти таҷрибавӣ хуб мувофиқанд.
• Дар шароити назариявии манбаъ, вақте \(p_{\sigma_s}\ge64\), эҳтимоли истифодашуда барои пасттар будани хароҷоти DSP аз IPP1 ҳадди ақал 0,95 аст.
• Дар таҷрибаҳои махсус сохташудаи 1024-bit-и манбаъ DSP аз се варианти кӯҳнаи муқоисашуда тезтар аст.
• Манбаъ мегӯяд, ки дар ҳолати мавҷудияти дараҷаҳои баланди ададҳои сода бартарии DSP намоёнтар мешавад.
• Дар таҷрибаи назоратии \(u_x\), тамоюлҳои Theorem 1/2, estimator-ҳо ва хароҷоти implementation ба ҳам наздиканд.

Натиҷаҳое, ки таҳқиқот дастгирӣ намекунад

• Наметавон хулоса кард, ки DSP модулҳои умумии 1024-bit RSA-ро самаранок факторизатсия мекунад.
• Нисбатҳои суръати 23,5×, 16,4× ва 35,6×-ро ба ҳамаи калидҳои RSA умумӣ кардан мумкин нест.
• Қимати %95 сатҳи муваффақияти умумии факторизатсияи RSA нест.
• Санҷида нашудааст, ки DSP дар маҷмӯъ аз усулҳои умумимақсади факторизатсия монанди Number Field Sieve тезтар бошад.
• Таҷрибаҳои таҳқиқот муқоисаи quantum factoring нестанд.
• Теоремаҳои мураккабӣ таҳлили пурраи хароҷоти сенарияи нокомии факторизатсияро дар бар намегиранд.
• Performance-и бисёрядроӣ ё суръатбахшидаи GPU санҷида нашудааст.
• Исбот нашудааст, ки дар CPU, arbitrary-precision library ё муҳити implementation-и дигар ҳамон нисбатҳои суръат нигоҳ дошта мешаванд.
• Барои instance-ҳои дар Шакли 7 намоённабудаи 9 ва 10 қиматҳои вақтро аз манбаъ баровардан мумкин нест.

Маҳдудиятҳои асосии усулӣ ва такрорпазирӣ

• Намунаҳои таҷриба бо таъмини махсуси сохтори smooth сохта шудаанд, то бо Pollard P-1 ҳалшаванда бошанд.
• Муқоиса дар як компютери шахсӣ ва бо single-thread иҷро шудааст.
• Матни манбаъ барои таҷрибаи аввал 10 модули 1024-bit мегӯяд, вале Шакли 7 танҳо ҳашт instance нишон медиҳад.
• Ҳамаи баландии bar-ҳои Шакли 7 ҳамчун ҷадвал дода нашудаанд.
• Қиматҳои хоми таҷриба, estimator ва назарияи Шакли 8 дар шакли ҷадвал нашр нашудаанд.
• Бахши мураккабии назариявии DSP/IPP1 возеҳан бо solvable situation маҳдуд шуда, failure scenario хориҷ карда шудааст.
• Дар манбаъ версияи arbitrary-precision arithmetic library, ки дар таҷрибаҳо истифода шудааст, ба таври муфассал гузориш нашудааст.
• Мақола дар контексти назарияи ададҳои классикӣ ва ҳисоббарории классикӣ мебошад; натиҷаи quantum factoring пешниҳод намекунад.

Маънои криптографии таҳқиқот

Алгоритмҳои Pollard P-1 душвории умумии масъалаи асосии integer-factorization-и RSA-ро аз байн намебаранд. Ба ҷойи ин онҳо algebraic weakness-ҳои муайянеро ҳадаф мегиранд, ки ҳангоми prime generation пайдо шуда метавонанд. Саҳми мақола низ ба он равона шудааст, ки ҳангоми мавҷуд будани ҳамин заъфи махсус раванди факторизатсия бо ҳисобҳои нолозими камтар иҷро шавад.

Аз ин рӯ хулосаи дурусти таҳқиқот “RSA дигар шикаста шуд” нест. Ифодаи дурусттар ин аст, ки стратегияи нави traversal/exponent-scaling, ки барои тезонидани факторизатсияи Pollard P-1 дар композитҳои махсуси дорои сохтори smooth \(P-1\) ё \(Q-1\) пешбинӣ шудааст, аз ҷиҳати назариявӣ ва таҷрибавӣ омӯхта шудааст.

Ёддошт оид ба Манбаъ ва Усул

Унвони аслӣ: Dynamic Scaling Pollard’s P-1 Algorithm

Муаллифон: Wenwen Xia; Geng Wang; Dawu Gu.

Тартиби муаллифон: Wenwen Xia якум; Geng Wang дуюм; Dawu Gu сеюм аст.

Муаллифони масъул: Geng Wang ва Dawu Gu.

Муассиса: School of Cyber Science and Engineering, Shanghai Jiao Tong University, Shanghai 200240, China.

Саҳми баробар: Дар манбаъ изҳороти муаллифи якуми баробар ё саҳми баробар мавҷуд нест.

Маҷалла: Cryptography.

Ношир: MDPI.

Ҷилд / шумора / мақола: 10(4), Article 57.

Шумораи саҳифаҳо: 26.

DOI: 10.3390/cryptography10040057.

Academic Editor: Josef Pieprzyk.

Пешниҳод: 14 Июн 2026.

Таҳрир: 23 Июл 2026.

Қабул: 29 Июл 2026.

Нашр: 13 Август 2026.

Ёддошти Version of Record: Дар сабти расмии MDPI Version Notes аввалин PDF-и Version of Record 13 Август 2026 ва версияи навшудаи PDF/HTML 17 Август 2026 нашр шудааст.

Навъи манбаъ: Мақолаи таҳқиқотии тақризшуда; назарияи ададҳо, криптоанализи классикӣ, тарҳи алгоритм, таҳлили мураккабии асимптотикӣ ва таҷрибаи компютерии назоратшавандаро муттаҳид мекунад.

Тақриз: Cryptography маҷаллаи тақризшавандаи MDPI мебошад. Маводи submission-и маҷалла раванди single-anonymized peer review-ро хабар медиҳад.

Ҳолати preprint: Манбаи коркардшуда Version of Record-и нашршуда аст; дар ин мақола preprint-и алоҳида асос гирифта нашудааст.

Иҷозатнома: Creative Commons Attribution 4.0 International (CC BY 4.0).

Пайванди расмӣ: https://doi.org/10.3390/cryptography10040057

Калимаҳои калидӣ: cryptanalysis; RSA; integer factorization; Pollard’s P-1.

Саҳми асосии илмӣ: Dynamic Scaling Pollard’s P-1 (DSP) ва Fast Multiplication (FM).

Алгоритмҳои муқоисашуда: DSP; IPP1; Pollard P-1-и аслӣ; варианти trivial-и Pollard P-1-и Bishop.

Моделҳои назариявӣ: Аз таркиби хароҷоти multiplication-и ададҳои бутуни калон, sliding-window modular powering, binary normal powering ва GCD estimator-ҳои хароҷоти DSP/IPP1 сохта шудаанд.

Хусусияти асосии DSP: Ҷудо кардани номзадҳои ададҳои сода ба фосилаҳои бузургии double-exponential, марҳила ба марҳила бурдани ададҳои содаи хурдтар ба сатҳҳои дараҷаи баландтар ва дубора истифода бурдани ҳосилҳои қаблан ҳисобшудаи ададҳои сода.

Хусусияти FM: Дарахти мутавозини multiplication, ки элементҳои симметрии канории рӯйхати афзояндаро pairwise зарб карда, дар ҳар давр рӯйхатро тақрибан ба нисф кам мекунад.

Таҷрибаи аввал: \(P-1\) тавре тавлид шудааст, ки ҳосили чанд адади тасодуфии 30-bit бошад; аз \(P\)-и 512-bit ва \(Q\)-и тасодуфии тақрибан ҳамон андоза модулҳои санҷишии 1024-bit \(N=PQ\) сохта шудаанд.

Муҳити таҷрибаи аввал: Ubuntu 20.04.1; x86-64; Intel Core i5-9500 @ 3.00 GHz; 16 GB RAM; single thread.

Натиҷаи асосии таҷрибаи аввал: Манбаъ хабар медиҳад, ки DSP тақрибан аз IPP1 23,5×, аз Pollard P-1-и аслӣ 16,4× ва аз варианти trivial 35,6× тезтар аст.

Номувофиқии дохилии манбаъ дар таҷрибаи аввал: Матн аз 10 test instance-и 1024-bit хабар медиҳад, дар ҳоле ки дар меҳвари x-и намоёни Шакли 7 танҳо instance 1-8 ҳастанд. Манбаъ ин фарқро шарҳ намедиҳад.

Таҷрибаи дуюм: \(P=2\times3^{u_x}\times1073741789\times z+1\), \(u_x\in\{0,20,40,60,80,100\}\); \(Q\)-и тасодуфии 512-bit; муқоисаи назария-estimator-таҷриба барои DSP ва IPP1.

Натиҷаи назариявии %95: Дар шарти \(p_{\sigma_s}\ge64\), аз баровардани асосёфта ба функсияи \(\rho_1\)-и Riesel барои шарти хароҷоти ба нафъи DSP истифодашуда эҳтимоли ҳадди ақал 0,95 ба даст меояд. Ин сатҳи муваффақияти шикастани RSA нест.

Репозитории код: https://github.com/Summwer/expemeriment_of_pollardpm1 — дар манбаъ санаи дастрасӣ 1 Август 2026 дода шудааст.

Маблағгузорӣ: National Cryptologic Science Fund of China, No. 2025NCSF02017.

Дастрасии додаҳо: Муаллифон мегӯянд, ки додаҳои хоми дастгиркунандаи натиҷаҳо бо дархост пешниҳод мешаванд.

Бархӯрди манфиатҳо: Муаллифон изҳор мекунанд, ки бархӯрди манфиатҳо вуҷуд надорад.

Саҳми муаллифон: Conceptualization, methodology, software, validation, formal analysis, investigation, data curation ва original draft: Wenwen Xia; resources: Dawu Gu; visualization: Wenwen Xia ва Geng Wang; supervision ва project administration: Geng Wang ва Dawu Gu; funding acquisition: Geng Wang ва Dawu Gu.

Кумитаи этика / розигии огоҳона: Дар манбаъ изҳороти ҷудогонаи кумитаи этика ё informed-consent вуҷуд надорад; таҳқиқот алгоритми математикӣ ва таҷрибаи синтетикӣ/ҳисоббарории факторизатсия мебошад.

Маҳдудиятҳои асосии усулӣ: Таҳлили назариявии cost analysis сенарияи нокомиро хориҷ мекунад; модулҳои таҷрибавӣ бо таъмини сохтори smooth-и мувофиқ ба Pollard P-1 сохта шудаанд; муқоиса дар як мошин ва single-thread аст; дар таҷрибаи аввал номувофиқии шумораи instance байни матн ва график вуҷуд дорад; додаҳои хоми рақамии Шакли 7-8 ҳамчун ҷадвал дода нашудаанд.

Ҳадди умумии тафсир: Таҳқиқот дастгирӣ мекунад, ки дар модулҳои дорои сохтори мувофиқи smooth \(P-1\) ё \(Q-1\), факторизатсияи Pollard P-1 бо DSP ва FM тезонда шавад; аммо arbitrary RSA modulus, муқоисаи умумии NFS ё хулосаи амалан шикастани ҳамаи калидҳои муосири RSA-ро дастгирӣ намекунад.