Ayrık logaritma. Ayrık logaritma

Örnek 13.13

Hangi n değeri için grubun ilkel kökleri vardır: 17, 20, 38 ve 50?

Çözüm

A. 17 bir asal sayı olduğundan (pt t, t 1'dir) ilkel köklere sahiptir.

B. ilkel kökleri yoktur.

C. ve 19 bir asal sayıdır.

D. ilkel kökleri var çünkü ve 5 bir asal sayıdır.

Bir grubun ilkel bir kökü varsa, genellikle bu tür birkaç kökü vardır. İlkel köklerin sayısı - olarak hesaplanabilir. Örneğin, ilkel köklerin sayısı - Bu - . Kök sayısını bulmadan önce grubun herhangi bir ilkel köke sahip olup olmadığını kontrol etmeniz gerektiğini lütfen unutmayın.

Eğer grup G =< Z N* , x > en az bir temel köke sahipse, bu durumda ilkel köklerin sayısı ((n)) olur

Üç soruyu ele alalım:

1. Bir a elementi ve bir grup verildiğinde, a'nın G'nin ilkel kökü olup olmadığı nasıl belirlenebilir? Bu o kadar kolay bir iş değil.

A. Bu görevin karmaşıklığı açısından n sayısını çarpanlara ayırma görevine benzer olduğunu bulmalıyız.

B. Bulmalıyız .

2. Bir grup verildiğinde tüm ilkel kökler nasıl bulunur? Bu problem ilk problemden daha zordur çünkü adım 1.b'deki hesaplamaları tüm grup için tekrarlamamız gerekir.

3. Bir grup verilmişse, ilkel kök G nasıl seçilir? Kriptografide bir grupta en az bir ilkel kök bulmalıyız. Ancak bu durumda n değeri kullanıcı tarafından seçilir ve kullanıcı bilir. Kullanıcı, ilkini bulana kadar birkaç öğeyi art arda dener.

Döngüsel grup. Döngüsel gruplar zaten 5-6. derslerde tartışılmıştı. Bir grubun ilkel kökleri varsa, bunların döngüsel olarak tekrarlandığını lütfen unutmayın. Her ilkel kök bir oluşturucudur ve bütün bir kümeyi oluşturmak için kullanılabilir. Başka bir deyişle, eğer g bir grupta ilkel bir kök ise, Zn* kümesini şu şekilde üretebiliriz:

Örnek 13.14

Grup iki ilkel kökü vardır, çünkü ve . İlkel kökleri bulabilirsiniz - bunlar 3 ve 7'dir. Aşağıda, her bir ilkel kökü kullanarak tam bir Z 10* kümesini nasıl oluşturabileceğiniz açıklanmaktadır.

g = 3 -> g 1 mod 10 = 3 g 2 mod 10 = 9 g 3 mod 10 = 7 g 4 mod 10 = 1 g = 7 -> g 1 mod 10 = 7 g 2 mod 10 = 9 g 3 mod 10 = 3 g 4 mod 10 = 1

Lütfen grubun p asal olduğundan her zaman döngüseldir.

Grup G =< Z n * , x >ilkel köklere sahipse döngüsel bir gruptur. Grup G =< Z p * , x >her zaman döngüseldir.

Ayrık logaritma fikri. Grup birçok ilginç özelliğe sahiptir.

Ayrık logaritmalar kullanarak modüler logaritmayı çözme

Şimdi y = a x (mod n) gibi problemlerin nasıl çözüldüğüne bakalım, yani y verildiğinde ve x'i bulmamız gerekiyor.

Ayrık logaritmaların tablolaştırılması. Yukarıdaki sorunu çözmenin bir yolu, her Z p* ve çeşitli tabanlar için bir tablo kullanmaktır. Bu tür bir tablo önceden hesaplanabilir ve kaydedilebilir. Örneğin Tablo 13.4'te değerler gösterilmektedir ayrık logaritma Z 7* için. Bu kümede iki ilkel kökümüz veya bazımız olduğunu biliyoruz.

Tablo 13.4. Ayrık logaritma G için =

sen	1	2	3	4	5	6
x = L 3 y	6	2	1	4	5	3
x = L 5 y	6	4	5	2	1	3

Başkaları için masa hazırlamak ayrık logaritmalar tüm gruplar ve tüm olası tabanlar için herhangi bir ayrık logaritmik problemi çözebiliriz. Bu yaklaşım geçmişte çalışılan geleneksel logaritmalara benzer. Hesap makineleri ve bilgisayarların ortaya çıkmasından önce, 10 tabanına göre logaritmaları hesaplamak için tablolar kullanılıyordu.

Örnek 13.15

Aşağıdaki durumların her birinde x'i bulun:

Tablo 13.4'ü rahatlıkla kullanabiliriz. ayrık logaritma.

EPFL ve Leipzig Üniversitesi'nden bir araştırmacı ekibi, bir asal sayı tabanına göre logaritmayı hesaplamayı başardı. 768 bit. Bunu yapabilmek için Şubat 2015'ten bu yana 200 çekirdeğe ve zamana ihtiyaçları vardı. Dijital eleğin bir çeşidini kullandılar. Dolayısıyla logaritma, sıradan sayıların kaydının da 768 bit olduğu çarpanlara ayırmaya eşittir.

Bu arada, yarınki güncellemeden sonra dyndns ana bilgisayarlarına ücretsiz TLS eklemek mümkün olacak! Bu çok güzel, artık tüm hamsterlerin sertifikaları olacak.

Yan kanal saldırılarına karşı koruma

Günümüzde şifreleme anahtarları hakkındaki bilgilerin neredeyse bir fan aracılığıyla uzaktan elde edilebileceği bir sır değil. Bu nedenle girdi verilerine bağlı olmayan sabit zamanlı algoritmalar giderek daha popüler hale geliyor. Almanlar, veri yan kanalları yoluyla hassas verilerin elde edilmesini zorlaştıracak uygulamalar için minimum gereksinimleri yayınladı. , okumanızı tavsiye ederim.

Benim için bu kadar, bir dahaki sefere görüşürüz!

Yani iki gücümüz var. Alt satırdaki sayıyı alırsanız, bu sayıyı elde etmek için ikiyi yükseltmeniz gereken gücü kolayca bulabilirsiniz. Örneğin, 16 elde etmek için ikinin dördüncü kuvvetini yükseltmeniz gerekir. Ve 64'ü elde etmek için ikinin altıncı kuvvetini artırmanız gerekiyor. Bu tablodan görülebilmektedir.

Ve şimdi - aslında logaritmanın tanımı:

x'in logaritması tabanı, x'i elde etmek için a'nın yükseltilmesi gereken kuvvettir.

Tanım: log a x = b, burada a tabandır, x argümandır, b ise logaritmanın gerçekte eşit olduğu şeydir.

Örneğin, 2 3 = 8 ⇒ log 2 8 = 3 (2 3 = 8 olduğundan 8'in 2 tabanlı logaritması üçtür). Aynı başarı günlüğü ile 2 64 = 6, çünkü 2 6 = 64.

Bir sayının belirli bir tabana göre logaritmasını bulma işlemine logaritma denir. Şimdi tablomuza yeni bir satır ekleyelim:

2 1	2 2	2 3	2 4	2 5	2 6
2	4	8	16	32	64
günlük 2 2 = 1	günlük 2 4 = 2	günlük 2 8 = 3	günlük 2 16 = 4	günlük 2 32 = 5	günlük 2 64 = 6

Ne yazık ki tüm logaritmalar bu kadar kolay hesaplanamıyor. Örneğin, log 2 5'i bulmayı deneyin. Tabloda 5 sayısı yok ama mantık, logaritmanın parça üzerinde bir yerde olacağını söylüyor. Çünkü 2 2< 5 < 2 3 , а чем больше степень двойки, тем больше получится число.

Bu tür sayılara irrasyonel denir: Ondalık noktadan sonraki sayılar sonsuza kadar yazılabilir ve asla tekrarlanmaz. Logaritmanın irrasyonel olduğu ortaya çıkarsa, onu bu şekilde bırakmak daha iyidir: log 2 5, log 3 8, log 5 100.

Logaritmanın iki değişkenli (taban ve argüman) bir ifade olduğunu anlamak önemlidir. İlk başta birçok kişi temelin nerede olduğunu ve argümanın nerede olduğunu karıştırır. Can sıkıcı yanlış anlamaları önlemek için resme bakın:

Önümüzde bir logaritmanın tanımından başka bir şey yok. Hatırlamak: logaritma bir kuvvettir Bir argüman elde etmek için tabanın içine inşa edilmesi gerekir. Bir güce yükseltilen tabandır - resimde kırmızıyla vurgulanmıştır. Tabanın her zaman altta olduğu ortaya çıktı! Öğrencilerime bu harika kuralı daha ilk derste anlatıyorum ve hiçbir kafa karışıklığı ortaya çıkmıyor.

Tanımı çözdük; geriye kalan tek şey logaritmanın nasıl sayılacağını öğrenmek. "log" işaretinden kurtulun. Başlangıç olarak, tanımdan iki önemli gerçeğin çıktığını not ediyoruz:

Argüman ve taban her zaman sıfırdan büyük olmalıdır. Bu, bir derecenin rasyonel bir üsle tanımlanmasından kaynaklanır ve logaritmanın tanımı buna indirgenir.
Taban birden farklı olmalıdır, çünkü bir dereceye kadar bir hala bir olarak kalır. Bu nedenle “iki elde etmek için kişinin hangi güce yükseltilmesi gerekir” sorusu anlamsızdır. Böyle bir derece yok!

Bu tür kısıtlamalara denir kabul edilebilir değerler aralığı(ODZ). Logaritmanın ODZ'sinin şu şekilde göründüğü ortaya çıktı: log a x = b ⇒ x > 0, a > 0, a ≠ 1.

b sayısı (logaritmanın değeri) üzerinde herhangi bir kısıtlama olmadığını unutmayın. Örneğin logaritma negatif olabilir: log 2 0,5 = −1, çünkü 0,5 = 2 −1.

Ancak şimdi yalnızca logaritmanın VA'sını bilmenin gerekli olmadığı sayısal ifadeleri ele alıyoruz. Sorunların yazarları tarafından tüm kısıtlamalar zaten dikkate alınmıştır. Ancak logaritmik denklemler ve eşitsizlikler devreye girdiğinde DL gereklilikleri zorunlu hale gelecektir. Sonuçta, temel ve argüman, yukarıdaki kısıtlamalara tam olarak uymayan çok güçlü yapılar içerebilir.

Şimdi logaritmaları hesaplamak için genel şemaya bakalım. Üç adımdan oluşur:

A tabanını ve x argümanını, mümkün olan minimum tabanı birden büyük olacak şekilde bir kuvvet olarak ifade edin. Bu arada ondalık sayılardan kurtulmak daha iyidir;
b değişkeninin denklemini çözün: x = a b ;
Ortaya çıkan b sayısı cevap olacaktır.

İşte bu! Logaritmanın irrasyonel olduğu ortaya çıkarsa, bu zaten ilk adımda görülecektir. Tabanın birden büyük olması gerekliliği çok önemlidir: bu, hata olasılığını azaltır ve hesaplamaları büyük ölçüde basitleştirir. Ondalık kesirlerde de durum aynıdır: Bunları hemen sıradan kesirlere dönüştürürseniz, çok daha az hata olacaktır.

Belirli örnekleri kullanarak bu şemanın nasıl çalıştığını görelim:

Görev. Logaritmayı hesaplayın: log 5 25

Tabanı ve argümanı beşin kuvveti olarak düşünelim: 5 = 5 1; 25 = 52;

Denklemi oluşturup çözelim:
log 5 25 = b ⇒ (5 1) b = 5 2 ⇒ 5 b = 5 2 ⇒ b = 2 ;

Cevabını aldık: 2.

Görev. Logaritmayı hesaplayın:

Görev. Logaritmayı hesaplayın: log 4 64

Tabanı ve argümanı ikinin kuvveti olarak düşünelim: 4 = 2 2; 64 = 26;
Denklemi oluşturup çözelim:
log 4 64 = b ⇒ (2 2) b = 2 6 ⇒ 2 2b = 2 6 ⇒ 2b = 6 ⇒ b = 3 ;
Cevabını aldık: 3.

Görev. Logaritmayı hesaplayın: log 16 1

Tabanı ve argümanı ikinin kuvveti olarak düşünelim: 16 = 2 4; 1 = 2 0;
Denklemi oluşturup çözelim:
log 16 1 = b ⇒ (2 4) b = 2 0 ⇒ 2 4b = 2 0 ⇒ 4b = 0 ⇒ b = 0 ;
Cevabını aldık: 0.

Görev. Logaritmayı hesaplayın: log 7 14

Tabanı ve argümanı yedinin kuvveti olarak düşünelim: 7 = 7 1; 7 1 olduğundan 14 yedinin kuvveti olarak temsil edilemez< 14 < 7 2 ;
Önceki paragraftan logaritmanın sayılmadığı anlaşılmaktadır;
Cevap değişiklik yok: log 7 14.

Son örnekle ilgili küçük bir not. Bir sayının başka bir sayının tam kuvveti olmadığından nasıl emin olabilirsiniz? Çok basit; bunu asal çarpanlara ayırmanız yeterli. Genişlemenin en az iki farklı faktörü varsa, sayı tam bir kuvvet değildir.

Görev. Sayıların tam kuvvetleri olup olmadığını öğrenin: 8; 48; 81; 35; 14.

8 = 2 · 2 · 2 = 2 3 - tam derece, çünkü yalnızca bir çarpan vardır;
48 = 6 · 8 = 3 · 2 · 2 · 2 · 2 = 3 · 2 4 - tam bir kuvvet değildir, çünkü iki çarpan vardır: 3 ve 2;
81 = 9 · 9 = 3 · 3 · 3 · 3 = 3 4 - tam derece;
35 = 7 · 5 - yine kesin bir kuvvet değil;
14 = 7 · 2 - yine kesin bir derece değil;

Ayrıca asal sayıların her zaman kendilerinin tam kuvvetleri olduğuna dikkat edin.

Ondalık logaritma

Bazı logaritmalar o kadar yaygındır ki özel bir isme ve sembole sahiptirler.

X'in ondalık logaritması, 10 tabanına göre logaritmasıdır; X sayısını elde etmek için 10 sayısının yükseltilmesi gereken kuvvet. Tanım: lg x.

Örneğin log 10 = 1; lg100 = 2; lg 1000 = 3 - vb.

Artık bir ders kitabında "lg 0.01'i bul" gibi bir ifade göründüğünde şunu bilin: bu bir yazım hatası değil. Bu bir ondalık logaritmadır. Ancak bu gösterime aşina değilseniz, istediğiniz zaman yeniden yazabilirsiniz:
günlük x = günlük 10 x

Sıradan logaritmalar için doğru olan her şey ondalık logaritmalar için de doğrudur.

Doğal logaritma

Kendi tanımı olan başka bir logaritma var. Bazı yönlerden ondalık sayıdan bile daha önemlidir. Doğal logaritmadan bahsediyoruz.

X'in doğal logaritması e tabanının logaritmasıdır, yani. x sayısını elde etmek için e sayısının yükseltilmesi gereken güç. Tanım: ln x .

Birçoğu şunu soracak: e sayısı nedir? Bu irrasyonel bir sayıdır; kesin değeri bulunup yazılamaz. Sadece ilk rakamları vereceğim:
e = 2,718281828459...

Bu sayının ne olduğu ve neden ihtiyaç duyulduğu konusunda detaya girmeyeceğiz. E'nin doğal logaritmanın tabanı olduğunu unutmayın:
ln x = log e x

Böylece ln e = 1; ln e 2 = 2; ln e 16 = 16 - vb. Öte yandan ln 2 irrasyonel bir sayıdır. Genel olarak herhangi bir rasyonel sayının doğal logaritması irrasyoneldir. Elbette birlik hariç: ln 1 = 0.

Doğal logaritmalar için sıradan logaritmalar için geçerli olan tüm kurallar geçerlidir.

Ayrık logaritma

Ayrık logaritma(DLOG) - işlevi tersine çevirme görevi G X bazı sonlu çarpımsal grupta G .

Çoğu zaman, disket logaritma problemi, kalıntı halkasının ters çevrilebilir elemanları grubunda, sonlu bir alanın çarpımsal grubunda veya sonlu bir alan üzerinde eliptik bir eğri üzerindeki noktalar grubunda dikkate alınır. Disket logaritma problemini çözmek için etkili algoritmalar genellikle bilinmemektedir.

verilen için G Ve Açözüm X denklemler G X = A isminde ayrık logaritma eleman A dayalı G. Durumunda G kalıntı halka modulosunun ters çevrilebilir elemanlarının grubudur Mçözüme de denir indeks sayılar A dayalı G. Sayı dizini A dayalı G eğer varolması garanti edilir G ilkel bir kök modulodur M.

Ayrık logaritma probleminin çözümü negatif olmayan bir tam sayı bulmaktır. X, tatmin edici denklem (1). Çözülebilirse grubun mertebesini aşmayan en az bir doğal çözümü olmalıdır. Bu, yukarıdan çözüm bulmaya yönelik algoritmanın karmaşıklığı hakkında hemen kaba bir tahmin verir; kapsamlı bir arama algoritması, verilen grubun düzeyinden daha yüksek olmayan birkaç adımda bir çözüm bulacaktır.

Çoğu zaman bu durum, yani grubun eleman tarafından döngüsel olarak oluşturulduğu durumlarda dikkate alınır. G. Bu durumda denklemin her zaman bir çözümü vardır. Keyfi bir grup durumunda, ayrık logaritma probleminin çözülebilirliği sorunu, yani denklem (1)'in çözümlerinin varlığı sorunu ayrı bir değerlendirme gerektirir.

Örnek

En kolay yol, kalıntı halka modulosundaki ayrık logaritma problemini bir asal sayı olarak düşünmektir.

Karşılaştırmanın verilmesine izin verin

Sorunu kaba kuvvet yöntemini kullanarak çözeceğiz. 3 sayısının tüm kuvvetlerini gösteren bir tablo yazalım. Her seferinde 17'ye bölümün geri kalanını hesaplıyoruz (örneğin, 3 3 ≡27 - 17'ye bölümün geri kalanı 10'dur).

3 1 ≡ 3	3 2 ≡ 9	3 3 ≡ 10	3 4 ≡ 13	3 5 ≡ 5	3 6 ≡ 15	3 7 ≡ 11	3 8 ≡ 16
3 9 ≡ 14	3 10 ≡ 8	3 11 ≡ 7	3 12 ≡ 4	3 13 ≡ 12	3 14 ≡ 2	3 15 ≡ 6	3 16 ≡ 1

Artık söz konusu karşılaştırmanın çözümünün şu olduğunu görmek kolaydır: x=4, 3 4 ≡13'ten beri.

Uygulamada modül genellikle kaba kuvvet yönteminin çok yavaş olmasına yetecek kadar büyük bir sayıdır, dolayısıyla daha hızlı algoritmalara ihtiyaç vardır.

Çözüm algoritmaları

Rasgele bir çarpımsal grupta

Makale, keyfi sonlu bir Abel grubundaki ayrık logaritma probleminin çözülebilirliğine ve çözümüne ayrılmıştır. BuchmannJ., Jacobson M.J., Teske E. Sonlu değişmeli gruplardaki bazı hesaplama problemleri üzerine. Algoritma, öğe çiftlerinden oluşan bir tablo kullanır ve çarpma işlemlerini gerçekleştirir. Bu algoritma yavaştır ve pratik kullanıma uygun değildir. Belirli grupların kendilerine ait, daha etkili algoritmaları vardır.

Ayrık bir logaritma hesaplama problemini verimli bir şekilde çözmenin bir başka olasılığı kuantum hesaplamayı içerir. Bunları kullanarak ayrık logaritmanın polinom zamanında hesaplanabileceği teorik olarak kanıtlanmıştır. Her durumda, ayrık logaritmayı hesaplamak için polinom algoritması uygulanırsa, bu, buna dayalı şifreleme sistemlerinin pratik olarak uygun olmadığı anlamına gelecektir.

Ayrık logaritma probleminin karmaşıklığına dayanan klasik şifreleme şemaları, Diffie-Hellman genel anahtar oluşturma şeması, El-Gamal elektronik imza şeması ve mesaj iletimi için Massey-Omura şifreleme sistemidir.

Bağlantılar

Vasilenko O. N. Kriptografide Sayı Teorik Algoritmaları. - Moskova: MTsNMO, 2003. - 328 s. - ISBN 5-94057-103-4
Koblitz N. Sayı teorisi ve kriptografi dersi. - Moskova: TVPb, 2001. - 254 s. - ISBN 5-85484-014-6
Odlyzko A.M. Sonlu alanlarda ayrık logaritmalar ve bunların kriptografik önemi // LNC'ler. - 1984. - T. 209. - S. 224-316.
Buchmann J., Jacobson M.J., Teske E. Sonlu değişmeli gruplardaki bazı hesaplama problemleri üzerine // Hesaplama Matematiği. - 1997. - T. 66. - No. 220. - S. 1663-1687.
Makale Scientific Network web sitesinde ayrık logaritma
Ayrık logaritmaların hesaplanmasına yönelik yöntemlerin gözden geçirilmesi (İngilizce)
Nechaev V.I. Ayrık bir logaritma için deterministik bir algoritmanın karmaşıklığı sorusu üzerine // Matematik Notları. - 1994. - V. 2. - T. 55. - S. 91-101.

Wikimedia Vakfı.

2010.

Diğer sözlüklerde “Ayrık logaritma”nın ne olduğuna bakın: ayrık logaritma - Grupta iki element d vardır; g, gr = d koşulunu karşılayan bir r tamsayısı olacak şekildedir; r'ye d'nin g tabanına ayrık logaritması denir.

Genel olarak bilgi teknolojisi konuları TR ayrık logaritma ...

Teknik Çevirmen Kılavuzu

Polig'in Hellman algoritması (Silver Polig'in Hellman algoritması olarak da bilinir), bir asal sayı modulo kalıntı halkasında deterministik bir ayrık logaritma algoritmasıdır. Algoritmanın özelliklerinden biri de... ... Vikipedi

1 Planı:
giriiş
3 Çözüm algoritmaları
- 3.1 Rasgele bir çarpımsal grupta
- 3.2 Sorunun beyanı
  - 3.2.1 2 Örnek
  - 3.2.2 Kalıntılar halkasında modulo prime
- 3.3 Üstel karmaşıklığa sahip algoritmalar
- 3.4 Alt üstel algoritmalar
4 Keyfi bir sonlu alanda

Eliptik bir eğri üzerindeki bir grup noktada

Ayrık logaritma(DLOG) - işlevi tersine çevirme görevi G X bazı sonlu çarpımsal grupta G .

Kriptografide hesaplama karmaşıklığı ve uygulamaları

verilen için G Ve Açözüm X denklemler G X = A isminde ayrık logaritma eleman A dayalı G. Durumunda G giriiş Mçözüme de denir indeks sayılar A dayalı G. Sayı dizini A dayalı G eğer varolması garanti edilir G ilkel bir kök modulodur M.

Çoğu zaman, ayrık logaritma problemi, bir kalıntı halkasının veya sonlu bir alanın çarpımsal grubunda ve ayrıca sonlu bir alan üzerindeki eliptik bir eğrinin nokta grubunda dikkate alınır. Ayrık logaritma problemini çözmek için etkili algoritmalar genellikle bilinmemektedir.

kalıntı halka modulosunun çarpımsal grubudur G 1. Sorunun beyanı

2. Örnek

En kolay yol, kalıntı halka modulosundaki ayrık logaritma problemini bir asal sayı olarak düşünmektir.

Karşılaştırmanın verilmesine izin verin

Artık söz konusu karşılaştırmanın çözümünün şu olduğunu görmek kolaydır: x=4, 3 4 ≡13'ten beri.

Uygulamada modül genellikle kaba kuvvet yönteminin çok yavaş olmasına yetecek kadar büyük bir sayıdır, dolayısıyla daha hızlı algoritmalara ihtiyaç vardır.

3. Çözüm algoritmaları

3.1. Rasgele bir çarpımsal grupta

J. Buchmann, M. J. Jacobson ve E. Teske'nin makalesi, keyfi sonlu bir Abel grubundaki ayrık logaritma probleminin çözülebilirliğine ve çözümüne ayrılmıştır. Algoritma, öğe çiftlerinden oluşan bir tablo kullanır ve çarpma işlemlerini gerçekleştirir. Bu algoritma yavaştır ve pratik kullanıma uygun değildir. Belirli grupların kendilerine ait, daha etkili algoritmaları vardır.

3.2. Kalıntılar halkasında modulo prime

Denklemi düşünün

Nerede P- basit, B bölünemez P. Eğer A grubun üretici bir elemanıysa, denklem (2)'nin herhangi bir çözüme sahip olduğu B. Bu tür sayılar A aynı zamanda ilkel kökler olarak da adlandırılır ve sayıları φ('ye eşittir. P− 1) , burada φ Euler fonksiyonudur. Denklemin (2) çözümü aşağıdaki formül kullanılarak bulunabilir:

