Ushbu tadqiqot Ekerå–Håstad kvant algoritmining qisqa diskret logarifm muammosini (short discrete logarithm problem, short DLP) bitta kvant ishga tushirishida yechish ehtimoli uchun simulyatsiyaga asoslanmagan matematik quyi chegarani keltirib chiqaradi va bu chiqishni klassik tarzda qayta ishlash uchun zarur hisoblash xarajatini yuqoridan chegaralaydi. Asosiy natija shundan iboratki, mos parametrlar va klassik post-processing tanlovi bilan qisqa logarifm \(d\) ni bir martalik ishga tushirishda tiklashning nazariy muvaffaqiyat quyi chegarasi \(1-10^{-10}\) darajasigacha oshirilishi mumkin. Bunday yuqori muvaffaqiyat ehtimoli kvant qismini kattalashtirishdan ko‘ra, kvant o‘lchovidan chiqadigan \((j,k)\) juftligini panjara asosidagi klassik qayta ishlashda meet-in-the-middle yoki kam xotirali random-walk usullaridan foydalanish orqali olinadi. Natijalar matematik va mantiqiy kvant sxemalari uchun; jismoniy kvant xato ko‘rsatkichlari va kvant xatolarini tuzatish yuklamasi hisobga olinmaydi.

Tadqiqotning muhim hissasi ilgari simulyatsiyalar yordamida o‘rganilgan muvaffaqiyat xatti-harakatini qat’iy ehtimollik va murakkablik chegaralari bilan almashtirishidir. Algoritm tartibi noma’lum bo‘lgan siklik guruhda \(x=g^d\) munosabatidagi qisqa \(d\) qiymatini nishonga oladi. Kvant qismida ikkita Fourier namunaviy chiqishi \(j\) va \(k\) hosil qilinadi, klassik qismda esa bu qiymatlar ikki o‘lchovli panjara muammosi orqali \(d\) ni topish uchun qayta ishlanadi.

Parametrlar orasida aniq xarajat almashinuvi mavjud. \(\Delta\) oshirilganda kvant kompyuterida baholanishi kerak bo‘lgan guruh amallari soni kamayishi mumkin; buning evaziga klassik qidiruv sohasi va post-processing xarajati ortadi. Tadqiqotning 2048 bitli xavfsiz-tub FF-DH misolida \(\Delta=0\) uchun 672 kvant guruh amali berilgan boshlang‘ich nuqtadan, \(\Delta=50\) tanlovi bilan 572 guruh amaligacha tushirish ko‘rsatilgan. Muallifning amaliy tajribalari bu taxminan %15 lik kamayish tanlangan parametrlarda klassik post-processing hali ham amaliy darajada saqlangan holda erishilishi mumkinligini bildiradi.

Qisqa diskret logarifm muammosi nima?

Tadqiqotda ko‘rib chiqilgan qisqa DLP da tartibi \(r\) bo‘lgan siklik guruh generatori \(g\) va

\[ x=g^d \]

qiymati beriladi. Maqsad \(d\ll r\) shartidagi qisqa diskret logarifm \(d\) ni hisoblashdir. Ushbu tadqiqotning muhim xususiyati guruh tartibi \(r\) ma’lum bo‘lishi shart emasligidir.

\(m\), \(d\) ning bit uzunligi uchun yuqori chegara sifatida

\[ d<2^m \]

qabul qilinadi. Maqola, shuningdek,

\[ \ell=m-\Delta \]

parametrini ta’riflaydi. \(\Delta\) kvant qismi xarajati bilan keyinchalik bajariladigan klassik qidiruv o‘rtasidagi almashinuvda markaziy rol o‘ynaydi.

Ekerå–Håstad yondashuvi Shor algoritmidan qaysi jihatdan farq qiladi?

Shorning asl diskret logarifm algoritmi ma’lum tartibli siklik guruhlarda umumiy diskret logarifmlarni ko‘rib chiqsa, bu yerda tahlil qilinayotgan Ekerå–Håstad yondashuvi guruh tartibi noma’lum bo‘lgan holatda qisqa logarifmlarni nishonga oladi.

Tadqiqot bu xususiyat, ayniqsa, xavfsiz-tub guruhlarda qisqa darajadan foydalanadigan chekli maydon Diffie–Hellman tizimlari va RSA butun sonlarni faktorlash muammosini qisqa DLP ga keltirish nuqtai nazaridan kriptoanalitik ahamiyatga ega ekanini ta’kidlaydi.

Kvant algoritmi qanday holatni hosil qiladi?

Algoritm avval \(a\) va \(b\) qiymatlari ustida tekis superpozitsiyalar yaratadi va ish registrida

\[ g^a x^{-b}=g^{a-bd} \]

qiymatini hisoblaydi. QFT dan oldingi holat manbada quyidagicha berilgan:

