Ayrık Logaritma (Discrete Logarithm)

Yazan: Şadi Evren ŞEKER

Ayrık logaritma daha çok soyut matematik alanında kullanılan bir işlemdir. Normal logaritma işlemi bilindiği üzere üst alma işleminin (exponent) tersidir. Örneğin doğal veya karmaşık sayılar için $log a (b)$ logaritma gösterimi $a x = b$ işleminin tersidir ve sonucu x değeridir. Ayrık logaritma ise doğal veya karmaşık sayılar üzerinde değil dairesel gruplar üzerinde tanımlı bir işlemdir ve bir G grubu için $g x = h$ işleminin tersini veren işlemdir.

Ayrık logaritmaları anlamanın en kolay yollarından birisi de (Z_p)^×. ahenk sınıfı (congruence class) üzerindeki işlemleridir. Bir ahenk sınıfı 0 ile p-1 arasındaki ayrık sayılar kümesi olup bu küme üzerinde tanımlı olan herhangi bir işlem yine bu küme içinden bir sonuç döndürmeldir. Basitçe modulo p işlem kümesi olarak düşünülebilir ve yapılan her işlemin p tabanında modulo alındığı düşünülebilir.

Daha açık bir şekilde ayrık üst (discrete exponent) denilen işlem bir sayının verilen üst değerinin verilen modulo p için hesaplanmasıdır. Yani sayının istenilen üstü hesaplanır ve p değerine bölünür sonuç bölme işleminin kalan kısmıdır.

Örneğin (Z₁₇)^× ahenk sınıfında 3⁴ işlemini ele alalım. Biliyoruz ki 3⁴ = 81 ‘dir. 81 sayısının 17 sayısına bölümünden kalan değer ise 13′tür bu durumda (Z₁₇)^× ahenk sınıfı için 3⁴ = 13 ‘tür denilebilir.

Ayrık logaritma ise bu işlemin tersidir. Örneğin 3^k ≡ 13 (mod 17) denklemini ele alalım. Buradaki k değerinin 4 olduğunu biraz önce görmüştük. Ancak bu tek çözüm değildir. Örneğin 3²⁰ ≡ 13 (mod 17) denkliği de doğrudur.

Bu durum için 3^{4+16 n} ≡ 13 (mod 17) denklemi çıkarılabilir, çünkü her 16 üstte bir mod 17 için 3′ün üstleri tekrarlamaktadır.

Örnek:

2 sayısının Z₂₉ ‘da bir ilkel kökü (primitive root) olup olmadığını bulunuz ve L₂(15) ayrık logaritma değerini bulunuz.

Çözüm:

2 sayısının Z₂₉‘da ilkel kökü bulunması, herhangi bir üstünün mod 29′da 1′e eşit olması demektir.

L₂(15) değeri ise, 2 sayısı ile üretilen grubun 15 değerine sahip olduğu eleman sayısıdır. Yani 2^k = 15 mod 29 için k değeridir.

Bu işlemi yapabilmek için 2 sayısının mod 29′daki bütün üstleri teker teker denenir. Örneğin:

2⁰ mod 29 ≡ 1

2¹ mod 29 ≡ 2

2² mod 29 ≡ 4

2³ mod 29 ≡ 8

2⁴ mod 29 ≡ 16

2⁵ mod 29 ≡ 32 ≡ 3

2⁶ mod 29 ≡ 64 ≡ 6

2⁷ mod 29 ≡ 128 ≡ 12

….

2²⁷ mod 29 ≡ 134217728 ≡ 15

2²⁸ mod 29 ≡ 268435456 ≡ 1

Yukarıdaki sayılara göre ayrık logaritması L₂(15) = 27 ve ilkel kökü vardır denilebilir.

« Ellipsel Eğri (Elliptic Curve) | Ağaçlar (tree) »

Yorumlar

Henüz yorum yapılmamış.

Ellipsel Eğri (Elliptic Curve) : bilgisayar.kavramlari.com | 07 May 2008, 04:01
[...] eğrilerin şifreleme sistemlerinde kullanılması aynı zamanda ayrık logaritma (discrete logarithm) hesaplamalarını da beraberinde getirmektedir. Buna göre bir sayının kendisi ile defalarca kere [...]
Menezes-Qu-Vanstone Şifrelemesi (Cipher) : bilgisayar.kavramlari.com | 08 Jun 2008, 18:10
[...] ahenk sınıfı (congurence class) yani işlemlerin gerçekleştiği mod [...]

Bu Yazı Hakkında

Bilgisayar Kavramları üzerinde şu anda okumakta olduğunuz 'Ayrık Logaritma (Discrete Logarithm)' isimli yazı 06 May 2008 tarihinde, saat: 22:52 'de Şadi Evren ŞEKER tarafından gönderilmiş, toplam 953 defa okunmuştur.

Benzer yazıları Bilgisayar Matematiği, Veri Güvenliği(Cryptography) kategorilerinden okuyabilirsiniz. Yazar ile irtibat kurmak için email gönderebilirsiniz. Yazıya yorum yapabilir ya da yapılan yorumları RSS 2.0 ile takibe alabilirsiniz.

Yazarın Kitabı

Bu yazının yazarı Şadi Evren ŞEKER'in son çıkan kitabı "Programlama ve Veri Yapılarına giriş (C, C++ ve JAVA ile)" hakkında bilgi almak için Buraya tıklayabilirsiniz.
Eklenen Son Yazılar