Bu tədqiqat Ekerå–Håstad kvant alqoritminin qısa diskret loqarifm problemini (short discrete logarithm problem, short DLP) bir kvant icrasında həll etmə ehtimalı üçün simulyasiyaya əsaslanmayan riyazi aşağı sərhəd çıxarır və bu çıxışın klassik emalı üçün lazım olan hesablama xərcini yuxarıdan məhdudlaşdırır. Əsas nəticə, uyğun parametr və klassik post-processing seçimi ilə qısa loqarifm \(d\)-nin bir icrada bərpa edilməsinə dair nəzəri uğur aşağı sərhədinin \(1-10^{-10}\) səviyyəsinə qədər yüksəldilə bilməsidir. Bu yüksək uğur ehtimalı kvant hissəsini böyütməkdən daha çox, kvant ölçməsindən çıxan \((j,k)\) cütünün qəfəs əsaslı klassik emalında meet-in-the-middle və ya aşağı yaddaşlı random-walk üsullarının istifadəsi ilə əldə olunur. Nəticələr riyazi və məntiqi kvant dövrələri üçündür; fiziki kvant xəta dərəcələri və kvant xəta düzəltmə yükü nəzərə alınmır.

Tədqiqatın mühüm töhfəsi əvvəllər simulyasiyalarla araşdırılmış uğur davranışını sərt ehtimal və mürəkkəblik sərhədləri ilə əvəz etməsidir. Alqoritm naməlum tərtibli tsiklik qrupda \(x=g^d\) münasibətindəki qısa \(d\) qiymətini hədəfləyir. Kvant hissəsində iki Fourier nümunələmə çıxışı \(j\) və \(k\) yaradılarkən, klassik hissədə bu qiymətlər ikiölçülü qəfəs problemi üzərindən \(d\)-ni tapmaq üçün emal olunur.

Parametrlər arasında aydın xərc mübadiləsi mövcuddur. \(\Delta\) artırıldıqda kvant kompüterində qiymətləndirilməli qrup əməliyyatlarının sayı azala bilər; bunun əvəzində klassik axtarış sahəsi və post-processing xərci artır. Tədqiqatın 2048 bit təhlükəsiz-sadə FF-DH nümunəsində \(\Delta=0\) üçün verilən 672 kvant qrup əməliyyatından, \(\Delta=50\) seçimi ilə 572 qrup əməliyyatına enildiyi göstərilir. Müəllifin tətbiq sınaqları bu təxminən %15 azalmanın seçilən parametrlərdə klassik post-processing hələ də praktik saxlanılarkən əldə edilə bildiyini bildirir.

Qısa diskret loqarifm problemi nədir?

Tədqiqatda nəzərdən keçirilən qısa DLP-də tərtibi \(r\) olan tsiklik qrupun generatoru \(g\) və

\[ x=g^d \]

qiyməti verilir. Məqsəd \(d\ll r\) şərtindəki qısa diskret loqarifm \(d\)-ni hesablamaqdır. Bu tədqiqatın mühüm xüsusiyyəti qrupun tərtibi \(r\)-nin məlum olmasının zəruri olmamasıdır.

\(m\), \(d\)-nin bit uzunluğu üçün yuxarı sərhəd olmaqla

\[ d<2^m \]

qəbul edilir. Məqalə həmçinin

\[ \ell=m-\Delta \]

parametrini müəyyən edir. \(\Delta\), kvant hissəsinin xərci ilə sonradan aparılacaq klassik axtarış arasındakı mübadilədə mərkəzi rol oynayır.

Ekerå–Håstad yanaşması Shor alqoritmindən hansı baxımdan fərqlənir?

Shor-un ilkin diskret loqarifm alqoritmi məlum tərtibli tsiklik qruplarda ümumi diskret loqarifmləri nəzərdən keçirərkən, burada araşdırılan Ekerå–Håstad yanaşması naməlum qrup tərtibində qısa loqarifmləri hədəfləyir.

Tədqiqat bu xüsusiyyətin xüsusilə təhlükəsiz-sadə qruplarda qısa qüvvət istifadə edən sonlu sahə Diffie–Hellman sistemləri və RSA tam ədəd faktorizasiyası probleminin qısa DLP-yə endirilməsi baxımından kriptoanalitik əhəmiyyət daşıdığını qeyd edir.

Kvant alqoritmi hansı vəziyyəti yaradır?