Ancak bu formülü hesaplamanın karmaşıklığı, numaralandırmanın karmaşıklığından daha kötüdür.

Aşağıdaki algoritmanın karmaşıklığı var

Algoritma

Algoritmanın sonu

Kalıntı alanında ayrık logaritma problemini çözmek için başka birçok algoritma da vardır. Genellikle üstel ve alt üstel olarak ayrılırlar. Bu problemi çözecek bir polinom algoritması henüz mevcut değildir.

3.2.1. Üstel karmaşıklığa sahip algoritmalar

3.2.2. Alt üstel algoritmalar

Bu algoritmalar, ve'nin bazı sabitler olduğu aritmetik işlemlerin karmaşıklığına sahiptir. Algoritmanın etkinliği büyük ölçüde yakınlığa bağlıdır. C 1'e ve D- 0'a.

Şu anda karmaşıklığı değerlendirmek için en iyi parametreler , .

Özel türdeki sayılar için sonuç iyileştirilebilir. Bazı durumlarda sabitlerin , olacağı bir algoritma oluşturmak mümkündür. Çünkü sürekli C 1'e yeterince yakınsa, benzer algoritmalar .

3.3. Keyfi bir sonlu alanda

Sorun sahada değerlendiriliyor GF(q), Nerede Q = P N , P- basit.