\[ \frac{1}{\sqrt{2^{m+2\ell}}} \sum_{a=0}^{2^{m+\ell}-1} \sum_{b=0}^{2^\ell-1} |a,b,g^{a-bd}\rangle . \]

So‘ngra dastlabki ikki boshqaruv registriga mos ravishda \(2^{m+\ell}\) va \(2^\ell\) o‘lchamli kvant Fourier o‘zgartirishlari (QFT) qo‘llanadi. Boshqaruv registrlari o‘lchanganda \(j\) va \(k\) qiymatlari olinadi.

Maqola oxiridagi 1-rasm ushbu sxemani bevosita ko‘rsatadi: birinchi boshqaruv registri \(g^a\) ni hosil qilishni, ikkinchi boshqaruv registri \(x^{-b}\) komponentini, ish registri esa ularning guruh amali bilan birlashtirilishini bajaradi. Har ikkala boshqaruv registrida QFT va o‘lchash amallari mavjud.

Ikkinchi sxema tuzilishi nega muhim?

2-rasm ayni matematik amalni qayta tartiblab, avval \(j\) ni, so‘ng \(j\) ma’lum bo‘lganda \(k\) ni hisoblash mumkinligini ko‘rsatadi. Bu qayta tartib ikki boshqaruv registrini bir vaqtning o‘zida saqlash zaruratini kamaytiradi.

Manbaga ko‘ra standart tuzilishda ikki boshqaruv registrining jami o‘lchami \(m+2\ell\) qubit bo‘lsa, amallarni qayta ketma-ketlashtirish orqali bir vaqtda kerak bo‘ladigan boshqaruv maydoni \(m+\ell\) qubitgacha qisqartiriladi. Maqola yarim-klassik QFT va boshqaruv qubitini qayta ishlatish orqali ikki boshqaruv registrining vazifasini bitta qayta ishlatiladigan boshqaruv qubiti bilan bajarish mumkinligini ham tushuntiradi; bu optimallashtirish asosiy tahlil mavzusi emas, balki sxemani amalga oshirishga oid izoh sifatida berilgan.

Kvant qismidagi asosiy xarajat nima?

Tadqiqotda kvant xarajatining ustun qismi ikkita darajaga oshirish amali sifatida qaraladi. Bir ishga tushirishda baholanishi kerak bo‘lgan guruh amallari soni

\[ m+2\ell \]

bo‘lib, \(\ell=m-\Delta\) bo‘lgani uchun:

\[ m+2\ell=3m-2\Delta. \]

Shunday qilib, \(\Delta=0\) holatda xarajat \(3m\) guruh amali miqyosidadir. \(\Delta\) ni oshirish kvant amallari sonini kamaytiradi; biroq keyingi bo‘limlarda ko‘rsatilganidek, klassik qidiruv xarajatini oshiradi.

\(j\) va \(k\) o‘lchovlari logarifm haqida qanday ma’lumot tashiydi?

Tadqiqot o‘lchovdan olingan juftlik uchun

\[ \alpha_d=\alpha(j,k) =\{dj+2^mk\}_{2^{m+\ell}} \]

va unga mos

\[ \theta_d= \frac{2\pi\alpha_d}{2^{m+\ell}} \]

burchakni ta’riflaydi. Bu yerdagi \(\{u\}_n\), \(u\) ning modulo \(n\) bo‘yicha markazlashtirilgan intervalga keltirilgan qiymatini bildiradi.

Isbotning muhim qismlaridan biri \(j\) ning

\[ [0,2^{m+\ell}) \]

oraliqdagi butun sonlar orasidan tekis taqsimot bilan tanlanishini ko‘rsatishdir. Sxemani amalga oshirishda \(j\) avval hisoblanishi mumkin; undan keyin \(k\), berilgan \(j\) shartida kvant ehtimollik taqsimotiga ko‘ra o‘lchanadi.

\(\tau\)-good juft nima?

Klassik post-processing muvaffaqiyatli ishlashi uchun muallif quyidagi ta’rifdan foydalanadi. \((j,k)\) juft

\[ \left| \{dj+2^mk\}_{2^{m+\ell}} \right| \leq 2^{m+\tau} \]

shartini bajarsa, \(\tau\)-good deb ataladi. Bu yerda

\[ \tau\in[0,\ell]\cap\mathbb Z. \]

\(\tau\) oshirilganda “yaxshi” deb qabul qilinadigan o‘lchov natijalari sohasi kengayadi va shu sabab muvaffaqiyatli o‘lchov olish ehtimoli ortadi; buning evaziga klassik panjara qidiruvi qamrab olishi kerak bo‘lgan soha ham kattalashishi mumkin.

\(\tau\)-good juft ehtimoli uchun qanday chegara isbotlanadi?