Alqoritm əvvəlcə \(a\) və \(b\) qiymətləri üzərində bərabər superpozisiyalar yaradır və iş registrində

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

qiymətini hesablayır. QFT-dən əvvəlki vəziyyət mənbədə belə verilir:

\[ \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 . \]

Daha sonra ilk iki idarəetmə registrinə müvafiq olaraq \(2^{m+\ell}\) və \(2^\ell\) ölçülü kvant Fourier çevirmələri (QFT) tətbiq olunur. İdarəetmə registrləri ölçüldükdə \(j\) və \(k\) qiymətləri əldə edilir.

Məqalənin sonundakı Şəkil 1 bu dövrəni birbaşa göstərir: ilk idarəetmə registri \(g^a\)-nın yaradılmasını, ikinci idarəetmə registri \(x^{-b}\) komponentini, iş registri isə bunların qrup əməliyyatı ilə birləşdirilməsini daşıyır. Hər iki idarəetmə registrində QFT və ölçmə əməliyyatları mövcuddur.

İkinci dövrə quruluşu niyə vacibdir?

Şəkil 2 eyni riyazi əməliyyatı yenidən düzərək əvvəlcə \(j\)-nin, sonra \(j\) məlum olduqda \(k\)-nın hesablana biləcəyini göstərir. Bu yenidən düzülüş iki idarəetmə registrini eyni vaxtda saxlamaq tələbatını azaldır.

Mənbəyə görə standart quruluşda iki idarəetmə registrinin ümumi ölçüsü \(m+2\ell\) qubit olduğu halda, əməliyyatların yenidən sıralanması ilə eyni vaxtda idarəetmə sahəsi \(m+\ell\) qubitə endirilə bilir. Məqalə həmçinin yarı-klassik QFT və idarəetmə qubitinin təkrar istifadəsi ilə iki idarəetmə registrinin funksiyasının tək təkrar istifadə edilən idarəetmə qubiti ilə yerinə yetirilə bildiyini izah edir; bu optimallaşdırma əsas analizin mövzusu deyil, dövrə tətbiqinə dair qeyd kimi təqdim olunur.

Kvant hissəsində əsas xərc nədir?

Tədqiqatda kvant xərcinin dominant komponenti iki qüvvətə yüksəltmə əməliyyatı kimi götürülür. Bir icrada qiymətləndirilməli qrup əməliyyatlarının sayı

\[ m+2\ell \]

olduğuna və \(\ell=m-\Delta\) olduğuna görə:

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

Beləliklə, \(\Delta=0\) halında xərc \(3m\) qrup əməliyyatı miqyasındadır. \(\Delta\)-nın artırılması kvant əməliyyatlarının sayını azaldır; lakin sonrakı bölmələrdə göründüyü kimi klassik axtarış xərcini artırır.

\(j\) və \(k\) ölçmələri loqarifm haqqında necə məlumat daşıyır?

Tədqiqat ölçmədən alınan cüt üçün

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

və ona uyğun

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

bucağını müəyyən edir. Buradakı \(\{u\}_n\), \(u\)-nun modulo \(n\) altında mərkəzləşdirilmiş intervala endirilmiş qiymətini göstərir.

İsbatın mühüm hissələrindən biri \(j\)-nin

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

intervalındakı tam ədədlər arasından bərabər paylanma ilə seçildiyinin göstərilməsidir. Dövrə tətbiqində \(j\) əvvəlcə hesablana bilər; sonra \(k\), müəyyən \(j\) şərtində kvant ehtimal paylanmasına görə ölçülür.

\(\tau\)-good cüt nədir?

Klassik post-processing-in uğurla işləməsi üçün müəllif aşağıdakı tərifdən istifadə edir. \((j,k)\) cütü

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

şərtini ödəyirsə \(\tau\)-good adlanır. Burada

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

\(\tau\) artırıldıqda “yaxşı” sayılan ölçmə nəticələrinin bölgəsi genişlənir və buna görə uğurlu ölçmə əldə etmə ehtimalı yüksəlir; bunun əvəzində klassik qəfəs axtarışının əhatə etməli olduğu sahə də böyüyə bilər.

\(\tau\)-good cütün ehtimalı üçün hansı sərhəd sübut olunur?

Lemma 1, sabit \(j\) üçün ölçülən \(k\)-nın \(\tau\)-good cüt yaratma ehtimalını aşağıdan məhdudlaşdırır:

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

