Bu çalışma, Ekerå–Håstad kuantum algoritmasının kısa ayrık logaritma problemini (short discrete logarithm problem, short DLP) tek bir kuantum çalıştırmasında çözme olasılığı için simülasyona dayanmayan matematiksel bir alt sınır türetiyor ve bu çıktının klasik olarak işlenmesi için gereken hesaplama maliyetini üstten sınırlıyor. Temel sonuç, uygun parametre ve klasik post-processing seçimiyle kısa logaritma \(d\)'nin tek çalıştırmada geri kazanılmasına ilişkin teorik başarı alt sınırının \(1-10^{-10}\) düzeyine kadar yükseltilebilmesi. Bu yüksek başarı olasılığı, kuantum bölümünü büyütmekten çok, kuantum ölçümünden çıkan \((j,k)\) çiftinin kafes tabanlı klasik işleminde meet-in-the-middle veya düşük bellekli random-walk teknikleri kullanılmasıyla elde ediliyor. Sonuçlar matematiksel ve mantıksal kuantum devreleri içindir; fiziksel kuantum hata oranları ve kuantum hata düzeltme yükü hesaba katılmamaktadır.

Çalışmanın önemli katkısı, daha önce simülasyonlarla incelenmiş başarı davranışını katı olasılık ve karmaşıklık sınırlarıyla değiştirmesidir. Algoritma bilinmeyen mertebeli bir döngüsel grupta \(x=g^d\) bağıntısındaki kısa \(d\) değerini hedefliyor. Kuantum bölümünde iki Fourier örnekleme çıktısı \(j\) ve \(k\) oluşturulurken, klasik bölümde bu değerler iki boyutlu bir kafes problemi üzerinden \(d\)'yi bulmak için işleniyor.

Parametreler arasında belirgin bir maliyet değiş-tokuşu bulunuyor. \(\Delta\) büyütüldüğünde kuantum bilgisayarında değerlendirilmesi gereken grup işlemlerinin sayısı azalabiliyor; bunun karşılığında klasik arama alanı ve post-processing maliyeti büyüyor. Çalışmanın 2048 bit güvenli-asal FF-DH örneğinde \(\Delta=0\) için 672 kuantum grup işlemi verilen başlangıç noktasından, \(\Delta=50\) seçimiyle 572 grup işlemine inilmesi gösteriliyor. Yazarın uygulama denemeleri bu yaklaşık %15'lik azalmanın, seçilen parametrelerde klasik post-processing hâlâ uygulanabilir tutulurken gerçekleştirilebildiğini belirtiyor.

Kısa ayrık logaritma problemi nedir?

Çalışmada ele alınan kısa DLP'de, mertebesi \(r\) olan bir döngüsel grubun üreteci \(g\) ve

\[ x=g^d \]

değeri veriliyor. Amaç, \(d\ll r\) koşulundaki kısa ayrık logaritma \(d\)'yi hesaplamak. Bu çalışmadaki önemli özellik, grubun mertebesi \(r\)'nin bilinmek zorunda olmamasıdır.

\(m\), \(d\)'nin bit uzunluğu için bir üst sınır olacak şekilde

\[ d<2^m \]

alınıyor. Makale ayrıca

\[ \ell=m-\Delta \]

parametresini tanımlıyor. \(\Delta\), kuantum bölümünün maliyeti ile daha sonra yapılacak klasik arama arasındaki değiş-tokuşta merkezi rol oynuyor.

Ekerå–Håstad yaklaşımı Shor algoritmasından hangi açıdan ayrılıyor?

Shor'un özgün ayrık logaritma algoritması genel ayrık logaritmaları bilinen mertebeli döngüsel gruplarda ele alırken, burada incelenen Ekerå–Håstad yaklaşımı bilinmeyen grup mertebesinde kısa logaritmaları hedefliyor.

Çalışma bu özelliğin özellikle güvenli-asal gruplarda kısa üs kullanan sonlu alan Diffie–Hellman sistemleri ve RSA tam sayı çarpanlara ayırma probleminin kısa DLP'ye indirgenmesi açısından kriptanalitik önem taşıdığını belirtiyor.