3.4. Eliptik bir eğri üzerindeki bir grup noktada

Sonlu bir alan üzerinde eliptik bir eğrinin bir grup noktasını ele alıyoruz. Bu grup iki noktanın eklenmesi işlemini tanımlar. Daha sonra MP- Bu . Eliptik bir eğri üzerindeki ayrık logaritma probleminin çözümü böyle bir doğal sayı bulmaktır. M, Ne

verilen puanlar için P Ve A.

1990 yılına kadar eliptik bir eğri üzerindeki bir grup noktanın yapısal özelliklerini hesaba katan ayrık logaritma algoritmaları yoktu. Daha sonra Alfred J. Menezes, Tatsuaki Okamoto ve Scott A. Vanstone, Weyl eşleştirmesini kullanan bir algoritma önerdiler. Bir alan üzerinde tanımlanan eliptik bir eğri için GF(Q), bu algoritma ayrık logaritma problemini alandaki benzer bir probleme indirger. GF(Q k) . Bununla birlikte, bu bilgi yalnızca derecenin olması durumunda faydalıdır. k küçük Bu koşul esas olarak tekil olmayan eliptik eğriler için karşılanır. Diğer durumlarda, böyle bir azalma neredeyse hiçbir zaman alt üstel algoritmalara yol açmaz.

4. Hesaplama karmaşıklığı ve kriptografideki uygulamalar

Ayrık logaritma problemi, açık anahtar kriptografisinin dayandığı temel problemlerden biridir. Bu tür sistemlerin ardındaki fikir, belirli sayısal fonksiyonların tersine çevrilmesinin yüksek hesaplama karmaşıklığına dayanır. Bu durumda ayrık logaritma işlemi üstel fonksiyonun tersidir. İkincisi oldukça basit bir şekilde hesaplanırken, ayrık logaritmayı hesaplamak için kullanılan en modern algoritmalar bile çok yüksek bir karmaşıklığa sahiptir; bu, sayıları çarpanlara ayırmaya yönelik en hızlı algoritmaların karmaşıklığıyla karşılaştırılabilir.

Ayrık logaritmanın hesaplanması sorununu etkili bir şekilde çözmenin bir başka olasılığı kuantum hesaplamayla ilgilidir. Bunları kullanarak ayrık logaritmanın polinom zamanında hesaplanabileceği teorik olarak kanıtlanmıştır. Her durumda, ayrık logaritmayı hesaplamak için polinom algoritması uygulanırsa, bu, buna dayalı şifreleme sistemlerinin pratik olarak uygun olmadığı anlamına gelecektir.