və trigamma funksiyası üçün istifadə olunan yuxarı sərhəd sayəsində

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

Bu eksperimental uğur faizi deyil. Kvant alqoritminin riyazi ehtimal paylanmasından çıxarılan analitik aşağı sərhəddir.

Qəfəs niyə klassik post-processing-in mərkəzindədir?

Tədqiqat ölçülən \(j\) üçün ikiölçülü

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

qəfəsini qurur.

\((j,k)\) cütü \(\tau\)-good olduqda məlum

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

vektoru ilə \(d\)-ni ehtiva edən naməlum

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

vektoru bir-birinə yaxın olur. Tədqiqatda bu yaxınlıq

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

kimi məhdudlaşdırılır.

Beləliklə problem, \(v\) ətrafındakı müəyyən radius daxilində \(L^\tau(j)\)-nin uyğun vektorunu tapmağa çevrilir.

\(t\)-balanced qəfəs nə deməkdir?

Qəfəsin ən qısa sıfırdan fərqli vektorunun normu \(\lambda_1\) olmaqla tədqiqat

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

şərtini ödəyən \(L^\tau(j)\) qəfəsini \(t\)-balanced adlandırır.

Lemma 2-yə görə qəfəsin \(t\)-balanced olmama ehtimalı ən çox

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

olduğuna görə, \(t\)-balanced olma ehtimalı üçün

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

şəklində aşağı sərhəd alınır; mənfi ola biləcək parametr sahələri əsas teoremdə sıfırla məhdudlaşdırılır.

Əsas uğur ehtimalı sərhədi

Theorem 1 və Theorem 2, \(\tau\)-good cüt və \(t\)-balanced qəfəs ehtimallarını birləşdirir. Beləliklə qısa loqarifmin hədəflənən klassik xərc sərhədi daxilində bərpa edilməsinə dair uğur aşağı sərhədi

\[ 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) \]

kimi verilir.

Bu formula tədqiqatın ən mühüm nəticəsidir: uğur ehtimalının artırılması ilə klassik post-processing sahəsinin böyüdülməsi arasındakı əlaqəni birbaşa riyazi ifadə edir.

Birinci klassik həll: meet-in-the-middle

İlk post-processing üsulu Shanks-in baby-step giant-step yanaşmasını iki ölçüyə genişləndirən deterministik meet-in-the-middle axtarışıdır.

Tədqiqat əvvəlcə Lagrange-reduced qəfəs bazası \((s_1,s_2)\) hesablayır. Babai-nin nearest-plane alqoritmi ilə məlum \(v\) vektoruna yaxın qəfəs nöqtəsi \(o\) tapılır. Axtarış sonra \(o\) ətrafındakı məhdud ikiölçülü sahəyə endirilir.

Theorem 1 üçün

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

təyin edilir. Müsbət tam sabit \(c\) üçün, əvvəlcədən bir neçə qrup elementi hesablanmaq şərti ilə lazım olan qrup əməliyyatlarının sayı ən çox

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

kimi yuxarıdan məhdudlaşdırılır.

Lookup cədvəlində saxlanmalı tam ədədlərin sayı isə ən çox

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

olur. \(c\)-nin artırılması yaddaş istifadəsini azaldarkən ikinci axtarış mərhələsində işi artıran zaman-yaddaş mübadiləsi yaradır.

İkinci klassik həll: random walk və Gaudry–Schost

Meet-in-the-middle yanaşmasında böyük parametrlər üçün yaddaş əsas məhdudiyyətə çevrilə bilər. Tədqiqat buna görə ikinci həll təklif edir: qəfəs axtarışını ikiölçülü qısa DLP-yə çevirmək və Gaudry–Schost alqoritmini Galbraith–Ruprai təkmilləşdirmələri ilə istifadə etmək.

Bu üsul deterministik böyük lookup cədvəli əvəzinə ehtimallı random-walk yanaşmasından istifadə edir və yaddaş ehtiyacını \(O(1)\) qrup elementi səviyyəsinə endirir.

Theorem 2 üçün

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

olmaqla idealizə edilmiş modeldə ən yaxşı, orta və ən pis hallar üçün gözlənilən qrup əməliyyatı sayı

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

ilə yuxarıdan məhdudlaşdırılır.

Buradakı nəticə gözlənilən mürəkkəblikdir və Gaudry–Schost analizinin idealizə edilmiş modelinə əsaslanır; deterministik mütləq işləmə vaxtı kimi şərh edilməməlidir.

