Matematikte, özellikle soyut cebir ve uygulamalarında, ayrık logaritma, genel logaritmanın grup kuramındaki karşılığıdır. Genel olarak bakıldığında, loga(b) ifadesi, ax = b ifadesinin gerçel sayılar kümesi içindeki çözümlerine karşılık gelir. Benzer olarak, g ve h sonlu devirli grup G'nin elemanları olduğunda, gx = h ifadesinin çözümü olan x sonuçlarına h'nin g tabanındaki ayrık logaritması denir.
Örnekler
Ayrık logaritmalar, muhtemelen en kolay anlaşılabilirler. Bu küme {1, …, p − 1} ihtiva eder ve asal sayı p modunda çarpmaya göre kapalıdır.
Bu kümede, bir elemanın k'ıncı kuvvetini bulmak istiyorsak, tam sayılar kümesinde, sayının k'ıncı kuvvetini alır, ardından, mod p'de sadeleştiririp, kalanı buluruz. Kalan aradığımız k'ıncı kuvveti verecektir. Bu işleme, ayrık kuvvet alma işlemi denir. Örnegin, (Z17)× çarpma grubunu ele alalım. 34 ifadesini hesaplamak için, öncelikle, 34 = 81 ifadesini hesaplarız. Ardından, 81'i 17'ye bölerek, kalan olan 13'e ulaşırız. Sonuç olarak, (Z17)× grubunda, 34=13'tür.
Ayrık logaritma, yukarıda bahsedilen kuvvet alma işleminin tersidir. Örneğin, 3k ≡ 13 (mod 17) denklenmini k değişkeni için çözmeye çalışalım. Yukarıda da yazdığı gibi, k=4 geçerli bir cevaptır. Buna karşın, tek cevap değildir. Örneğin, 316 ≡ 1 (mod 17) olduğundan, n tam sayı olmak kaydıyla, tüm çözümler 34+16 n ≡ 13 × 1n ≡ 13 (mod 17) şeklinde yazılabilir.
Bu bağlamda, 4 + 16n formunda sonsuz sayıda çözüm vardır. Hatta, 16, 3m ≡ 1 (mod 17) denklemini sağlayan en küçük sayı olduğundan, tüm çözümler bu şekildedir. Benzer olarak çözüm kümesi, k ≡ 4 (mod 16) şeklinde de ifade edilebilir.
Tanım
G, n elemanlı sonlu bir olsun. Burada, grubun çarpma gösteriminde olduğunu varsayalım. g bahsi geçen grubun herhangi bir üreteci olsun. Bu durumda, G grubunun tüm elemanları, g 'nin bir kuvveti olarak yazılabilir, ör: b = gk. Burada, b, g 'nin k'ıncı kuvvetidir diyebiliriz.
(burada Zn, n modundaki tam sayıların halkasını ifade etmektedir. Burada G grubundaki her b sayısı, k tam sayısını işaret etmektedir. Bu işaret eden fonksiyon, bir grup isomorfizması olup, g bazında ayrık logaritma işlevi olarak isimlendirilir.
Genel logratima için geçerli olan baz değiştirme işlemi burada da çalışmaktadır. Örneğin, h, G grubunun diğer bir üreteci olsun. Baz değiştirme işlemi aşağıdaki gibi uygulanabilir:
Algoritmalar
Ayrık logaritma problemi loggb 'nin genel çözümünü hesaplayan hızlı ve verimli bir algoritma bilinmemektedır. En naif algoritma, g sayısının, b sayısına ulaşılana dek kuvvetlendirimesi olarak tanımlanabilir. Bu süreç içerinde ulaşılan kuvvet k, ifadenin çözümü olacaktır. Bu algoritmaya çarpma işlemini kullanarak deneme yanılma yöntemi denir. Bu basit algoritmanın çalışma süresi, işlemin yapıldığı G grubunun büyüklüğü ile doğru orantılıdır. Dolayısı ile, çalışma süresi grubun büyüklüğünü ifade eden sayının basamak sayısı ile üstel ilişki içerisindedir. Buna karşın, tarafında keşfedilmiş, quantum bilgisayarlarda çalışan, polinom zamanlı, verimli bir algoritma bilinmektedir.
Daha karmaşık ve sofistike algoritmalar bilinmektedir. Bu algoritmalar genellikle, çarpanlara ayırma probleminin çözümünden esinlenmişlerdir. Doğal olarak, yukarıda bahsedilen algoritmadan daha verimli ve hızlı çalışmaktadırlar. Buna karşın hiçbiri, problemi çözememektedir. Bu algoritmaların bazıları söyledir:
- (Pollard'ın lambda algoritması olarak da bilinir)
Çarpanlara Ayırma ile Karşılatırma
İki problem birbirinden farklı olsa dahi, bazı benzerlikler taşımaktadır:
- iki problemin de çözümü zordur (sonucu verimli ve hızlı hesaplayan herhangi bir algoritma bilinmemektedir),
- iki problem için de quantum bilgisayarlar üzerinde verimli ve hızlı hesaplayan algoritmalar bilinmektedir,
- bir problemi çözen algoritma, diğerine uyarlanabilmektedir ve
- iki problemin de çözümünün de zor olması, kriptografik yapılarda kullanılmalarına sebep olmuştur.
Kriptografi
Grup kuramında, ayrık logaritmanın hesaplanmasının zor olduğu gruplar mevcuttur. Bazı gruplarda, (ör: yüksek mertebeleri asal kuvvetli alt gruplar (Zp)×) en kötü durumlar için ayrık logaritma hesaplayan verimli algoritmalar bulunamamıştır. Ek olarak, işlemin ortalama karmaşıklığı'nın problemi kadar zor olduğu gösterilebilmiştir.
Aynı zamanda, ayrık logaritma probleminin tersinin, yani ayrık kuvvet alma işleminin kolay olduğu, yöntemi ile verimli bir şekilde gösterilmiştir. Bu iki işlem arasındaki asimetri, tam sayılar kümesindeki çarpanlara ayırma ve çarpma işlemi arasındaki bağıntıya benzer. Bu bağıntı, kriptografik yapıtaşlarının oluşturulmasında kullanılmaktadır.
Genel olarak, ayrık logaritma problemi, kriptografide döngüsel sonlu gruplarda uygulanır (Zp)×. Örnek olarak, ElGamal, Diffie-Hellman ve Dijital imza verilebilir.
Yeni nesil kriptografi uygulamaları, ayrık logaritma problemini, sonlu cisimler üzerinde kurulan ellipsel eğrilerin döngüsel alt grupları üzerinde uygulamaktadır. bkz
Kaynakça
- ; . Chapter 5, Prime Numbers: A computational perspective, 2nd ed., Springer.
- Stinson, Douglas Robert (2006), Cryptography: Theory and Practice (3.3 isbn=978-1-58488-508-5 bas.), Londra: CRC Press
wikipedia, wiki, viki, vikipedia, oku, kitap, kütüphane, kütübhane, ara, ara bul, bul, herşey, ne arasanız burada,hikayeler, makale, kitaplar, öğren, wiki, bilgi, tarih, yukle, izle, telefon için, turk, türk, türkçe, turkce, nasıl yapılır, ne demek, nasıl, yapmak, yapılır, indir, ücretsiz, ücretsiz indir, bedava, bedava indir, mp3, video, mp4, 3gp, jpg, jpeg, gif, png, resim, müzik, şarkı, film, film, oyun, oyunlar, mobil, cep telefonu, telefon, android, ios, apple, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, pc, web, computer, bilgisayar
Matematikte ozellikle soyut cebir ve uygulamalarinda ayrik logaritma genel logaritmanin grup kuramindaki karsiligidir Genel olarak bakildiginda loga b ifadesi ax b ifadesinin gercel sayilar kumesi icindeki cozumlerine karsilik gelir Benzer olarak g ve h sonlu devirli grup G nin elemanlari oldugunda gx h ifadesinin cozumu olan x sonuclarina h nin g tabanindaki ayrik logaritmasi denir OrneklerAyrik logaritmalar muhtemelen en kolay anlasilabilirler Bu kume 1 p 1 ihtiva eder ve asal sayi p modunda carpmaya gore kapalidir Bu kumede bir elemanin k inci kuvvetini bulmak istiyorsak tam sayilar kumesinde sayinin k inci kuvvetini alir ardindan mod p de sadelestiririp kalani buluruz Kalan aradigimiz k inci kuvveti verecektir Bu isleme ayrik kuvvet alma islemi denir Ornegin Z17 carpma grubunu ele alalim 34 ifadesini hesaplamak icin oncelikle 34 81 ifadesini hesaplariz Ardindan 81 i 17 ye bolerek kalan olan 13 e ulasiriz Sonuc olarak Z17 grubunda 34 13 tur Ayrik logaritma yukarida bahsedilen kuvvet alma isleminin tersidir Ornegin 3k 13 mod 17 denklenmini k degiskeni icin cozmeye calisalim Yukarida da yazdigi gibi k 4 gecerli bir cevaptir Buna karsin tek cevap degildir Ornegin 316 1 mod 17 oldugundan n tam sayi olmak kaydiyla tum cozumler 34 16 n 13 1n 13 mod 17 seklinde yazilabilir Bu baglamda 4 16n formunda sonsuz sayida cozum vardir Hatta 16 3m 1 mod 17 denklemini saglayan en kucuk sayi oldugundan tum cozumler bu sekildedir Benzer olarak cozum kumesi k 4 mod 16 seklinde de ifade edilebilir TanimG n elemanli sonlu bir olsun Burada grubun carpma gosteriminde oldugunu varsayalim g bahsi gecen grubun herhangi bir ureteci olsun Bu durumda G grubunun tum elemanlari g nin bir kuvveti olarak yazilabilir or b gk Burada b g nin k inci kuvvetidir diyebiliriz logg G Zn displaystyle log g colon G rightarrow mathbb Z n burada Zn n modundaki tam sayilarin halkasini ifade etmektedir Burada G grubundaki her b sayisi k tam sayisini isaret etmektedir Bu isaret eden fonksiyon bir grup isomorfizmasi olup g bazinda ayrik logaritma islevi olarak isimlendirilir Genel logratima icin gecerli olan baz degistirme islemi burada da calismaktadir Ornegin h G grubunun diger bir ureteci olsun Baz degistirme islemi asagidaki gibi uygulanabilir logh b logh g logg b displaystyle log h b log h g cdot log g b AlgoritmalarAyrik logaritma problemi loggb nin genel cozumunu hesaplayan hizli ve verimli bir algoritma bilinmemektedir En naif algoritma g sayisinin b sayisina ulasilana dek kuvvetlendirimesi olarak tanimlanabilir Bu surec icerinde ulasilan kuvvet k ifadenin cozumu olacaktir Bu algoritmaya carpma islemini kullanarak deneme yanilma yontemi denir Bu basit algoritmanin calisma suresi islemin yapildigi G grubunun buyuklugu ile dogru orantilidir Dolayisi ile calisma suresi grubun buyuklugunu ifade eden sayinin basamak sayisi ile ustel iliski icerisindedir Buna karsin tarafinda kesfedilmis quantum bilgisayarlarda calisan polinom zamanli verimli bir algoritma bilinmektedir Daha karmasik ve sofistike algoritmalar bilinmektedir Bu algoritmalar genellikle carpanlara ayirma probleminin cozumunden esinlenmislerdir Dogal olarak yukarida bahsedilen algoritmadan daha verimli ve hizli calismaktadirlar Buna karsin hicbiri problemi cozememektedir Bu algoritmalarin bazilari soyledir Pollard in lambda algoritmasi olarak da bilinir Carpanlara Ayirma ile KarsilatirmaIki problem birbirinden farkli olsa dahi bazi benzerlikler tasimaktadir iki problemin de cozumu zordur sonucu verimli ve hizli hesaplayan herhangi bir algoritma bilinmemektedir iki problem icin de quantum bilgisayarlar uzerinde verimli ve hizli hesaplayan algoritmalar bilinmektedir bir problemi cozen algoritma digerine uyarlanabilmektedir ve iki problemin de cozumunun de zor olmasi kriptografik yapilarda kullanilmalarina sebep olmustur KriptografiGrup kuraminda ayrik logaritmanin hesaplanmasinin zor oldugu gruplar mevcuttur Bazi gruplarda or yuksek mertebeleri asal kuvvetli alt gruplar Zp en kotu durumlar icin ayrik logaritma hesaplayan verimli algoritmalar bulunamamistir Ek olarak islemin ortalama karmasikligi nin problemi kadar zor oldugu gosterilebilmistir Ayni zamanda ayrik logaritma probleminin tersinin yani ayrik kuvvet alma isleminin kolay oldugu yontemi ile verimli bir sekilde gosterilmistir Bu iki islem arasindaki asimetri tam sayilar kumesindeki carpanlara ayirma ve carpma islemi arasindaki bagintiya benzer Bu baginti kriptografik yapitaslarinin olusturulmasinda kullanilmaktadir Genel olarak ayrik logaritma problemi kriptografide dongusel sonlu gruplarda uygulanir Zp Ornek olarak ElGamal Diffie Hellman ve Dijital imza verilebilir Yeni nesil kriptografi uygulamalari ayrik logaritma problemini sonlu cisimler uzerinde kurulan ellipsel egrilerin dongusel alt gruplari uzerinde uygulamaktadir bkzKaynakca Shor Peter 1997 Polynomial Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer SIAM Journal on Computing 26 5 ss 1484 1509 arXiv quant ph 9508027 2 Chapter 5 Prime Numbers A computational perspective 2nd ed Springer Stinson Douglas Robert 2006 Cryptography Theory and Practice 3 3 isbn 978 1 58488 508 5 bas Londra CRC Press KB1 bakim Dikey cizgi eksik link