Lemma 1, sobit \(j\) uchun o‘lchangan \(k\) ning \(\tau\)-good juft hosil qilish ehtimolini quyidan chegaralaydi:

\[ P_{\tau\text{-good}} \geq 1-\psi'(2^\tau) \]

va trigamma funksiyasi uchun ishlatilgan yuqori chegara tufayli

\[ P_{\tau\text{-good}} > 1- \frac{1}{2^\tau} - \frac{1}{2\cdot2^{2\tau}} - \frac{1}{6\cdot2^{3\tau}}. \]

Bu eksperimental muvaffaqiyat foizi emas. Kvant algoritmining matematik ehtimollik taqsimotidan keltirib chiqarilgan analitik quyi chegaradir.

Nega panjara klassik post-processing markazida?

Tadqiqot o‘lchangan \(j\) uchun ikki o‘lchovli

\[ L^\tau(j) = \langle (j,2^\tau), (2^{m+\ell},0) \rangle \]

panjarani quradi.

\((j,k)\) juft \(\tau\)-good bo‘lganda ma’lum

\[ v= (\{-2^mk\}_{2^{m+\ell}},0) \]

vektor bilan \(d\) ni o‘z ichiga oladigan noma’lum

\[ u= (dj+2^{m+\ell}z,2^\tau d) \]

vektor bir-biriga yaqin bo‘ladi. Tadqiqotda bu yaqinlik

\[ \|u-v\|<2^{m+\tau}\sqrt 2 \]

ko‘rinishida chegaralanadi.

Shunday qilib muammo \(v\) atrofidagi muayyan radius ichida \(L^\tau(j)\) ning mos vektorini topishga aylanadi.

\(t\)-balanced panjara nimani anglatadi?

Panjaraning eng qisqa nol bo‘lmagan vektori normasi \(\lambda_1\) bo‘lsin. Tadqiqot

\[ \lambda_1\geq2^{m-t} \]

shartini bajaradigan \(L^\tau(j)\) panjarani \(t\)-balanced deb ta’riflaydi.

Lemma 2 ga ko‘ra panjaraning \(t\)-balanced bo‘lmaslik ehtimoli ko‘pi bilan

\[ 2^{\Delta-2(t-1)-\tau} \]

bo‘ladi, shuning uchun \(t\)-balanced bo‘lish ehtimoli uchun

\[ P_{\mathrm{balanced}} \geq 1-2^{\Delta-2(t-1)-\tau} \]

ko‘rinishidagi quyi chegara olinadi; manfiy bo‘lishi mumkin bo‘lgan parametr sohalari asosiy teoremda nol bilan chegaralanadi.

Asosiy muvaffaqiyat ehtimoli chegarasi

Theorem 1 va Theorem 2, \(\tau\)-good juft va \(t\)-balanced panjara ehtimollarini birlashtiradi. Natijada qisqa logarifmni maqsadli klassik xarajat chegarasi ichida tiklashning muvaffaqiyat quyi chegarasi

\[ P_{\mathrm{success}} \geq \max\left( 0, 1- \frac{1}{2^\tau} - \frac{1}{2\cdot2^{2\tau}} - \frac{1}{6\cdot2^{3\tau}} \right) \max\left( 0, 1-2^{\Delta-2(t-1)-\tau} \right) \]

ko‘rinishida beriladi.

Bu formula tadqiqotning eng muhim natijasidir: muvaffaqiyat ehtimolini oshirish bilan klassik post-processing sohasini kengaytirish o‘rtasidagi bog‘lanishni bevosita matematik tarzda ifodalaydi.

Birinchi klassik yechim: meet-in-the-middle

Birinchi post-processing usuli Shanksning baby-step giant-step yondashuvini ikki o‘lchovga kengaytirgan deterministik meet-in-the-middle qidiruvidir.

Tadqiqot avval Lagrange-reduced panjara bazasi \((s_1,s_2)\) ni hisoblaydi. Babai nearest-plane algoritmi bilan ma’lum \(v\) vektoriga yaqin panjara nuqtasi \(o\) topiladi. So‘ng qidiruv \(o\) atrofidagi cheklangan ikki o‘lchovli sohaga qisqartiriladi.

Theorem 1 uchun

\[ N= 2^{\Delta+\tau+1} + 2^{\tau+t+2} + 2 \]

ta’riflanadi. Musbat butun sonli sobit \(c\) uchun, bir nechta guruh elementlari oldindan hisoblangan bo‘lishi sharti bilan kerakli guruh amallari soni ko‘pi bilan

\[ 2^3c\sqrt N = 8c\sqrt N \]

deb yuqoridan chegaralanadi.

Lookup jadvalida saqlanishi kerak bo‘lgan butun sonlar miqdori esa ko‘pi bilan

\[ \frac{8\sqrt N}{c}+3 \]

bo‘ladi. \(c\) ni oshirish xotira sarfini kamaytiradi, biroq ikkinchi qidiruv bosqichidagi ishni oshiradigan vaqt-xotira almashinuvini yaratadi.

Ikkinchi klassik yechim: random walk va Gaudry–Schost

Meet-in-the-middle yondashuvida katta parametrlar uchun xotira asosiy cheklovga aylanishi mumkin. Shu sababli tadqiqot ikkinchi yechimni taklif qiladi: panjara qidiruvini ikki o‘lchovli qisqa DLP ga aylantirish va Gaudry–Schost algoritmini Galbraith–Ruprai yaxshilanishlari bilan qo‘llash.

Bu usul katta deterministik lookup jadvali o‘rniga ehtimolli random-walk yondashuvidan foydalanadi va xotira ehtiyojini \(O(1)\) guruh elementi darajasiga tushiradi.

Theorem 2 uchun

\[ N= 2^{\Delta+\tau+4} + 2^{\tau+t+5} + 5 \]

bo‘lib, ideallashtirilgan modelda eng yaxshi, o‘rtacha va eng yomon holat uchun kutilayotgan guruh amallari soni

\[ \left(\frac{4}{3}+o(1)\right)\sqrt{\pi N} \]

bilan yuqoridan chegaralanadi.

Bu yerda natija kutilayotgan murakkablikdir va Gaudry–Schost tahlilining ideallashtirilgan modeliga asoslanadi; deterministik mutlaq ish vaqti sifatida talqin qilinmasligi kerak.

\(\Delta\), \(\tau\) va \(t\) parametrlari nimani o‘zgartiradi?

Muvaffaqiyat ehtimolini qanchagacha oshirish mumkin?

Tadqiqotning 1-jadvali \(\Delta=0\) uchun klassik ish yuklamasi bilan isbotlangan muvaffaqiyat quyi chegarasi qanday o‘zgarishini aniq ko‘rsatadi:

Bu qiymatlar eksperimental kuzatuv ko‘rsatkichlari emas. Theorem 1 dan olingan kafolatlangan matematik quyi va yuqori chegaralarning tanlangan parametr kombinatsiyalaridir.

\(\Delta\) kattalashganda nima bo‘ladi?

1-jadval va 2-jadval birgalikda ko‘rilganda asosiy tendensiya ravshan: bir xil maqsadli muvaffaqiyat ehtimoli saqlangan holda \(\Delta\) oshirilsa, klassik enumeration xarajati sezilarli darajada ortadi.

Masalan, \(1-10^{-10}\) muvaffaqiyat quyi chegarasi uchun:

Shuning uchun kvant xarajatini kamaytirish maqsadida \(\Delta\) ni doimiy ravishda oshirish tekin optimallashtirish emas. Kvant hisoblash kamayadi, biroq klassik hisoblash va meet-in-the-middle qo‘llansa xotira talabi tez ortadi.

FF-DH misollarida kvant amal soni qanday o‘zgaradi?

Tadqiqotning 3-jadvali xavfsiz-tub FF-DH guruhlari uchun Ekerå–Håstad algoritmining kvant guruh amallari sonini

\[ o_{\mathrm{EH}}=3m-2\Delta \]

ko‘rinishida ishlatadi. 2048 bitli xavfsiz-tub va \(m=224\) bitli qisqa daraja misolida manba quyidagi qiymatlarni beradi:

\(\Delta=50\) misoli 672 dan 572 kvant guruh amaliga o‘tishni anglatadi. Tadqiqotning o‘z bahosiga ko‘ra bu taxminan %15 kvant guruh amali kamayishidir. Buning evaziga klassik ish yuqori chegarasi \(\log_2\) o‘lchovida 22,1 dan 33,6 gacha oshadi.

Muallif optimallashtirilgan parallel amalga oshirishdagi dastlabki tajribalarda \(\Delta=50\) va kamida %99 muvaffaqiyat maqsadida oddiy kompyuterda post-processing bajarish odatda muammo tug‘dirmaganini bildiradi. Bu amaliy tajribaga asoslangan kuzatuv bo‘lib, tadqiqotning matematik teoremidan alohida qayd etilgan.

RSA nuqtai nazaridan tadqiqot nima deydi?

Tadqiqot RSA butun sonni faktorlash muammosini qisqa DLP ga keltirish orqali shu muvaffaqiyat tahlili doirasini RSA ga qo‘llashni ham ko‘rib chiqadi. Biroq bunda qo‘shimcha shart bor: tasodifiy tanlangan \(g\) yetarlicha katta tartibga ega bo‘lishi kerak.

RSA uchun 4-jadval ushbu qo‘shimcha ehtimol kamaytirish omilini \(f(\Delta)\) orqali hisobga oladi. Masalan \(\Delta=20\) uchun manba kamaytirish omilini kamida

\[ f(20)\geq0{,}999867 \]

deb oladi. Shu parametrlar oilasida:

Bu jadval mavjud jismoniy kvant kompyuterida RSA kaliti ko‘rsatilgan miqdordagi amallar bilan buziladi degani emas. Tadqiqot bu yerda algoritmik muvaffaqiyat ehtimoli va klassik enumeration xarajatini tahlil qiladi; jismoniy qubit, xatolarni tuzatish, darvoza xatosi va umumiy haqiqiy ish vaqti bu hisobdan tashqarida qoladi.

Asimptotik natija nega muhim?

Corollary 1 muammo o‘lchami \(m\) cheksizga borganda \(\Delta\), \(\tau\) va \(t\) ni \(m\) ga bog‘liq ravishda tanlash orqali muvaffaqiyat ehtimoli quyi chegarasini birga yaqinlashtirish mumkinligini, shu bilan bir vaqtda klassik enumeration murakkabligini

\[ O(\mathrm{poly}(m)) \]

doirasida saqlash mumkinligini ko‘rsatadi.

Masalan, tadqiqot \(\Delta\) va \(t\) ni sobit saqlab,

\[ \tau=\log_2 f(m) \]

tanlash mos super-sobit, biroq polinom bilan chegaralangan \(f(m)\) uchun ushbu natijani ta’minlashi mumkinligini tushuntiradi.

Tadqiqot qo‘llab-quvvatlaydigan natijalar

• Ekerå–Håstad qisqa DLP algoritmining bitta ishga tushirishdagi muvaffaqiyat ehtimoli uchun simulyatsiyaga asoslanmagan qat’iy quyi chegaralar olinishi mumkin.
• Mos klassik post-processing parametrlarida muvaffaqiyat ehtimoli quyi chegarasi \(1-10^{-10}\) darajasigacha oshirilishi mumkin.
• Meet-in-the-middle qidiruvi cheklangan panjara enumeration muammosini deterministik tarzda tezlashtiradi.
• Gaudry–Schost asosidagi random-walk yondashuvi shu qidiruv muammosining xotira talabini \(O(1)\) guruh elementigacha kamaytirishi mumkin.
• \(\Delta\) ni oshirish kvantda kerakli guruh amallarini kamaytiradi, biroq klassik post-processing xarajatini oshiradi.
• Tahlil xavfsiz-tub qisqa darajali FF-DH ssenariylariga bevosita, RSA ga esa qisqa DLP keltirish orqali qo‘llanadi.
• Parametrlar muammo o‘lchamiga mos miqyoslanganda muvaffaqiyat quyi chegarasi asimptotik ravishda birga yaqinlashishi, klassik post-processing esa polinom vaqtda qolishi mumkin.

Tadqiqot isbotlamaydigan natijalar

• Tadqiqot haqiqiy kvant kompyuterida RSA yoki FF-DH buzish tajribasini bajarmaydi.
• Nazariy muvaffaqiyat ehtimoli jismoniy kvant apparatining xato qilmaslik ehtimoli emas.
• Tahlil kvant xatolarini tuzatish yukini yoki jismoniy qubit xarajatini hisoblamaydi.
• Guruh amallari sonini bevosita soniya, kvant darvozasi yoki jismoniy qubit soniga tenglashtirib bo‘lmaydi.
• Random-walk usulining berilgan murakkabligi ideallashtirilgan modeldagi kutilayotgan murakkablikdir.
• \(\Delta\) ni oshirish umumiy xarajatni kamaytirmaydi; klassik vaqt va/yoki xotira xarajati ortadi.
• RSA qo‘llanmasida qisqa DLP keltirishning qo‘shimcha tartib sharti va unga bog‘liq muvaffaqiyat kamaytirish omilini e’tibordan chetda qoldirib bo‘lmaydi.

Tadqiqot usuli va topilmalar

Tadqiqot dizayni

Tadqiqot eksperimental kvant apparati tadqiqoti emas, balki nazariy kriptografiya va kvant algoritmlari sohasidagi matematik muvaffaqiyat ehtimoli va murakkablik tahlilidir. Asosiy maqsad ilgari simulyatsiyaga asoslangan muvaffaqiyat bahosining o‘rniga isbotlangan quyi chegaralarni qo‘yishdir.

Tahlil to‘rt asosiy bosqichda olib boriladi:

1. Kvant algoritmining \((j,k)\) o‘lchov taqsimoti tahlil qilinadi.
2. \((j,k)\) ning \(\tau\)-good bo‘lish ehtimoli quyidan chegaralanadi.
3. \(L^\tau(j)\) panjaraning \(t\)-balanced bo‘lish ehtimoli quyidan chegaralanadi.
4. Bu ikki hodisa sodir bo‘lganda \(d\) ni tiklaydigan klassik enumeration amali xarajati yuqoridan chegaralanadi.

Lemma 1 ning roli

Lemma 1 ma’lum \(j\) uchun o‘lchangan \(k\) ning mos faza hududiga tushish ehtimolini tahlil qiladi. Isbotda ehtimollik taqsimotining musbat va manfiy dumlari alohida-alohida yuqoridan chegaralanadi. Trigonometrik chegaralar va trigamma funksiyasidan foydalanib jami dum ehtimoli nazorat qilinadi.

Natija:

\[ P_{\tau\text{-good}} > 1- 2^{-\tau} - \frac{1}{2}2^{-2\tau} - \frac{1}{6}2^{-3\tau}. \]

Lemma 2 ning roli

Ikkinchi ehtimollik komponenti panjara geometriyasidan keladi. Eng qisqa nol bo‘lmagan vektor juda qisqa bo‘lsa enumeration sohasini nazorat qilish qiyinlashgani uchun \(t\)-balanced sharti qo‘llanadi.

Panjara fundamental sohasi uchun

\[ \lambda_1\lambda_2^\perp = 2^{m+\ell+\tau} \]

munosabatidan va \(j\) ning tekis taqsimlanishidan foydalanib

\[ P(L^\tau(j)\text{ balanced değil}) \leq 2^{\Delta-2(t-1)-\tau} \]

chegarasi olinadi.

Meet-in-the-middle enumeration qanday chegaralanadi?

Lagrange-reduced baza va Babai nearest-plane chiqishi yordamida qidiruv ikki indeks \(m_1\) va \(m_2\) bilan cheklangan to‘g‘ri to‘rtburchak indeks sohasiga qisqartiriladi. Tadqiqot bu sohaning o‘lchamlarini \(B_1\) va \(B_2\) bilan chegaralaydi.

Shanks yondashuvining ikki o‘lchovli umumlashtirilishi barcha \((2B_1+1)(2B_2+1)\) nomzodlarni birma-bir tekshirish o‘rniga qidiruvni ikki qismga ajratadi. Birinchi qism lookup jadvaliga yoziladi, ikkinchi qism esa jadvaldagi mosliklarni izlaydi.

Bu tuzilma nomzodlar soniga taxminan kvadrat ildizli bog‘liqlik beruvchi meet-in-the-middle tezlashtirishining asosidir.

Random-walk yechimi qaysi cheklovni bartaraf etadi?

Meet-in-the-middle usulida lookup jadvali kattalashgani sari xotira tor joyga aylanadi. Shu sabab tadqiqot enumeration muammosini

\[ g_1^{i_1}g_2^{i_2}=x' \]

ko‘rinishidagi ikki o‘lchovli qisqa DLP sifatida qayta yozadi.

Bu muammo Gaudry–Schost algoritmi va Galbraith–Ruprai yaxshilanishi bilan yechilsa, katta lookup jadvali kerak bo‘lmaydi. Natijada xotira sarfi asimptotik ravishda \(O(1)\) guruh elementigacha tushirilishi mumkin.

1-jadval va 2-jadvalning asosiy xabari

1-jadval va 2-jadval \(\Delta\), \(\tau\) va \(t\) o‘zgarganda muvaffaqiyat quyi chegarasi bilan klassik enumeration yuqori chegarasi qanday harakatlanishini ko‘rsatadi. Eng ko‘zga tashlanadigan tendensiya: \(\Delta\) oshishi bilan bir xil muvaffaqiyat darajasiga erishish uchun talab etiladigan klassik ish tez ortadi.

Masalan %99 muvaffaqiyat quyi chegarasida “Work” qiymati \(\Delta=0\) uchun ko‘pi bilan 8,6 bo‘lsa, \(\Delta=50\) uchun 32,1; \(\Delta=100\) uchun 57,1 va \(\Delta=130\) uchun 72,1 sifatida beriladi. “Work” qiymatlari bevosita amal soni emas, manbada ta’riflangan guruh amallari yuqori chegarasining \(\log_2\) ko‘rinishidir.

3-jadvalning asosiy xabari

FF-DH jadvali kvant va klassik xarajat almashinuvini real kriptografik parametrlar orqali yaqqol ko‘rsatadi. Jadvalda 2048, 3072, 4096, 6144 va 8192 bitli xavfsiz-tub guruhlar uchun qisqa daraja uzunliklari berilgan va Ekerå–Håstad algoritmining kvant guruh amallari soni o‘zgartirilgan Shor yondashuvi bilan nisbatlangan.

Masalan 4096 bitli xavfsiz-tub, \(m=304\) bitli qisqa daraja misolida:

• \(\Delta=0\): 912 kvant guruh amali, afzallik 9,0.
• \(\Delta=50\): 812 kvant guruh amali, afzallik 10,0.
• \(\Delta=70\): 772 kvant guruh amali, afzallik 10,5.

Biroq ushbu afzallikning oshishi klassik post-processing xarajatining ortishi bilan birgalikda baholanishi kerak.

4-jadvalning asosiy xabari

RSA jadvali nafaqat qisqa DLP algoritmining muvaffaqiyat chegarasini, balki RSA keltirishida tanlangan guruh elementining yetarlicha katta tartibga ega bo‘lmaslik ehtimolini ham hisobga oladi. Shu bois FF-DH jadvalidan farqli ravishda qo‘shimcha \(f(\Delta)\) kamaytirish omili mavjud.

Tadqiqot \(\Delta\) oshgani sari bu omil birga yaqinlashishini, biroq qo‘llanilgan analitik quyi chegara usulining hisoblash xarajati \(\Delta\) bilan tez o‘sishini qayd etadi. Shu sabab jadvalda juda yuqori muvaffaqiyat maqsadlari uchun barcha qiymatlar berilmagan.

Algoritmlar amalda sinalganmi?

Muallif maqoladagi Algorithm 1 va Algorithm 2 post-processing usullarini amalga oshirganini va simulyatsiya qilingan kvant algoritmi chiqishlarini qayta ishlash orqali ular kutilgan tarzda ishlashini tasdiqlaganini bildiradi.

Shuningdek, optimallashtirilgan va parallellashtirilgan dastlabki amaliy tajribalar \(\Delta=50\) uchun, kamida %99 muvaffaqiyat maqsad qilinganda, oddiy kompyuterda post-processing qilish odatda muammo tug‘dirmaganini ko‘rsatgani aytiladi. Tadqiqot bu amalga oshirishni optimallashtirish va yanada parallellashtirish bo‘yicha ishlar davom etayotganini ham aniq bildiradi.

1-rasm va 2-rasmning ilmiy xabari

1-rasm \(m+\ell\) qubitlik birinchi va \(\ell\) qubitlik ikkinchi boshqaruv registrini, \(g^a\) va \(x^{-b}\) boshqariladigan guruh amallarini, QFT bloklarini hamda \(j,k\) o‘lchovlarini bitta sxemada ko‘rsatadi.

2-rasm matematik jihatdan ekvivalent sxemani vaqt bo‘yicha qayta tartiblaydi. Birinchi boshqaruv registrining QFT va o‘lchovi \(g^a\) amalidan darhol keyinga ko‘chiriladi, ikkinchi boshqaruv registri esa keyinroq tayyorlanadi. Natijada \(j\) ni avval hisoblab, \(k\) ni \(j\) ga bog‘liq holda keyin olish Lemma 1 ning ehtimollik tahlilida ishlatilgan tuzilma bilan vizual mos keladi.

Tadqiqotning asosiy miqdoriy topilmalari

Tadqiqotning asosiy kuchli tomonlari

• Ilgari simulyatsiya bilan baholangan single-run muvaffaqiyat xatti-harakatini analitik quyi chegaralar bilan qo‘llab-quvvatlashi.
• Kvant xarajati va klassik post-processing xarajatini bir parametrlar oilasi ichida birgalikda baholashi.
• Muvaffaqiyat ehtimolidan tashqari klassik enumeration murakkabligini ham ochiq yuqori chegara bilan taqdim etishi.
• Vaqt-xotira almashinuvli deterministik va kam xotirali ehtimolli ikkita turli post-processing yondashuvini taklif qilishi.
• FF-DH va RSA keltirish uchun alohida parametr jadvallarini taqdim etishi.
• Post-processing algoritmlarining simulyatsiya qilingan kvant chiqishlari ustida amalda tekshirilgan bo‘lishi.

Tadqiqotning asosiy cheklovlari

• Asosiy matematik tahlil kvant kompyuteri algoritmni matematik ta’rifiga muvofiq va hisoblash xatosisiz bajaradi deb faraz qiladi.
• Kvant xatolarini tuzatishning jismoniy va hisoblash yuklamasi tahlilga kiritilmagan.
• Tahlil mantiqiy kvant sxemalari va mantiqiy xarajatlar bilan cheklangan.
• Qisqa DLP tahlili \(r\geq2^{m+\ell}+(2^\ell-1)d\) ko‘rinishidagi qisqalik shartidan foydalanadi; RSA holatida bu shart qo‘shimcha ehtimol omilini talab qiladi.
• Gaudry–Schost usuli uchun berilgan ish miqdori ideallashtirilgan modeldagi kutilayotgan qiymatdir.
• Katta \(\Delta\) qiymatlarida meet-in-the-middle post-processing xotira talabi amaliy qo‘llanishni cheklashi mumkin.
• Optimallashtirilgan parallel post-processing amalga oshirish natijalari dastlabki xarakterda va muallif yanada optimallashtirish ishlari davom etayotganini bildiradi.

Manba va usul izohi

To‘liq asl ish nomi: On the success probability of the quantum algorithm for the short DLP

Muallif: Martin Ekerå.

Mualliflar soni: Bir.

Ham-birinchi muallif/ham-hissa: Qo‘llanmaydi; ish bitta muallifniki.

Mas’ul muallif: Manbada alohida “corresponding author” belgisi ishlatilmagan. Martin Ekerå uchun aloqa e-pochtasi berilgan.

Affiliatsiyalar: KTH Royal Institute of Technology, Stockholm, Sweden; Swedish NCSA, Swedish Armed Forces, Stockholm, Sweden.

Jurnal: IACR Communications in Cryptology.

Jild / son: 3 / 1.

ISSN: 3006-5496.

Sahifa uzunligi: 32 sahifa.

DOI: 10.62056/an2isgsfg

Rasmiy nashr havolasi: https://doi.org/10.62056/an2isgsfg

Nashriyot / nashr tashkiloti: International Association for Cryptologic Research (IACR).

Manba turi: Taqrizdan o‘tgan tadqiqot maqolasi.

Taqriz holati: Taqrizli jurnalda nashr etilgan ish. IACR Communications in Cryptology to‘liq taqrizli jurnal bo‘lib, jurnalning rasmiy siyosatida ikki tomonlama anonim taqriz qo‘llanilishi qayd etilgan.

Topshirilgan sana: 2-fevral 2026.

Qabul qilingan sana: 23-aprel 2026.

Nashr sanasi: 4-may 2026.

Preprint aloqasi: Ishning oldingi versiyalari arXiv:2309.01754 ostida e’lon qilingan. arXiv qaydi yakuniy jurnal nashriga va DOI 10.62056/an2isgsfg ga havola beradi. Ushbu Verianla maqolasidagi ilmiy bayon foydalanuvchi yuklagan nashr qilingan 32 sahifalik versiyaga asoslangan.

Litsenziya: Creative Commons Attribution 4.0 (CC BY 4.0). Mualliflik huquqi muallif(lar)da qoladi.

Moliyalashtirish va qo‘llab-quvvatlash: Tadqiqotda moliyalashtirish va qo‘llab-quvvatlash Swedish NCSA tomonidan berilgani; Swedish NCSA Swedish Armed Forces tarkibida ekani aytiladi. Hisoblashlar shuningdek Swedish Research Council grant agreement no. 2022-06725 bilan qisman moliyalashtirilgan National Academic Infrastructure for Supercomputing in Sweden (NAISS) doirasida KTH PDC resurslarida bajarilgan.

Tashakkur: Muallif Johan Håstad ga izoh va tavsiyalari uchun, Joel Gärtner ga esa dastlabki preprint versiyasidagi Lemma 3 muammosiga e’tibor qaratgani uchun minnatdorlik bildiradi.

Ma’lumot va dasturiy ta’minot izohi: Tadqiqot eksperimental ma’lumotlar to‘plamiga asoslanmaydi. Muallif post-processing algoritmlarini amalga oshirganini va simulyatsiya qilingan kvant algoritmi chiqishlari bilan tekshirganini bildiradi. Maqolada ochiq, biroq optimallashtirilmagan Algorithm 1 amalga oshirishi va simulyator uchun Quaspy dasturiy omboriga havola berilgan.

Manfaatlar to‘qnashuvi: Yuklangan ishda alohida manfaatlar to‘qnashuvi bo‘limi aniqlanmagan.

Muallif hissalari: Ish bitta muallifli va alohida CRediT hissa bayonoti berilmagan.

Asosiy usul: Ekerå–Håstad qisqa DLP kvant algoritmining o‘lchov taqsimotini analitik chegaralash; ikki o‘lchovli panjara tahlili; Lagrange reduksiyasi va Babai nearest-plane usuli; meet-in-the-middle enumeration; ikki o‘lchovli qisqa DLP ga keltirish va Gaudry–Schost/Galbraith–Ruprai random-walk tahlili.

Ilmiy mazmun chegarasi: Ushbu Verianla maqolasidagi algoritmik mexanizmlar, formulalar, sonli jadvallar, FF-DH va RSA natijalari, amalga oshirish kuzatuvlari va cheklovlar yuklangan manba ishiga asoslangan. Tashqi manbalar faqat ish identifikatori, nashr sanasi, jurnal holati, DOI, litsenziya va preprint-nashr munosabatini bibliografik tekshirish uchun ishlatilgan; PDF tashqarisidan yangi ilmiy topilma qo‘shilmagan.

Eng muhim talqin chegarasi: Tadqiqotning muvaffaqiyat ehtimoli va xarajat chegaralari mantiqiy kvant algoritmiga tegishlidir. Jismoniy apparat xatolari, kvant xatolarini tuzatish va buning qo‘shimcha jismoniy resurs xarajatlari ushbu tahlilda yo‘q.