\(\Delta\), \(\tau\) və \(t\) parametrləri nəyi dəyişir?

Uğur ehtimalı nə qədər yüksəldilə bilər?

Tədqiqatın Cədvəl 1-i \(\Delta=0\) üçün klassik iş yükü ilə sübut olunan uğur aşağı sərhədinin necə dəyişdiyini aydın göstərir:

Bu qiymətlər eksperimental müşahidə nisbətləri deyil. Theorem 1-dən əldə edilən zəmanətli riyazi aşağı və yuxarı sərhədlərin seçilmiş parametr kombinasiyalarıdır.

\(\Delta\) böyüdükdə nə baş verir?

Cədvəl 1 və Cədvəl 2 birlikdə qiymətləndirildikdə əsas meyl aydındır: eyni hədəf uğur ehtimalı saxlanılarkən \(\Delta\) böyüdükcə klassik enumeration xərci nəzərəçarpacaq dərəcədə artır.

Məsələn \(1-10^{-10}\) uğur aşağı sərhədi üçün:

Buna görə kvant xərcini azaltmaq üçün \(\Delta\)-nı davamlı artırmaq pulsuz optimallaşdırma deyil. Kvant hesablaması azalarkən klassik hesablamanın və meet-in-the-middle istifadə edilirsə yaddaş ehtiyacının sürətlə artması baş verir.

FF-DH nümunələrində kvant əməliyyat sayı necə dəyişir?

Tədqiqatın Cədvəl 3-ü təhlükəsiz-sadə FF-DH qrupları üçün Ekerå–Håstad alqoritminin kvant qrup əməliyyat sayını

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

kimi istifadə edir. 2048 bit təhlükəsiz-sadə və \(m=224\) bit qısa qüvvət nümunəsində mənbə bu qiymətləri verir:

\(\Delta=50\) nümunəsi 672-dən 572 kvant qrup əməliyyatına keçid deməkdir. Tədqiqatın öz qiymətləndirməsinə görə bu təxminən %15 kvant qrup əməliyyatı azalmasıdır. Bunun əvəzində klassik iş yuxarı sərhədi \(\log_2\) ölçüsündə 22,1-dən 33,6-ya yüksəlir.

Müəllif optimallaşdırılmış paralel tətbiqlə aparılan ilkin sınaqlarda \(\Delta=50\) və ən az %99 uğur hədəfində post-processing-in adi kompüterdə icrasının ümumiyyətlə problem yaratmadığını bildirir. Bu ifadə tətbiq təcrübəsinə əsaslanan müşahidədir; tədqiqatın riyazi teoremindən ayrıca bildirilir.

RSA baxımından tədqiqat nə deyir?

Tədqiqat RSA tam ədəd faktorizasiyası probleminin qısa DLP-yə endirilməsi vasitəsilə eyni uğur analizi çərçivəsinin RSA-ya tətbiq edilə bilməsini nəzərdən keçirir. Lakin burada əlavə şərt var: təsadüfi seçilən \(g\)-nin kifayət qədər böyük tərtibə malik olması lazımdır.

RSA üçün Cədvəl 4 bu əlavə ehtimal azalma faktorunu \(f(\Delta)\) ilə nəzərə alır. Məsələn \(\Delta=20\) üçün mənbə azalma faktorunu ən az

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

kimi istifadə edir. Eyni parametr ailəsində:

Bu cədvəl bir RSA açarının mövcud fiziki kvant kompüterində göstərilən miqdarda əməliyyatla sındırılacağını demir. Tədqiqat burada alqoritmik uğur ehtimalını və klassik enumeration xərcini təhlil edir; fiziki qubit, xəta düzəltmə, qapı xətası və ümumi real işləmə vaxtı bu hesabdan kənardadır.

Asimptotik nəticə niyə vacibdir?

Corollary 1 problem ölçüsü \(m\) sonsuzluğa gedərkən \(\Delta\), \(\tau\) və \(t\)-nin \(m\)-dən asılı seçilməsi ilə uğur ehtimalı aşağı sərhədinin 1-ə yaxınlaşa biləcəyini, eyni zamanda klassik enumeration mürəkkəbliyinin

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

daxilində saxlanıla biləcəyini göstərir.

Məsələn tədqiqat \(\Delta\) və \(t\)-ni sabit saxlayıb

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

