Yazan : Şadi Evren ŞEKER

Bilgisayar bilimlerinde özellikle şifreleme sistemlerinde kullanılan ve ayrık matematik altında incelenen ayrık logaritma (discrete logarithm) problemini çözmek için geliştirilen bir yöntemdir. İsmi basitçe büyük ve küçük adımlardan esinlenerek konulmuştur. Ayrık logaritma alınırken, en klasik ve etkili yöntem bütün üslerin denenmesidir. Örneğin bir radyoda kanal ararken, önce hızlı çevirerek arama yapılır sonra istenen frekansa yaklaşınca yavaş çevirerek hassas ayar yaparız.

Bebe ve dev adımı çözümü de benzer şekilde önce dev adımlarla arama yapar. Yakın olan bir değer için, bu değerden yola çıkarak ufak ufak arama işlemini sürdürür.

Durumu anlamak için iki basit örnek verelim.

Örnek 1:

Örneğin ayrık logaritma hesabı yapacağımız denklem aşağıdaki şekilde verilmiş olsun:

3a (mod 101) = 37

Soru a değeridir. Bu soruyu aşağıdaki şekle çevirmek mümkündür:

a = log3 37 (mod 101)

Sorunun çözümü için bebek ve dev adımları yaklaşımımızda öncelikle bir dev adım miktarı belirliyoruz. Çözüm için örneğin 10 sayısını belirleyelim. Yani 10ar 10ar dev adımlar atarak önce arama yapacak sonra yakın bir değer bulduğumuzda teker teker bebek adımları atarak tam sonucu bulmaya çalışacağız.

Dev Adımlar 0 1 2 3 4 5 6 7 8 9
3-10i (mod 101) 1 14 95 17 36 100 87 6 84 65
37. 3-10i (mod 101) 37 13 81 23 19 64 88 29 78 82

Yukarıdaki tabloda, dev adımları hesaplamak için öncelikle, 3-10i (mod 101) değerlerini verilen her i değeri için hesapladık. Ardından bu değerleri (mod 101) için 37 ile çarptık. Bu işlemi yapmak için basit bir kod yazılabilir.

Çıkan sonuçlara bakıyoruz ve 3’ün bir katını bulmaya çalışıyoruz. Çıkan sonuçlardan sadece 81 (son satırdaki 3. Sonuç) 3’ün kuvvetidir. Bu değeri bulduktan sonra dev adım atma işlemini tamamlıyoruz. Bir sonraki işlem olan bebek adımlarına geçebiliriz.

81 = 34 olduğuna göre,

34(mod 101) = 37. 3-20 (mod 101) şeklinde yazabiliriz. Eşitliğin iki tarafını eşitlersek:

320 34(mod 101) = 37. (mod 101) sonuç olarak aradığımız a değeri 24 olarak bulunmuş olur.

Gerçekten bu sonucun doğru olduğunu, 324 (mod 101) = 37 eşitliğini sağlayarak görebiliriz.

Örnek 2:

Bu örnekte biraz daha ufak sayılar seçerek yukarıdaki örnekte bulunan tabloyu da adım adım çıkarmayı deneyelim.

Örneğimiz bu sefer,

a = log3 5 (mod 11) olsun.

Sorunun çözümü için öncelikle dev adımı belirliyoruz. Dev adımlarımızı 4 olarak belirleyelim ve tablomuzu oluşturalım:

Dev Adımlar 0 1 2
3-4i (mod 11) 1 3 9
5. 3-4i (mod 11) 5 4 1

Yukarıdaki sayıların hesaplanmasını adım adım açıklayalım:

3-4i (mod 11) değeri, i=0 için , 3-0 (mod 11) olarak hesaplanır ve bu değer 1 olarak bulunur.

3-4i (mod 11) değeri, i=1 için , 3-4 (mod 11) olarak hesaplanır ve bu değer 1/81 olarak bulunur. Modüler aritmetikte kesirli sayıların tam sayıya çevrilmesi gerekir. Z11‘de çalıştığımız için payda kısmını sadeleştiriyoruz. 81 (mod 11) = 4 olduğu için kesirli sayımız ¼ olarak yazılır. Tam sayıya çevirmek için pay kısmına 11 ekleyerek tam bölünene kadar devam ederiz. (1+11) / 4 = 12 / 4 = 3 olarak bulunur.

3-4i (mod 11) değeri, i=2 için , 3-8 (mod 11) olarak hesaplanır ve bu değer 1/6561 olarak bulunur. 6561 (mod 11) = 5 olarak bulunur. Dolayısıyla bu kesir 1/5 olarak düşünülebilir. Tam sayıya çevirmek için pay kısmına 11 ekleyerek devam ediyoruz, 12/5, 23/5, 34/5, 45/5 = 9 değerini buluyoruz.

Yukarıdaki tabloda sadece 3 adım bulunmasının sebebi, Z11‘de çalışıyor olmamızdır. Yani bir adım daha gidecek olursak 3-12 (mod 11) değeri gibi, 11’den büyük bir değere ulaşılacaktır dolayısıyla i = 2 için son değeri bulup tabloyu bitiriyoruz.

Şimdi bebek adımlarına başlayabiliriz. Bulduğumuz sonuçlar arasından 3’ün bir kuvvetini arıyoruz ve bu kuvveti tablomuzun son satırının son sütunundaki 1 değeri ile buluyoruz.

30 (mod 11)= 5. 3-8 (mod 11) eşitliğini yazabiliriz.

Sonuç olarak çözümümüz 8 bulunuyor ve

log3 5 (mod 11) = 8 olarak buluyoruz.

Sonucu sağlamak için , 38 (mod 11) = 5 doğruluğu sınanabilir.

Bir cevap yazın

E-posta hesabınız yayımlanmayacak. Gerekli alanlar * ile işaretlenmişlerdir