Ayrık logaritma

Matematikte, özellikle soyut cebir ve uygulamalarında, ayrık logaritma, genel logaritmanın grup kuramındaki karşılığıdır. Genel olarak bakıldığında, log_a(b) ifadesi, a^x = b ifadesinin gerçel sayılar kümesi içindeki çözümlerine karşılık gelir. Benzer olarak, g ve h sonlu devirli grup G'nin elemanları olduğunda, g^x = h ifadesinin çözümü olan x sonuçlarına h'nin g tabanındaki ayrık logaritması denir.

Örnekler

Ayrık logaritmalar, muhtemelen en kolay (Z_p)^× anlaşılabilirler. Bu küme {1, …, p − 1} denklik sınıfını ihtiva eder ve asal sayı p modunda çarpmaya göre kapalıdır.

Bu kümede, bir elemanın k'ıncı kuvvetini bulmak istiyorsak, tam sayılar kümesinde, sayının k'ıncı kuvvetini alır, ardından, mod p'de sadeleştiririp, kalanı buluruz. Kalan aradığımız k'ıncı kuvveti verecektir. Bu işleme, ayrık kuvvet alma işlemi denir. Örnegin, (Z₁₇)^× çarpma grubunu ele alalım. 3⁴ ifadesini hesaplamak için, öncelikle, 3⁴ = 81 ifadesini hesaplarız. Ardından, 81'i 17'ye bölerek, kalan olan 13'e ulaşırız. Sonuç olarak, (Z₁₇)^× grubunda, 3⁴=13'tür.

Ayrık logaritma, yukarıda bahsedilen kuvvet alma işleminin tersidir. Örneğin, 3^k ≡ 13 (mod 17) denklenmini k değişkeni için çözmeye çalışalım. Yukarıda da yazdığı gibi, k=4 geçerli bir cevaptır. Buna karşın, tek cevap değildir. Örneğin, 3¹⁶ ≡ 1 (mod 17) olduğundan, n tam sayı olmak kaydıyla, tüm çözümler 3^{4+16 n} ≡ 13 × 1ⁿ ≡ 13 (mod 17) şeklinde yazılabilir.

Bu bağlamda, 4 + 16n formunda sonsuz sayıda çözüm vardır. Hatta, 16, 3^m ≡ 1 (mod 17) denklemini sağlayan en küçük sayı olduğundan, tüm çözümler bu şekildedir. Benzer olarak çözüm kümesi, k ≡ 4 (mod 16) şeklinde de ifade edilebilir.

Tanım

G, n elemanlı sonlu bir döngüsel grup olsun. Burada, grubun çarpma gösteriminde olduğunu varsayalım. g bahsi geçen grubun herhangi bir üreteci olsun. Bu durumda, G grubunun tüm elemanları, g 'nin bir kuvveti olarak yazılabilir, ör: b = g^k. Burada, b, g 'nin k'ıncı kuvvetidir diyebiliriz.

\log _{g}\colon G\rightarrow \mathbb {Z} _{n}