seçməyin, uyğun super-sabit, lakin polinomla məhdud \(f(m)\) üçün bu nəticəni təmin edə biləcəyini izah edir.

Tədqiqatın dəstəklədiyi nəticələr

• Ekerå–Håstad qısa DLP alqoritminin bir icradakı uğur ehtimalı üçün simulyasiyaya əsaslanmayan sərt aşağı sərhədlər əldə edilə bilər.
• Uyğun klassik post-processing parametrləri ilə uğur ehtimalı aşağı sərhədi \(1-10^{-10}\) səviyyəsinə qədər yüksəldilə bilər.
• Meet-in-the-middle axtarışı məhdud qəfəs enumeration probleminin deterministik sürətləndirilməsini təmin edir.
• Gaudry–Schost əsaslı random-walk yanaşması eyni axtarış probleminin yaddaş tələbini \(O(1)\) qrup elementinə qədər azalda bilər.
• \(\Delta\)-nın artırılması kvantda lazım olan qrup əməliyyatlarını azaldarkən klassik post-processing xərcini artırır.
• Analiz təhlükəsiz-sadə qısa qüvvətli FF-DH ssenarilərinə birbaşa və RSA-ya qısa DLP endirilməsi vasitəsilə tətbiq olunur.
• Parametrlər problem ölçüsünə uyğun miqyaslandıqda uğur aşağı sərhədi asimptotik olaraq 1-ə yaxınlaşarkən klassik post-processing polinom zamanda saxlanıla bilər.

Tədqiqatın sübut etmədiyi nəticələr

• Tədqiqat real kvant kompüterində RSA və ya FF-DH sındırma təcrübəsi həyata keçirmir.
• Nəzəri uğur ehtimalı fiziki kvant avadanlığının xəta etməmə ehtimalı deyil.
• Analiz kvant xəta düzəltmə yükünü və ya fiziki qubit xərcini hesablamır.
• Qrup əməliyyatı sayı birbaşa saniyə, kvant qapısı və ya fiziki qubit sayı ilə eyniləşdirilə bilməz.
• Random-walk üsulunun verilən mürəkkəbliyi idealizə edilmiş modeldə gözlənilən mürəkkəblikdir.
• \(\Delta\)-nı artırmaq bütün xərci azaltmır; klassik zaman və/və ya yaddaş xərci böyüyür.
• RSA tətbiqində qısa DLP endirilməsinin əlavə tərtib şərti və ona bağlı uğur azalma faktoru nəzərdən qaçırıla bilməz.

Tədqiqatın Metodu və Tapıntıları

Tədqiqat dizaynı

Tədqiqat eksperimental kvant avadanlığı işi deyil, nəzəri kriptoqrafiya və kvant alqoritmləri sahəsində riyazi uğur ehtimalı və mürəkkəblik analizidir. Araşdırmanın əsas məqsədi əvvəlki simulyasiya əsaslı uğur qiymətləndirməsinin yerinə sübut edilmiş aşağı sərhədlər qoymaqdır.

Analiz dörd əsas mərhələdə irəliləyir:

1. Kvant alqoritminin \((j,k)\) ölçmə paylanması təhlil olunur.
2. \((j,k)\)-nın \(\tau\)-good olma ehtimalı aşağıdan məhdudlaşdırılır.
3. \(L^\tau(j)\) qəfəsinin \(t\)-balanced olma ehtimalı aşağıdan məhdudlaşdırılır.
4. Bu iki hadisə baş verdikdə \(d\)-ni bərpa edəcək klassik enumeration əməliyyatının xərci yuxarıdan məhdudlaşdırılır.

Lemma 1-in rolu

Lemma 1 müəyyən \(j\) üçün ölçülən \(k\)-nın uyğun faz bölgəsinə düşmə ehtimalını təhlil edir. İsbatda ehtimal paylanmasının müsbət və mənfi quyruqları ayrı-ayrılıqda yuxarıdan məhdudlaşdırılır. Triqonometrik sərhədlər və trigamma funksiyasından istifadə etməklə ümumi quyruq ehtimalı nəzarətdə saxlanılır.

Nəticə:

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

Lemma 2-nin rolu

İkinci ehtimal komponenti qəfəs geometriyasından gəlir. Ən qısa sıfırdan fərqli vektorun həddən artıq qısa olması enumeration sahəsinin nəzarətini çətinləşdirdiyi üçün \(t\)-balanced şərti istifadə olunur.

Qəfəsin fundamental sahəsi üçün

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

