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.

Örnekler

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.

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 = 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.

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:

Algoritmalar

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çersindedir. 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:

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

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

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 (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.

Genel olarak, ayrık logaritma problemi, kriptografide döngüsel sonlu gruplarda uygulanır (Zp)×. Ö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

Referanslar

  1. Shor, Peter (1997). "Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer". SIAM Journal on Computing 26 (5): 1484–1509. arXiv:quant-ph/9508027.
This article is issued from Vikipedi - version of the 8/21/2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.