Yazan : Şadi Evren ŞEKER
Bilgisayar bilimlerinde özellikle veri güvenliği konusunda kullanılan ayrık logaritma probleminin (discrete logarithm) çözümü için geliştirilmiş algoritmalardan birisidir. Literatürde algoritmayı bulan kişi olan Daniel Shank’a ithafen Shank’s algorithm olarak geçer.
Algoritma basitçe, 
denklemine çözüm arar. Bu denklemde p bir asal sayı olmak üzere, denklemin çözümünün en azından pozitif tam sayı çözümlerini bulabilmektedir.
Algoritmayı aşağıdaki şekilde açıklayabiliriz:
denklemi, klasik bir ayrık logaritma denklemidir ve buradaki amaç a değerini bulmaktır. Bu denklemde, a değerinin alabileceği değerler 0 ≤ a ≤ p-2 şeklinde yazılabilir ve denklem aşağıdaki şekle indirgenebilir:
y= xa mod p
bu denklemdeki a için , a = jm + i şeklinde bir yazım getirirsek (bu noktada, bütün sayı sisteminin doğrusal (linear) olduğunu ve sayı sistemindeki bütün sayıların jm+i şeklinde yazılabileceğine dikkat ediniz):
sonucuna ulaşırız. Bu noktada dikkat edilecek bir husus, shank algoritmasının p-1 gibi bir asal sayının bir noksanının tam kare olması durumunda çalıştığdır ve bu özellik fermanın küçük teoreminden (fermat’s little theorem) çıkmaktadır.
Buradan elde edilebilecek denklemi aşağıdaki şekilde çözebiliriz:
B≡ amj+i mod p, deklemi açarsak
B≡ amj a i mod p
B a -i≡ amj mod p
Sonucunu elde ederiz. Şayet bu denklikteki (i, B a -i) ile (j, amj) değerlerini eşit yapan bir değer bulunursa şayet bu denklemi çözebiliriz.
Bu denklik durumunun anlamı, logaB ≡ mj+i (mod p-1) denkleminin sağlanması olacaktır.
Örnek
Shank algoritmasını daha iyi anlayabilmek için aşağıdaki denklemi çözmeye çalışalım.
log 3 525 mod 809 = ?
Bu denklem shank algoritması ile çözülebilir, 
öncelikle, 0 ≤ j ≤ 28 arasındaki değerler için (j, 99j
mod 809) sonuçlarını listeleyelim:
(0, 1) (1, 99) (2, 93) (3, 308) (4, 559) (5, 329) (6, 211) (7, 664) (8, 207) (9, 268) (10, 644) (11, 654) (12, 26) (13, 147) (14, 800) (15, 727) (16, 781) (17, 464) (18, 632) (19, 275) (20, 528) (21, 496) (22, 564) (23, 15) (24, 676) (25, 586) (26, 575) (27, 295) (28, 81)
Ardından denkliğin ikinci kısmı olan (i, 525.3-i mod 809) ikililerini listeleyelim:
(0, 525) (1, 175) (2, 328) (3, 379) (4, 396) (5, 132) (6, 44) (7, 554) (8, 724) (9, 511) (10, 440) (11, 686) (12, 768) (13, 256) (14, 355) (15, 388) (16, 399) (17, 133) (18, 314) (19, 644) (20, 754) (21, 521) (22, 713) (23, 777) (24, 259) (25, 356) (26, 658) (27, 489) (28, 163)
İki listedeki ortak sayıyı ararsak, 644 sayısının iki listede de geçtiğini görürüz. Bu değerleri veren i ve j değerlerini denkleme yerleştiriyoruz:
log3525 ≡ 29 . 10 + 19 = 309 olarak bulunur.
Algoritmanın adım adım işleyişi (Hadi Bey’in soruları üzeirne ekliyorum)
Algoritmanın çalışması sırasında bazı değişkenlerin hesaplanması gerekir. Bu değişkenleri aşağıdaki örnek üzerinden anlayarak öğrenelim:
Örneğimiz,
log2 15 mod 19 sorusunu çözmek olsun.
Buradaki p-1 değeri 18 olarak bulunur.
a değeri 2 ‘dir (2 tabanına göre logaritma alınmış)
a-1 değeri hesaplanır (a’nın çarpmaya göre tersi diğer bir deyişle mod 19’da 1 sonucu veren değer. Bunun için uzatılmış öklit bağlantısı (Extended euclidean algorithm) kullanılabilir) a-1 değeri 10’dur. Gerçekteden de 2 x 10 mod 19 = 1 olduğu görülebilir.
m değeri 5’tir ( 18’in karekökü 5 olduğu için)
am mod 19 hesaplanır : 25 mod 19 = 13 olarak bulunur.
Şimdi listelerimizi hazırlayalım. İlk listede (i , ami) değerlerini hazırlayacağız.
(0,1) , ( 1,13) , (2, 17 ) , (3,12) , ( 4,4)
ikinci listemizde ise (j, Ba-j) değerini hesaplayacağız.
(0,15) , ( 1,17) , (2,18), (3,9) , (4,14)
iki listede ortak sonç veren değerleri yazalım :
(2,17) ile ( 1, 17)
bu iki değer birbirine eşitlenirse:
ami = Ba-j mod p
25.2 = 15.2-1 (Değerleri yazdık)
210 = 15.2-1 (eşitliğin her iki tarafını da 2-1 değerine bölersek)
211 = 15
log2 15 mod 19 = 11 olarak bulunur.
Gerçekten de 211 = 2048 ve 2048 mod 19 = 11 olduğu görülebilir.
Merhaba, 525 nereden ve nasıl hesaplandı. Açıklarsanız çok sevinirim.
sorunuzda haklısınız, soru metninde hata vardı, yazıda ilgili hatayı düzelttim. ilginiz için teşekkürler.
Merhaba, halen netleşmeyen noktalar var kafamda. , (99^j (mod 809)) denklemi açılırken 99 değeri nasıl elde edildi. o noktayı yakalayamadım. açıklarsanoz sevinirim.
99 değeri a değerinin (3 değerinin) tersidir. Sanırım yazıda algoritma anlaşılmııyor. Daha iyi anlaşılması için yukarıdaki yazıya ekleme yapıyorum. Adım adım algoritmanın nasıl çalışacağını ve bir örnek daha ekliyorum. İnşallah yardımcı olur.
Başarılar
Halen bulanık olan noktalar var. Teker teker hepsini yazıyorum. Netleştirirseniz çok sevinirim.
1- İlk örnekte 99 değerinin, 3 değerinin tersi olduğunu belirtmişsiniz. 3×99=(297 mod 809) değeri 1’e eşit değil. bu noktada bir hatamı oldu acaba?
2- “m değeri 5′tir ( 18′in karekökü 5 olduğu için)” şeklinde bir ibare kullanılmış 18’in karekökü (3 kök 2 ) yani 4.24 dolaylarında bir değer. ikinci örnekte 0<=i<=m-1 den yola çıkarak diyorum 0<=i<=3.24 yani 0<=i<=3 aralığında alınması gerekmiyormuydu. "18′in karekökü 5 olduğu için" sözünü tam anlayamadım. Ayrıca ilk örnektede 808'in kökü 29'a eşit değil. kök 808 = 28.42 dolaylarında bir sayı buradada i nin 0 ile 28.42-1 yani 27.42 yani 27 eşit aralığında alınması gerekmiyormu? 3- ikinci örnekte a'nın tersi 10 olarak hesaplandı ancak daha sonra kullanıldığına rastlamadım. 4- ikinci örnekte a^m mod 19 hesaplanır demişsiniz ve m değerini 5 olarak hesaplamanıza rağmen 2^10 mod 19 = 13 hesaplamışsınız. 5- 2^11 mod 19 = 15, denklemde 11 yazılmış atladınız herhalde. Kusura bakmayın çok allak bullak olduğu için tekrar tekrar soruyorum. Sağolun
teker teker cevaplamaya çalışayım.
99 değeri 3^10 mod 809 denkleminde bulunur.
karekök ibaresi doğrudur. Bulduğunuz kareköklerin ceiling (tavan) fonkisiyonunu alırsınız. Örneğin 4.xx için 5 veya 28.xxx için 29 yuvarlaması yaparsınız.
m değeri konusunda haklısınız yanlışlıkla 10 yazılmış, yazıda 5 olarak düzeltiyorum bu durumda diğer yorumlarınız da çözülmüş oluyor. yani 2^5 mod 19 = 13 hesabı yapılmış olmalıydı zaten 2^10mod19 13 değildir.
başarılar
Merhaba, 99 değeri 3’ün tersi ve 3^10 mod 809 demişsiniz. buradaki 10 değeri nereden geldi? denklemde (a^m.j) deki m den geldiğini düşündüm ilk önce ancak m değerini 29’a eşit. ayrıca 3×99=297 mod 809 = 297. 1’e eşit olmamış. lütfen yardımcı olun.
3^10=59049 =72×809+801 dolayısıyla 3^10 mod 809 = 801 yani 99 değil
nedense bu yorumlara ancak hep geç saatlerde cevap yazabiliyorum kusura bakmayın biraz yanlış anlamaya sebep oldu yorumlar. 99 değerini açık ve net şekilde anlatayım.
a^m mod p olarak hesaplanır.
bu soruda a = 3 , m = 29 ( 808’in karekökü) ve p = 809 olduğu için
a^29 mod 809 denkleminden 29 bulunur. (bu denklemlerdeki şapka işareti üst anlamındadır)
umarım yardımcı olur.
başarılar
Çok teşekkür ederim, yazı çok yararlı oldu. Sağolun.