münasibətindən və \(j\)-nin bərabər paylanmasından istifadə etməklə

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

sərhədi alınır.

Meet-in-the-middle enumeration necə məhdudlaşdırılır?

Lagrange-reduced baza və Babai nearest-plane çıxışından istifadə etməklə axtarış iki indeks \(m_1\) və \(m_2\) ilə sonlu düzbucaqlı indeks sahəsinə endirilir. Tədqiqat bu sahənin ölçülərini \(B_1\) və \(B_2\) ilə məhdudlaşdırır.

Shanks yanaşmasının ikiölçülü ümumiləşdirilməsi bütün \((2B_1+1)(2B_2+1)\) namizədləri bir-bir yoxlamaq əvəzinə axtarışı iki hissəyə bölür. Birinci hissə lookup cədvəlinə yazılır, ikinci hissə isə cədvəldə uyğunluqları axtarır.

Bu quruluş namizəd sayına təxminən kvadrat kök asılılığı qazandıran meet-in-the-middle sürətləndirilməsinin əsasını təşkil edir.

Random-walk həlli hansı məhdudiyyəti aradan qaldırır?

Meet-in-the-middle üsulunda lookup cədvəli böyüdükcə yaddaş darboğaza çevrilir. Tədqiqat buna görə enumeration problemini

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

şəklində ikiölçülü qısa DLP kimi yenidən yazır.

Bu problem Gaudry–Schost alqoritmi və Galbraith–Ruprai təkmilləşdirməsi ilə həll edildikdə böyük lookup cədvəlinə ehtiyac qalmır. Beləliklə yaddaş sərfi asimptotik olaraq \(O(1)\) qrup elementinə endirilə bilir.

Cədvəl 1 və Cədvəl 2-nin əsas mesajı

Cədvəl 1 və Cədvəl 2 \(\Delta\), \(\tau\) və \(t\) dəyişdikcə uğur aşağı sərhədi ilə klassik enumeration yuxarı sərhədinin necə dəyişdiyini göstərir. Ən aydın meyl, \(\Delta\)-nın böyüdülməsi ilə eyni uğur səviyyəsinə çatmaq üçün lazım olan klassik işin sürətlə artmasıdır.

Məsələn %99 uğur aşağı sərhədində “Work” qiyməti \(\Delta=0\) üçün ən çox 8,6 olduğu halda, \(\Delta=50\) üçün 32,1; \(\Delta=100\) üçün 57,1 və \(\Delta=130\) üçün 72,1 verilir. “Work” qiymətləri birbaşa əməliyyat sayı deyil, mənbədə müəyyən edilən qrup əməliyyatı yuxarı sərhədinin \(\log_2\) göstərimidir.

Cədvəl 3-ün əsas mesajı

FF-DH cədvəli kvant və klassik xərc mübadiləsini real kriptoqrafik parametrlərlə görünən edir. Cədvəldə 2048, 3072, 4096, 6144 və 8192 bit təhlükəsiz-sadə qruplar üçün qısa qüvvət uzunluqları verilir və Ekerå–Håstad alqoritminin kvant qrup əməliyyatı sayı dəyişdirilmiş Shor yanaşması ilə nisbətləndirilir.

Məsələn 4096 bit təhlükəsiz-sadə, \(m=304\) bit qısa qüvvət nümunəsində:

• \(\Delta=0\): 912 kvant qrup əməliyyatı, üstünlük 9,0.
• \(\Delta=50\): 812 kvant qrup əməliyyatı, üstünlük 10,0.
• \(\Delta=70\): 772 kvant qrup əməliyyatı, üstünlük 10,5.

Lakin bu üstünlük artımı klassik post-processing xərcindəki artımla birlikdə qiymətləndirilməlidir.

Cədvəl 4-ün əsas mesajı

RSA cədvəli yalnız qısa DLP alqoritminin uğur sərhədini deyil, RSA endirilməsində seçilən qrup elementinin kifayət qədər böyük tərtibə malik olmama ehtimalını da nəzərə alır. Buna görə FF-DH cədvəlindən fərqli olaraq əlavə \(f(\Delta)\) azalma faktoru var.

Tədqiqat \(\Delta\) böyüdükcə bu faktorun 1-ə yaxınlaşdığını, lakin istifadə edilən analitik aşağı sərhəd üsulunun hesablama xərcinin \(\Delta\) ilə sürətlə artdığını qeyd edir. Buna görə cədvəldə daha yüksək uğur hədəfləri üçün bütün qiymətlər verilməyib.

