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, loga(b) ifadesi, ax = 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, gx = h ifadesinin çözümü olan x sonuçlarına h'nin g tabanındaki ayrık logaritması denir.

Ayrık logaritmalar, muhtemelen en kolay (Zp)× 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, (Z17)× çarpma grubunu ele alalım. 34 ifadesini hesaplamak için, öncelikle, 34 = 81 ifadesini hesaplarız. Ardından, 81'i 17'ye bölerek, kalan olan 13'e ulaşırız. Sonuç olarak, (Z17)× grubunda, 34=13'tür.

Ayrık logaritma, yukarıda bahsedilen kuvvet alma işleminin tersidir. Örneğin, 3k ≡ 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, 316 ≡ 1 (mod 17) olduğundan, n tam sayı olmak kaydıyla, tüm çözümler 34+16 n ≡ 13 × 1n ≡ 13 (mod 17) şeklinde yazılabilir.

Bu bağlamda, 4 + 16n formunda sonsuz sayıda çözüm vardır. Hatta, 16, 3m ≡ 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.

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 = gk. Burada, b, g 'nin k'ıncı kuvvetidir diyebiliriz.

(burada Zn, 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.

Ayrık logaritma problemi logg 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çerinde 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.

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 (Zp)×) 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.