(burada Z_n, n modundaki tam sayıların halkasını ifade etmektedir. Burada G grubundaki her b sayısı, k tam sayısını işaret etmektedir. Bu işaret eden fonksiyon, bir grup isomorfizması olup, g bazında ayrık logaritma işlevi olarak isimlendirilir.

Genel logratima için geçerli olan baz değiştirme işlemi burada da çalışmaktadır. Örneğin, h, G grubunun diğer bir üreteci olsun. Baz değiştirme işlemi aşağıdaki gibi uygulanabilir:

\log _{h}(b)=\log _{h}(g)\cdot \log _{g}(b).

Algoritmalar

Ayrık logaritma problemi log_g b 'nin genel çözümünü hesaplayan hızlı ve verimli bir algoritma bilinmemektedır. En naif algoritma, g sayısının, b sayısına ulaşılana dek kuvvetlendirimesi olarak tanımlanabilir. Bu süreç içerisinde ulaşılan kuvvet k, ifadenin çözümü olacaktır. Bu algoritmaya çarpma işlemini kullanarak deneme yanılma yöntemi denir. Bu basit algoritmanın çalışma süresi, işlemin yapıldığı G grubunun büyüklüğü ile doğru orantılıdır. Dolayısı ile, çalışma süresi grubun büyüklüğünü ifade eden sayının basamak sayısı ile üstel ilişki içerisindedir. Buna karşın, Peter Shor tarafında keşfedilmiş, quantum bilgisayarlarda çalışan, polinom zamanlı, verimli bir algoritma bilinmektedir.^[1]

Daha karmaşık ve sofistike algoritmalar bilinmektedir. Bu algoritmalar genellikle, çarpanlara ayırma probleminin çözümünden esinlenmişlerdir. Doğal olarak, yukarıda bahsedilen algoritmadan daha verimli ve hızlı çalışmaktadırlar. Buna karşın hiçbiri, problemi polinom zamanda çözememektedir. Bu algoritmaların bazıları söyledir:

Bebek-adım dev-adım
Logaritmalar için Pollard'ın rho algoritması
Pollard'ın kanguru algoritması (Pollard'ın lambda algoritması olarak da bilinir)
Pohlig–Hellman algoritması
Index calculus algoritmaıs
Sayı cisimleri eleği algoritması
Fonksiyon cisimleri eleği algoritması

Çarpanlara Ayırma ile Karşılatırma

İki problem birbirinden farklı olsa dahi, bazı benzerlikler taşımaktadır:

iki problemin de çözümü zordur (sonucu verimli ve hızlı hesaplayan herhangi bir algoritma bilinmemektedir),
iki problem için de quantum bilgisayarlar üzerinde verimli ve hızlı hesaplayan algoritmalar bilinmektedir,
bir problemi çözen algoritma, diğerine uyarlanabilmektedir ve
iki problemin de çözümünün de zor olması, kriptografik yapılarda kullanılmalarına sebep olmuştur.

Kriptografi

Grup kuramında, ayrık logaritmanın hesaplanmasının zor olduğu gruplar mevcuttur. Bazı gruplarda, (ör: yüksek mertebeleri asal kuvvetli alt gruplar (Z_p)^×) en kötü durumlar için ayrık logaritma hesaplayan verimli algoritmalar bulunamamıştır. Ek olarak, işlemin ortalama karmaşıklığı'nın rastegele öz-indirgenebilirlik problemi kadar zor olduğu gösterilebilmiştir.

Aynı zamanda, ayrık logaritma probleminin tersinin, yani ayrık kuvvet alma işleminin kolay olduğu, kare alarak kuvvet alma yöntemi ile verimli bir şekilde gösterilmiştir. Bu iki işlem arasındaki asimetri, tam sayılar kümesindeki çarpanlara ayırma ve çarpma işlemi arasındaki bağıntıya benzer. Bu bağıntı, kriptografik yapıtaşlarının oluşturulmasında kullanılmaktadır.

Genel olarak, ayrık logaritma problemi, kriptografide döngüsel sonlu gruplarda uygulanır (Z_p)^×. Örnek olarak, ElGamal, Diffie-Hellman ve Dijital imza verilebilir.

Yeni nesil kriptografi uygulamaları, ayrık logaritma problemini, sonlu cisimler üzerinde kurulan ellipsel eğrilerin döngüsel alt grupları üzerinde uygulamaktadır. bkz ellipsel eğri kriptografisi

Kaynakça

^ Shor, Peter (1997). "Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer". SIAM Journal on Computing. 26 (5). ss. 1484-1509. arXiv:quant-ph/9508027 $2.

Richard Crandall; Carl Pomerance. Chapter 5, Prime Numbers: A computational perspective, 2nd ed., Springer.
Stinson, Douglas Robert (2006), Cryptography: Theory and Practice (3.3 isbn=978-1-58488-508-5 bas.), Londra: CRC Press KB1 bakım: Dikey çizgi eksik (link)

[1] Shor, Peter (1997). "Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer". SIAM Journal on Computing. 26 (5). ss. 1484-1509. arXiv:quant-ph/9508027 $2.

[1]