Alqoritmlər praktikada sınaqdan keçirilibmi?

Müəllif məqalədəki Algorithm 1 və Algorithm 2 post-processing üsullarını tətbiq etdiyini və simulyasiya edilmiş kvant alqoritmi çıxışlarını emal etməklə gözlənilən şəkildə işlədiyini təsdiqlədiyini bildirir.

Bundan əlavə optimallaşdırılmış və paralelləşdirilmiş ilkin tətbiq sınaqlarının \(\Delta=50\) üçün ən az %99 uğur hədəflənərkən adi kompüterdə post-processing etməyin ümumiyyətlə problem yaratmadığını göstərdiyi qeyd olunur. Tədqiqat bu tətbiqin optimallaşdırılması və daha çox paralelləşdirilməsi üzərində işlərin davam etdiyini də açıq bildirir.

Şəkil 1 və Şəkil 2-nin elmi mesajı

Şəkil 1 \(m+\ell\) qubitlik birinci və \(\ell\) qubitlik ikinci idarəetmə registrini, \(g^a\) və \(x^{-b}\) idarə olunan qrup əməliyyatlarını, QFT bloklarını və \(j,k\) ölçmələrini eyni dövrədə göstərir.

Şəkil 2 riyazi olaraq ekvivalent dövrəni vaxtlama baxımından yenidən düzür. Birinci idarəetmə registrinin QFT və ölçməsi \(g^a\) əməliyyatından dərhal sonraya keçirilir, ikinci idarəetmə registri isə daha sonra hazırlanır. Beləliklə \(j\)-nin əvvəl hesablanması və \(k\)-nın \(j\)-yə bağlı olaraq sonra əldə edilməsi Lemma 1-in ehtimal analizində istifadə olunan quruluşla vizual olaraq uyğunlaşır.

Tədqiqatın əsas kəmiyyət nəticələri

Tədqiqatın əsas güclü tərəfləri

• Əvvəllər simulyasiya ilə qiymətləndirilən single-run uğur davranışını analitik aşağı sərhədlərlə dəstəkləməsi.
• Kvant xərci ilə klassik post-processing xərcini eyni parametr ailəsi daxilində birlikdə qiymətləndirməsi.
• Uğur ehtimalına əlavə olaraq klassik enumeration mürəkkəbliyini də açıq yuxarı sərhədlə verməsi.
• Zaman-yaddaş mübadiləli deterministik və aşağı yaddaşlı ehtimallı olmaqla iki ayrı post-processing yanaşması təqdim etməsi.
• FF-DH və RSA endirilməsi üçün ayrı parametr cədvəlləri təqdim etməsi.
• Post-processing alqoritmlərinin simulyasiya edilmiş kvant çıxışları üzərində tətbiqlə yoxlanmış olması.

Tədqiqatın əsas məhdudiyyətləri

• Əsas riyazi analiz kvant kompüterinin alqoritmi riyazi tərifinə uyğun və hesablama xətası olmadan icra etdiyini fərz edir.
• Kvant xəta düzəltməsinin fiziki və hesablama yükü analizə daxil edilməyib.
• Analiz məntiqi kvant dövrələri və məntiqi xərclərlə məhduddur.
• Qısa DLP analizi \(r\geq2^{m+\ell}+(2^\ell-1)d\) şəklində qısalıq şərtindən istifadə edir; RSA halında bu şərt əlavə ehtimal faktoru tələb edir.
• Gaudry–Schost üsulu üçün verilən iş miqdarı idealizə edilmiş modeldə gözlənilən qiymətdir.
• Böyük \(\Delta\) qiymətlərində meet-in-the-middle post-processing-in yaddaş ehtiyacı praktik tətbiqi məhdudlaşdıra bilər.
• Optimallaşdırılmış paralel post-processing tətbiqinə dair nəticələr ilkin xarakterlidir və müəllif əlavə optimallaşdırma işlərinin davam etdiyini bildirir.

Mənbə və Metod Qeydi

Tam orijinal iş adı: On the success probability of the quantum algorithm for the short DLP

Müəllif: Martin Ekerå.

Müəllif sayı: Bir.

Birgə birinci müəllif/birgə töhfə: Tətbiq edilmir; iş tək müəlliflidir.