Kuantum algoritması hangi durumu oluşturuyor?

Algoritma önce \(a\) ve \(b\) değerleri üzerinde düzgün süperpozisyonlar oluşturuyor ve çalışma kaydında

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

değerini hesaplıyor. QFT öncesindeki durum kaynakta şu yapıyla veriliyor:

\[ \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 kontrol kaydına sırasıyla \(2^{m+\ell}\) ve \(2^\ell\) boyutlarında kuantum Fourier dönüşümleri (QFT) uygulanıyor. Kontrol kayıtları ölçüldüğünde \(j\) ve \(k\) değerleri elde ediliyor.

Makalenin sonundaki Şekil 1 bu devreyi doğrudan gösteriyor: ilk kontrol kaydı \(g^a\) üretilmesini, ikinci kontrol kaydı \(x^{-b}\) bileşenini ve çalışma kaydı bunların grup işlemiyle birleştirilmesini taşıyor. Her iki kontrol kaydında QFT ve ölçüm işlemleri bulunuyor.

İkinci devre düzeni neden önemli?

Şekil 2, aynı matematiksel işlemi yeniden düzenleyerek önce \(j\)'nin, ardından \(j\) bilinirken \(k\)'nın hesaplanabileceğini gösteriyor. Bu yeniden düzenleme, iki kontrol kaydını eşzamanlı tutma gereksinimini azaltıyor.

Kaynağa göre standart düzenlemede iki kontrol kaydının toplam büyüklüğü \(m+2\ell\) qubit iken, işlemlerin yeniden sıralanmasıyla eşzamanlı kontrol alanı \(m+\ell\) qubit'e indirilebiliyor. Makale ayrıca yarı-klasik QFT ve kontrol qubit'i geri dönüşümüyle iki kontrol kaydının işlevinin tek bir tekrar kullanılan kontrol qubit'iyle gerçekleştirilebildiğini açıklıyor; bu optimizasyon ana analizin konusu değil, devre uygulamasına ilişkin bir not olarak sunuluyor.

Kuantum bölümündeki temel maliyet nedir?

Çalışmada kuantum maliyetin baskın bileşeni iki üs alma işlemi olarak ele alınıyor. Tek çalıştırmada değerlendirilmesi gereken grup işlemlerinin sayısı

\[ m+2\ell \]

olduğundan ve \(\ell=m-\Delta\) olduğundan:

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

Dolayısıyla \(\Delta=0\) durumunda maliyet \(3m\) grup işlemi ölçeğindedir. \(\Delta\)'nın artırılması kuantum işlemlerinin sayısını azaltır; ancak ilerleyen bölümlerde görüldüğü üzere klasik arama maliyetini artırır.

\(j\) ve \(k\) ölçümleri logaritma hakkında nasıl bilgi taşıyor?

Çalışma ölçümden elde edilen çift için

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

ve buna karşılık gelen

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

açısını tanımlıyor. Buradaki \(\{u\}_n\), \(u\)'nun modulo \(n\) altında merkezlenmiş aralıkta indirgenmiş değerini gösteriyor.

İspatın önemli parçalarından biri \(j\)'nin

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

aralığındaki tam sayılar arasından düzgün dağılımla seçildiğinin gösterilmesidir. Devre uygulamasında \(j\) önce hesaplanabiliyor; ardından \(k\), belirli \(j\) koşulunda kuantum olasılık dağılımına göre ölçülüyor.

\(\tau\)-good çift nedir?

Klasik post-processing'in başarıyla çalışması için yazar şu tanımı kullanıyor. \((j,k)\) çifti,

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

koşulunu sağlıyorsa \(\tau\)-good olarak adlandırılıyor. Burada

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

\(\tau\) büyütüldüğünde “iyi” kabul edilen ölçüm sonuçlarının bölgesi genişliyor ve bu nedenle başarılı bir ölçüm elde etme olasılığı yükseliyor; buna karşılık klasik kafes aramasının kapsaması gereken bölge de büyüyebiliyor.

\(\tau\)-good bir çiftin olasılığı için hangi sınır kanıtlanıyor?

Lemma 1, sabit bir \(j\) için ölçülen \(k\)'nın \(\tau\)-good bir çift oluşturma olasılığını aşağıdan sınırlar:

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

ve trigamma fonksiyonu için kullanılan üst sınır sayesinde

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

Bu bir deneysel başarı yüzdesi değildir. Kuantum algoritmasının matematiksel olasılık dağılımından türetilen analitik bir alt sınırdır.

Kafes neden klasik post-processing'in merkezinde?

Çalışma, ölçülen \(j\) için iki boyutlu

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

kafesini kuruyor.

\((j,k)\) çifti \(\tau\)-good olduğunda bilinen

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

vektörü ile \(d\)'yi içeren bilinmeyen

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

vektörü birbirine yakın oluyor. Çalışmada bu yakınlık

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

olarak sınırlandırılıyor.

Dolayısıyla problem, \(v\) çevresindeki belirli yarıçap içinde \(L^\tau(j)\)'nin uygun vektörünü bulmaya dönüşüyor.

\(t\)-balanced kafes ne anlama geliyor?

Kafesin en kısa sıfır olmayan vektörünün normu \(\lambda_1\) olmak üzere çalışma

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

koşulunu sağlayan \(L^\tau(j)\) kafesini \(t\)-balanced olarak tanımlıyor.

Lemma 2'ye göre kafesin \(t\)-balanced olmama olasılığı en fazla

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

olduğundan, \(t\)-balanced olma olasılığı için

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

şeklinde bir alt sınır elde ediliyor; negatif olabilecek parametre bölgeleri ana teoremde sıfırla sınırlandırılıyor.

Ana başarı olasılığı sınırı

Theorem 1 ve Theorem 2, \(\tau\)-good çift ve \(t\)-balanced kafes olasılıklarını birleştiriyor. Böylece kısa logaritmanın hedeflenen klasik maliyet sınırı içinde geri kazanılmasına ilişkin başarı alt sınırı

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

olarak veriliyor.

Bu formül çalışmanın en önemli sonucudur: başarı olasılığının artırılması ile klasik post-processing alanının büyütülmesi arasındaki ilişkiyi doğrudan matematiksel olarak ifade eder.

Birinci klasik çözüm: meet-in-the-middle

İlk post-processing yöntemi, Shanks'in baby-step giant-step yaklaşımını iki boyuta genişleten deterministik bir meet-in-the-middle aramasıdır.

Çalışma önce Lagrange-indirgenmiş bir kafes bazı \((s_1,s_2)\) hesaplıyor. Babai'nin nearest-plane algoritmasıyla bilinen \(v\) vektörüne yakın bir kafes noktası \(o\) bulunuyor. Arama daha sonra \(o\) çevresindeki sınırlı iki boyutlu bölgeye indirgeniyor.

Theorem 1 için

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

tanımlanıyor. Pozitif tam sayı sabit \(c\) için, önceden birkaç grup elemanı hesaplanmış olmak şartıyla gerekli grup işlemi sayısı en fazla

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

olarak üstten sınırlandırılıyor.

Lookup tablosunda tutulması gereken tam sayı sayısı ise en fazla

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

oluyor. \(c\)'nin artırılması bellek kullanımını azaltırken ikinci arama aşamasındaki işi artıran bir zaman-bellek değiş-tokuşu sağlıyor.

İkinci klasik çözüm: random walk ve Gaudry–Schost

Meet-in-the-middle yaklaşımında büyük parametreler için bellek temel sınırlayıcı hâle gelebiliyor. Çalışma bu nedenle ikinci bir çözüm sunuyor: kafes aramasını iki boyutlu kısa DLP'ye dönüştürmek ve Gaudry–Schost algoritmasını Galbraith–Ruprai iyileştirmeleriyle kullanmak.

Bu yöntem deterministik büyük lookup tablosu yerine olasılıksal random-walk yaklaşımı kullanıyor ve bellek ihtiyacını \(O(1)\) grup elemanı düzeyine indiriyor.

Theorem 2 için

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

olmak üzere idealize modelde en iyi, ortalama ve en kötü durum için beklenen grup işlemi sayısı

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

ile üstten sınırlandırılıyor.

Buradaki sonuç beklenen karmaşıklıktır ve Gaudry–Schost analizinin idealize modeline dayanır; deterministik mutlak çalışma süresi olarak yorumlanmamalıdır.

\(\Delta\), \(\tau\) ve \(t\) parametreleri neyi değiştiriyor?

Başarı olasılığı ne kadar yükseltilebiliyor?

Çalışmanın Tablo 1'i, \(\Delta=0\) için klasik iş yükü ile kanıtlanan başarı alt sınırının nasıl değiştiğini açık biçimde gösteriyor:

Bu değerler deneysel gözlem oranları değildir. Teorem 1'den elde edilen garantili matematiksel alt ve üst sınırların seçilmiş parametre kombinasyonlarıdır.

\(\Delta\) büyüdüğünde ne oluyor?

Tablo 1 ve Tablo 2 birlikte değerlendirildiğinde temel eğilim açıktır: aynı hedef başarı olasılığı korunurken \(\Delta\) büyütüldikçe klasik enumeration maliyeti belirgin biçimde yükseliyor.

Örneğin \(1-10^{-10}\) başarı alt sınırı için:

Bu nedenle kuantum maliyetini azaltmak amacıyla \(\Delta\)'yı sürekli artırmak ücretsiz bir optimizasyon değildir. Kuantum hesaplama azalırken klasik hesaplama ve meet-in-the-middle kullanılıyorsa bellek ihtiyacı hızla büyür.

FF-DH örneklerinde kuantum işlem sayısı nasıl değişiyor?

Çalışmanın Tablo 3'ü, güvenli-asal FF-DH grupları için Ekerå–Håstad algoritmasının kuantum grup işlem sayısını

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

olarak kullanıyor. 2048 bit güvenli-asal ve \(m=224\) bit kısa üs örneğinde kaynak şu değerleri veriyor:

\(\Delta=50\) örneği, 672'den 572 kuantum grup işlemine geçiş anlamına gelir. Çalışmanın kendi değerlendirmesine göre bu yaklaşık %15 kuantum grup işlemi azalmasıdır. Bunun karşılığında klasik iş üst sınırı \(\log_2\) ölçekte 22,1'den 33,6'ya yükselmektedir.

Yazar, optimize edilmiş paralel uygulamayla yapılan ilk deneylerde \(\Delta=50\) ve en az %99 başarı hedefinde post-processing'in sıradan bir bilgisayarda çalıştırılmasının genellikle sorun oluşturmadığını bildiriyor. Bu ifade uygulama deneyimine dayalı bir gözlemdir; çalışmanın matematiksel teoreminden bağımsız olarak ayrıca raporlanmıştır.

RSA açısından çalışma ne söylüyor?

Çalışma, RSA tam sayı çarpanlara ayırma probleminin kısa DLP'ye indirgenmesi üzerinden aynı başarı analizi çerçevesinin RSA'ya uygulanabileceğini ele alıyor. Ancak burada ek bir koşul vardır: rastgele seçilen \(g\)'nin yeterince büyük mertebeye sahip olması gerekir.

RSA için Tablo 4 bu ek olasılık azaltma faktörünü \(f(\Delta)\) ile hesaba katıyor. Örneğin \(\Delta=20\) için kaynak, azaltma faktörünü en az

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

olarak kullanıyor. Aynı parametre ailesinde:

Bu tablo bir RSA anahtarının mevcut bir fiziksel kuantum bilgisayarda belirtilen miktarda işlemle kırılacağını söylemez. Çalışma burada algoritmik başarı olasılığı ve klasik enumeration maliyetini analiz eder; fiziksel qubit, hata düzeltme, kapı hatası ve toplam gerçek çalışma süresi bu hesabın dışında tutulmuştur.

Asimptotik sonuç neden önemli?

Corollary 1, problem büyüklüğü \(m\) sonsuza giderken \(\Delta\), \(\tau\) ve \(t\)'nin \(m\)'ye bağlı seçilmesiyle başarı olasılığı alt sınırının bire yaklaşabileceğini, aynı anda klasik enumeration karmaşıklığının

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

içinde tutulabileceğini gösteriyor.

Örneğin çalışma, \(\Delta\) ve \(t\)'yi sabit tutup

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

seçmenin, uygun süper-sabit ancak polinomla sınırlı \(f(m)\) için bu sonucu sağlayabileceğini açıklıyor.

Çalışmanın desteklediği sonuçlar

• Ekerå–Håstad kısa DLP algoritmasının tek çalıştırmadaki başarı olasılığı için simülasyona dayanmayan katı alt sınırlar elde edilebilir.
• Uygun klasik post-processing parametreleriyle başarı olasılığı alt sınırı \(1-10^{-10}\) düzeyine kadar yükseltilebilir.
• Meet-in-the-middle araması, sınırlı kafes enumeration probleminin deterministik olarak hızlandırılmasını sağlar.
• Gaudry–Schost tabanlı random-walk yaklaşımı aynı arama probleminin bellek ihtiyacını \(O(1)\) grup elemanına kadar indirebilir.
• \(\Delta\)'nın artırılması kuantumda gereken grup işlemlerini azaltırken klasik post-processing maliyetini artırır.
• Analiz güvenli-asal kısa üs FF-DH senaryolarına doğrudan ve RSA'ya kısa DLP indirgemesi üzerinden uygulanmaktadır.
• Parametreler problem büyüklüğüne uygun ölçeklendiğinde başarı alt sınırı asimptotik olarak bire yaklaşabilirken klasik post-processing polinom zamanda tutulabilir.

Çalışmanın kanıtlamadığı sonuçlar

• Çalışma gerçek bir kuantum bilgisayar üzerinde RSA veya FF-DH kırma deneyi gerçekleştirmemektedir.
• Teorik başarı olasılığı, fiziksel kuantum donanımının hata yapmama olasılığı değildir.
• Analiz kuantum hata düzeltme yükünü veya fiziksel qubit maliyetini hesaplamamaktadır.
• Grup işlemi sayısı doğrudan saniye, kuantum kapısı veya fiziksel qubit sayısıyla özdeş değildir.
• Random-walk yönteminin verilen karmaşıklığı idealize modelde beklenen karmaşıklıktır.
• \(\Delta\)'yı artırmak bütün maliyeti azaltmaz; klasik zaman ve/veya bellek maliyeti büyür.
• RSA uygulamasında kısa DLP indirgemesinin ek mertebe koşulu ve buna bağlı başarı azaltma faktörü göz ardı edilemez.

Çalışmanın Yöntemi ve Bulguları

Araştırma tasarımı

Çalışma deneysel kuantum donanım araştırması değil, teorik kriptografi ve kuantum algoritmaları alanında matematiksel bir başarı olasılığı ve karmaşıklık analizidir. Araştırmanın temel amacı önceki simülasyon temelli başarı tahmininin yerine ispatlanmış alt sınırlar koymaktır.

Analiz dört ana aşamada ilerliyor:

1. Kuantum algoritmasının \((j,k)\) ölçüm dağılımı analiz ediliyor.
2. \((j,k)\)'nın \(\tau\)-good olma olasılığı aşağıdan sınırlandırılıyor.
3. \(L^\tau(j)\) kafesinin \(t\)-balanced olma olasılığı aşağıdan sınırlandırılıyor.
4. Bu iki olay gerçekleştiğinde \(d\)'yi geri kazanacak klasik enumeration işleminin maliyeti üstten sınırlandırılıyor.

Lemma 1'in rolü

Lemma 1, belirli \(j\) için ölçülen \(k\)'nın uygun faz bölgesine düşme olasılığını analiz ediyor. İspatta olasılık dağılımının pozitif ve negatif kuyrukları ayrı ayrı üstten sınırlandırılıyor. Trigonometrik sınırlar ve trigamma fonksiyonu kullanılarak toplam kuyruk olasılığı kontrol ediliyor.

Sonuç:

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

Lemma 2'nin rolü

İkinci olasılık bileşeni kafes geometrisinden geliyor. En kısa sıfır olmayan vektörün çok kısa olması enumeration alanının kontrolünü zorlaştıracağından \(t\)-balanced koşulu kullanılıyor.

Kafesin temel bölge alanı için

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

bağıntısından ve \(j\)'nin düzgün dağılımından yararlanılarak

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

sınırı elde ediliyor.

Meet-in-the-middle enumeration nasıl sınırlandırılıyor?

Lagrange-indirgenmiş baz ve Babai nearest-plane çıktısı kullanılarak arama iki indeks \(m_1\) ve \(m_2\) ile sonlu bir dikdörtgensel indeks alanına indirgeniyor. Çalışma bu alanın boyutlarını \(B_1\) ve \(B_2\) ile sınırlandırıyor.

Shanks yaklaşımının iki boyutlu genellemesi, doğrudan bütün \((2B_1+1)(2B_2+1)\) adayları tek tek kontrol etmek yerine aramayı iki parçaya bölüyor. İlk kısım lookup tablosuna yazılırken ikinci kısım tablodaki eşleşmeleri arıyor.

Bu yapı, aday sayısına yaklaşık karekök bağımlılığı kazandıran meet-in-the-middle hızlanmasının temelidir.

Random-walk çözümü hangi sınırlamayı gideriyor?

Meet-in-the-middle yönteminde lookup tablosu büyüdükçe bellek darboğaz hâline gelir. Çalışma bu nedenle enumeration problemini

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

biçiminde iki boyutlu kısa DLP olarak yeniden yazıyor.

Bu problem Gaudry–Schost algoritması ve Galbraith–Ruprai iyileştirmesiyle çözüldüğünde büyük lookup tablosuna ihtiyaç kalmıyor. Böylece bellek tüketimi asimptotik olarak \(O(1)\) grup elemanına indirilebiliyor.

Tablo 1 ve Tablo 2'nin ana mesajı

Tablo 1 ve Tablo 2, \(\Delta\), \(\tau\) ve \(t\) değiştikçe başarı alt sınırı ile klasik enumeration üst sınırının nasıl hareket ettiğini gösteriyor. Görsel olarak en belirgin eğilim, \(\Delta\)'nın büyütülmesiyle aynı başarı düzeyine ulaşmak için gereken klasik işin hızla artmasıdır.

Örneğin %99 başarı alt sınırında “Work” değeri \(\Delta=0\) için en fazla 8,6 iken, \(\Delta=50\) için 32,1; \(\Delta=100\) için 57,1 ve \(\Delta=130\) için 72,1 olarak verilmektedir. “Work” değerleri doğrudan işlem sayısı değil, kaynakta tanımlanan grup işlemi üst sınırının \(\log_2\) gösterimidir.

Tablo 3'ün ana mesajı

FF-DH tablosu, kuantum ve klasik maliyet değiş-tokuşunu gerçek kriptografik parametreler üzerinden görünür hâle getiriyor. Tabloda 2048, 3072, 4096, 6144 ve 8192 bit güvenli-asal gruplar için kısa üs uzunlukları verilmiş ve Ekerå–Håstad algoritmasının kuantum grup işlemi sayısı değiştirilmiş Shor yaklaşımıyla oranlanmıştır.

Örneğin 4096 bit güvenli-asal, \(m=304\) bit kısa üs örneğinde:

• \(\Delta=0\): 912 kuantum grup işlemi, avantaj 9,0.
• \(\Delta=50\): 812 kuantum grup işlemi, avantaj 10,0.
• \(\Delta=70\): 772 kuantum grup işlemi, avantaj 10,5.

Ancak bu avantaj artışı klasik post-processing maliyetindeki artışla birlikte değerlendirilmelidir.

Tablo 4'ün ana mesajı

RSA tablosu yalnız kısa DLP algoritmasının başarı sınırını değil, RSA indirgemesinde seçilen grup elemanının yeterli mertebeye sahip olmama olasılığını da hesaba katıyor. Bu nedenle FF-DH tablosundan farklı olarak ek \(f(\Delta)\) azaltma faktörü bulunuyor.

Çalışma \(\Delta\) büyüdükçe bu faktörün bire yaklaştığını, fakat kullanılan analitik alt sınır yönteminin hesaplama maliyetinin \(\Delta\) ile hızla büyüdüğünü belirtiyor. Bu nedenle tabloda çok daha yüksek başarı hedefleri için bütün değerler verilmemiştir.

Algoritmalar uygulamada test edilmiş mi?

Yazar, makaledeki Algorithm 1 ve Algorithm 2 post-processing yöntemlerini uyguladığını ve simüle edilmiş kuantum algoritması çıktılarının işlenmesiyle beklenen biçimde çalıştıklarını doğruladığını bildiriyor.

Ayrıca optimize edilmiş ve paralelleştirilmiş ilk uygulama deneylerinin \(\Delta=50\) için, en az %99 başarı hedeflenirken sıradan bir bilgisayarda post-processing yapmanın genellikle sorun olmadığını gösterdiği belirtiliyor. Çalışma bu uygulamanın optimizasyonu ve daha fazla paralelleştirilmesi üzerinde çalışmaların devam ettiğini de açıkça ifade ediyor.

Şekil 1 ve Şekil 2'nin bilimsel mesajı

Şekil 1, \(m+\ell\) qubit'lik ilk ve \(\ell\) qubit'lik ikinci kontrol kaydını, \(g^a\) ve \(x^{-b}\) kontrollü grup işlemlerini, QFT bloklarını ve \(j,k\) ölçümlerini aynı devrede gösterir.

Şekil 2 matematiksel olarak eşdeğer devreyi zamanlama açısından yeniden düzenler. İlk kontrol kaydının QFT ve ölçümü \(g^a\) işleminin hemen sonrasına alınırken ikinci kontrol kaydı daha sonra hazırlanır. Böylece \(j\)'nin önce hesaplanıp \(k\)'nın \(j\)'ye bağlı olarak daha sonra elde edilebilmesi, Lemma 1'in olasılık analizinde kullanılan yapıyla görsel olarak uyumludur.

Çalışmanın temel nicel bulguları

Çalışmanın başlıca güçlü yönleri

• Daha önce simülasyonla değerlendirilen tek-run başarı davranışını analitik alt sınırlarla desteklemesi.
• Kuantum maliyet ile klasik post-processing maliyetini aynı parametre ailesi içinde birlikte değerlendirmesi.
• Başarı olasılığına ek olarak klasik enumeration karmaşıklığını da açık biçimde üstten sınırlaması.
• Zaman-bellek değiş-tokuşlu deterministik ve düşük bellekli olasılıksal olmak üzere iki ayrı post-processing yaklaşımı sağlaması.
• FF-DH ve RSA indirgemesi için ayrı parametre tabloları sunması.
• Post-processing algoritmalarının simüle kuantum çıktıları üzerinde uygulanarak kontrol edilmiş olması.

Çalışmanın başlıca sınırlılıkları

• Ana matematiksel analiz, kuantum bilgisayarın algoritmayı matematiksel tanımına uygun ve hesaplama hatası olmadan yürüttüğünü varsayar.
• Kuantum hata düzeltmenin fiziksel ve hesaplama yükü analize dahil edilmemiştir.
• Analiz mantıksal kuantum devreleri ve mantıksal maliyetlerle sınırlıdır.
• Kısa DLP analizi \(r\geq2^{m+\ell}+(2^\ell-1)d\) biçimindeki kısa olma koşulunu kullanır; RSA durumunda bu koşul ek olasılık faktörü gerektirir.
• Gaudry–Schost yöntemi için verilen çalışma miktarı idealize modelde beklenen değerdir.
• Büyük \(\Delta\) değerlerinde meet-in-the-middle post-processing'in bellek ihtiyacı pratik uygulanabilirliği sınırlayabilir.
• Optimize paralel post-processing uygulamasına ilişkin sonuçlar başlangıç niteliğindedir ve yazar daha fazla optimizasyon çalışmasının sürdüğünü belirtmektedir.

Kaynak ve Yöntem Notu

Tam özgün çalışma adı: On the success probability of the quantum algorithm for the short DLP

Yazar: Martin Ekerå.

Yazar sayısı: Bir.

Eş birinci yazar/eş katkı: Uygulanabilir değil; çalışma tek yazarlıdır.

Sorumlu yazar: Kaynakta ayrı bir “corresponding author” etiketi kullanılmamıştır. Martin Ekerå için iletişim e-postası verilmiştir.

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

Dergi: IACR Communications in Cryptology.

Cilt / sayı: 3 / 1.

ISSN: 3006-5496.

Sayfa uzunluğu: 32 sayfa.

DOI: 10.62056/an2isgsfg

Resmî yayın bağlantısı: https://doi.org/10.62056/an2isgsfg

Yayınevi / yayın kuruluşu: International Association for Cryptologic Research (IACR).

Kaynak türü: Hakemli araştırma makalesi.

Hakemlik durumu: Hakemli dergide yayımlanmış çalışma. IACR Communications in Cryptology tam hakemli bir dergidir ve derginin resmî politikası çift-kör hakem değerlendirmesi uygulandığını belirtmektedir.

Gönderim tarihi: 2 Şubat 2026.

Kabul tarihi: 23 Nisan 2026.

Yayın tarihi: 4 Mayıs 2026.

Preprint ilişkisi: Çalışmanın önceki sürümleri arXiv:2309.01754 altında yayımlanmıştır. arXiv kaydı nihai dergi yayınına ve DOI 10.62056/an2isgsfg'ye bağlantı vermektedir. Bu Verianla makalesindeki bilimsel anlatım kullanıcının yüklediği yayımlanmış 32 sayfalık sürüme dayanmaktadır.

Lisans: Creative Commons Attribution 4.0 (CC BY 4.0). Telif hakkı yazar(lar)da kalmaktadır.

Finansman ve destek: Çalışmada finansman ve desteğin Swedish NCSA tarafından sağlandığı; Swedish NCSA'nın Swedish Armed Forces bünyesinde bulunduğu belirtilmektedir. Hesaplamalar ayrıca Swedish Research Council grant agreement no. 2022-06725 ile kısmen finanse edilen National Academic Infrastructure for Supercomputing in Sweden (NAISS) kapsamında KTH PDC kaynaklarıyla gerçekleştirilmiştir.

Teşekkür: Yazar Johan Håstad'a yorum ve tavsiyeleri için, Joel Gärtner'e ise ilk preprint sürümündeki Lemma 3 problemine dikkat çektiği için teşekkür etmektedir.

Veri ve yazılım notu: Çalışma deneysel veri setine dayanmamaktadır. Yazar post-processing algoritmalarını uyguladığını ve simüle kuantum algoritması çıktılarıyla doğruladığını belirtmektedir. Makalede erişilebilir ancak optimize edilmemiş Algorithm 1 uygulaması ve simülatör için Quaspy yazılım deposuna atıf yapılmıştır.

Çıkar çatışması: Yüklenen çalışmada ayrı bir çıkar çatışması bölümü tespit edilmemiştir.

Yazar katkıları: Çalışma tek yazarlıdır ve ayrı bir CRediT katkı beyanı verilmemiştir.

Temel yöntem: Ekerå–Håstad kısa DLP kuantum algoritmasının ölçüm dağılımının analitik olarak sınırlandırılması; iki boyutlu kafes analizi; Lagrange indirgeme ve Babai nearest-plane yöntemi; meet-in-the-middle enumeration; iki boyutlu kısa DLP'ye indirgeme ve Gaudry–Schost/Galbraith–Ruprai random-walk analizi.

Bilimsel içerik sınırı: Bu Verianla makalesindeki algoritmik mekanizmalar, formüller, sayısal tablolar, FF-DH ve RSA sonuçları, uygulama gözlemleri ve sınırlılıklar yüklenen kaynak çalışmaya dayanmaktadır. Dış kaynak kullanımı yalnız çalışma kimliği, yayın tarihi, dergi statüsü, DOI, lisans ve preprint-yayın ilişkisini bibliyografik olarak doğrulamak amacıyla yapılmıştır; PDF dışından yeni bilimsel bulgu eklenmemiştir.

En önemli yorum sınırı: Çalışmanın başarı olasılığı ve maliyet sınırları mantıksal kuantum algoritmasına ilişkindir. Fiziksel donanım hataları, kuantum hata düzeltmesi ve bunların getireceği ek fiziksel kaynak maliyetleri bu analizde yer almamaktadır.