Akademik Veri Yönetim Sistemi
Tezin Türü: Doktora
Tezin Yürütüldüğü Kurum: Ankara Üniversitesi, Fen Bilimleri Enstitüsü, Türkiye
Tezin Onay Tarihi: 2009
Tezin Dili: Türkçe
Öğrenci: MURAT ŞAHİN
Danışman: ALİ BÜLENT EKİN
Özet:Fq mertebesi q olan sonlu bir cisim ve g, Fq nun bir primitif elemanı olmak üzere q, g ve y ∈ Fq verildiğinde y = gx, 0 6 x < q − 1 olacak şekildeki x tamsayısını bulma problemine sonlu cisimlerde diskret logaritma problemi denir. Sayılar teorisinde uzun bir geçmişe sahip olan bu problem önceleri sonlu cisimlerde bazı hesaplamaları yapabilmek için kullanılmış, 1950 li yıllarda rotor makinelerinin yerini kaydır-kaydet dizilerinin almasıyla kriptografide önemli bir rol oynamaya başlamıştır. Burada bir asalın kuvveti olan q tamsayısı yeterince büyük seçildiğinde x diskret logaritmasını hesaplamak zordur. Bu zorluğu temel alarak 1976 yılında Diffie ve Hellman açık anahtar kripto sistemlerinin doğmasına vesile olan anahtar değiş-tokuş yöntemini geliştirmişlerdir. Günümüzde, bir çok kriptografi uygulamasının güvenliği diskret logaritma probleminin bu zorluğuna dayanmaktadır. Diskret logaritma problemi ile ilgili olan ve kriptografide kullanılan diğer bir önemli problem de çarpanlara ayırma problemidir. Gauss’un çarpanlara ayırmanın matematikteki önemini dile getiren ünlü sözüne benzer herhangi bir söz diskret logaritma problemi için edilmemiş olmasına rağmen bu problemin çarpanlara ayırma probleminden daha zor olduğu düşünülmektedir. Bu tezde, sonlu cisimlerdeki diskret logaritmayı hesaplayan karekök zamanlı algoritmalardan Küçük adım-Büyük adım, Pollard ρ, Kanguru ve Pohlig-Hellman algoritmalarını inceledik. Gadiyar vd. (2009) Ardışık kare alma-çarpma algoritmasının tersini düşünerek diskret logaritma için olasılıksal, karekök zamanlı bir algoritma geliştirdiler. Bu algoritmayı farklı yorumlayarak çalışma zamanını detaylı bir şekilde inceleyip Pollard ρ-algoritması ile kıyasladık. Aynı zamanda, ihmal edilebilir bir hafıza gereksinimi duyacak şekilde bu algoritmayı geliştirdik. Karekök zamanlı algoritmalara ilaveten indeks calculus algoritmalar olarak adlandırılan yarı üstel zamanlı algoritmalardan bazılarını inceledikten sonra, sonlu cisimlerdeki diskret logaritmayı en etkili şekilde hesaplayan Sayı Cismi Eleği algoritmasını inceledik.Abstract Let Fq a finite field of order q and g a primitive element of Fq, for given q, g and y ∈ Fq finding integer x such that y = gx, 0 6 x < q − 1 is called discrete logarithm problem in finite fields. At first, this problem which has a long history in number theory was used for some computations in finite fields and then it started to play an important role in cryptography by shift-register sequences displaced rotor machines in the 1950s. When the prime power q in here is choosen sufficiently large, calculating the discrete logarithm x is hard. In 1976, Diffie and Hellman improved the Key-exchange method leading to emergence of public key cryptosystems by using this hardness as a base. Nowdays, the security of the many cryptographic applications depend on the hardness of this problem. Another important problem used in cryptography and related to the discrete logarithm problem is factoring problem. Although there is not any word for discrete logarithm problem like the famous quates of Gauss about importance of the factoring in mathematics, it is thought more hard than the factoring. In this thesis, We investigated square root algorithms calculating the discrete logarithm problem, namely, Baby step-Giant step, Pollard ρ and Kangaroo algorithms. Gadiyar et al. (2009) improved a probabilistic, square root algorithm by thinking inverse of the Repeated square-multiply algorithm. Running time of the Gadiyar’s algorithm is investigated in details by interpreting the algorithm in a different way and compared with Pollard ρ-algorithm. At the same time, this algorithm has improved such that negligible memory requirement. In addition to square root algorithms, After studying some exponential algorithms called index calculus algorithms, we examined the Number Field Sieve algorithm which is the most effective algorithm in finite fields.