Məsul müəllif: Mənbədə ayrıca “corresponding author” etiketi istifadə edilməyib. Martin Ekerå üçün əlaqə e-poçtu verilib.

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

Jurnal: IACR Communications in Cryptology.

Cild / nömrə: 3 / 1.

ISSN: 3006-5496.

Səhifə uzunluğu: 32 səhifə.

DOI: 10.62056/an2isgsfg

Rəsmi nəşr bağlantısı: https://doi.org/10.62056/an2isgsfg

Nəşriyyat / nəşr qurumu: International Association for Cryptologic Research (IACR).

Mənbə növü: Rəyçilərdən keçmiş tədqiqat məqaləsi.

Rəyçilik vəziyyəti: Rəyçilərdən keçmiş jurnalda dərc olunmuş işdir. IACR Communications in Cryptology tam peer-reviewed jurnaldır və jurnalın rəsmi siyasəti double-blind peer review tətbiq edildiyini bildirir.

Göndərilmə tarixi: 2 fevral 2026.

Qəbul tarixi: 23 aprel 2026.

Nəşr tarixi: 4 may 2026.

Preprint əlaqəsi: İşin əvvəlki versiyaları arXiv:2309.01754 altında dərc olunub. arXiv qeydi yekun jurnal nəşrinə və DOI 10.62056/an2isgsfg-yə keçid verir. Bu Verianla məqaləsindəki elmi izah istifadəçinin yüklədiyi nəşr olunmuş 32 səhifəlik versiyaya əsaslanır.

Lisenziya: Creative Commons Attribution 4.0 (CC BY 4.0). Müəllif hüquqları müəllif(lər)də qalır.

Maliyyələşmə və dəstək: Tədqiqatda maliyyələşmə və dəstəyin Swedish NCSA tərəfindən təmin edildiyi; Swedish NCSA-nın Swedish Armed Forces tərkibində olduğu bildirilir. Hesablamalar həmçinin Swedish Research Council grant agreement no. 2022-06725 ilə qismən maliyyələşdirilən National Academic Infrastructure for Supercomputing in Sweden (NAISS) çərçivəsində KTH PDC resursları ilə aparılıb.

Təşəkkür: Müəllif Johan Håstad-a şərh və tövsiyələri üçün, Joel Gärtner-ə isə ilkin preprint versiyasındakı Lemma 3 probleminə diqqət çəkdiyi üçün təşəkkür edir.

Məlumat və proqram təminatı qeydi: Tədqiqat eksperimental məlumat dəstinə əsaslanmır. Müəllif post-processing alqoritmlərini tətbiq etdiyini və simulyasiya edilmiş kvant alqoritmi çıxışları ilə doğruladığını bildirir. Məqalədə əlçatan, lakin optimallaşdırılmamış Algorithm 1 tətbiqi və simulyator üçün Quaspy proqram deposuna istinad edilir.

Maraqlar toqquşması: Yüklənmiş tədqiqatda ayrıca maraqlar toqquşması bölməsi aşkar edilməyib.

Müəllif töhfələri: İş tək müəlliflidir və ayrıca CRediT töhfə bəyanı verilməyib.

Əsas metod: Ekerå–Håstad qısa DLP kvant alqoritminin ölçmə paylanmasının analitik sərhədlənməsi; ikiölçülü qəfəs analizi; Lagrange reduction və Babai nearest-plane üsulu; meet-in-the-middle enumeration; ikiölçülü qısa DLP-yə endirmə və Gaudry–Schost/Galbraith–Ruprai random-walk analizi.

Elmi məzmun sərhədi: Bu Verianla məqaləsindəki alqoritmik mexanizmlər, formulalar, ədədi cədvəllər, FF-DH və RSA nəticələri, tətbiq müşahidələri və məhdudiyyətlər yüklənmiş mənbə işinə əsaslanır. Xarici mənbələr yalnız iş kimliyi, nəşr tarixi, jurnal statusu, DOI, lisenziya və preprint-nəşr əlaqəsini biblioqrafik olaraq yoxlamaq məqsədi ilə istifadə edilib; PDF xaricindən yeni elmi tapıntı əlavə edilməyib.

Ən mühüm şərh sərhədi: Tədqiqatın uğur ehtimalı və xərc sərhədləri məntiqi kvant alqoritminə aiddir. Fiziki avadanlıq xətaları, kvant xəta düzəltməsi və bunların gətirəcəyi əlavə fiziki resurs xərcləri bu analizdə yer almır.