Sonlu cisimlerde diskret logaritma problemi
Discrete logaritm problem in finite fields
- Tez No: 258605
- Danışmanlar: PROF. DR. ALİ BÜLENT EKİN
- Tez Türü: Doktora
- Konular: Matematik, Mathematics
- Anahtar Kelimeler: Belirtilmemiş.
- Yıl: 2009
- Dil: Türkçe
- Üniversite: Ankara Üniversitesi
- Enstitü: Fen Bilimleri Enstitüsü
- Ana Bilim Dalı: Matematik Ana Bilim Dalı
- Bilim Dalı: Belirtilmemiş.
- Sayfa Sayısı: Belirtilmemiş.
Özet
GF(q) mertebesi q olan sonlu bir cisim ve g, GF(q) nun bir primitif elemanı olmak üzere q, g ve GF(q) verildiğinde y=g^x, 0<= 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 sonlucisimlerde 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 diskretlogaritma 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 rho, 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 rho-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.
Özet (Çeviri)
Let GF(q) a finite field of order q and g a primitive element of GF(q), for given q, g andy in GF(q) finding integer x such that y=g^x ,0<= x<q-1 is called discrete logarithm problemin finite fields. At first,this problem which has a long history in number theory was used for somecomputations in finite fields and then it started to play an important rolein cryptography by shift-register sequences displaced rotor machines in the1950s. When the prime power q in here is choosen sufficiently large,calculating the discrete logarithm x is hard. In 1976, Diffie and Hellmanimproved the Key-exchange method leading to emergence of public keycryptosystems by using this hardness as a base. Nowdays, the security of themany cryptographic applications depend on the hardness of this problem.Another important problem used in cryptography and related to thediscrete logarithm problem is factoring problem. Although there is not anyword for discrete logarithm problem like the famous quates of Gauss aboutimportance of the factoring in mathematics, it is thought more hard than thefactoring.In this thesis, We investigated square root algorithms calculatingthe discrete logarithm problem, namely, Baby step-Giant step,Pollard rho and Kangaroo algorithms. Gadiyar et al.(2009) improved a probabilistic, square root algorithm by thinking inverseof the Repeated square-multiply algorithm. Running time of theGadiyar's algorithm is investigated in details by interpreting the algorithmin a different way and compared with Pollard rho algorithm. At the sametime, this algorithm has improved such that negligible memory requirement.In addition to square root algorithms, After studying some exponentialalgorithms called index calculus algorithms, we examined the NumberField Sieve algorithm which is the most effective algorithm in finitefields.
Benzer Tezler
- On the conic representation of some quartics
Bazı kuartıkların koniklerle temsili hakkında
İBRAHİM KIRAT
- Sonlu cisimlerde bazı katsayıları verilen indirgenmez polinomların belirlenmesi
The determination of irreducible polynomials over finite fields with given several coefficients
KÜBRA AFŞAR
- Elastik cisimlerde iki boyutlu doğrusal sürtünmesiz temas probleminin sonlu elemanlar metodu ile analizi
2-d frictionless contact analysis of elastic continua with finite element method
OKAN ADALI
Yüksek Lisans
Türkçe
2018
İnşaat Mühendisliğiİstanbul Teknik Üniversitesiİnşaat Mühendisliği Ana Bilim Dalı
PROF. DR. MEHMET HAKKI OMURTAG
PROF. DR. NİHAL ERATLI
PROF. DR. NAZMİYE YAHNİOĞLU
- Sonlu şekil değiştirebilen kısıtlı termoelastik cisimlerde dalga yayılması ve kayma bandı oluşumu
Wave propagation and shear band formation in finite deformable constrained thermoelastic solids
BAHADIR ALYAVUZ
Doktora
Türkçe
2008
İnşaat MühendisliğiGazi Üniversitesiİnşaat Mühendisliği Bölümü
PROF. DR. TEKİN GÜLTOP
- Çok boyutlu cisimlerde geçici rejimde ısı transferinin sonlu hacimler ve sonlu farklar yöntemleriyle hesaplanması
Calculation of heat transfer for multi-dimensional bodies at transient regime using finite volume and finite difference methods
HASAN DANIŞMAN
