Tekst źródłowy strony Logarytm dyskretny

'''[[Logarytm]] dyskretny''' elementu <math>b</math> przy podstawie <math>a</math> w danej [[grupa (matematyka)|grupie]] skończonej – [[Liczby całkowite|liczba całkowita]] <math>c,</math> dla której zachodzi równość (w [[notacja|notacji]] multiplikatywnej):
: <math>a^c = b.</math>

Logarytm dyskretny nie zawsze istnieje, a jeśli istnieje, może nie być jednoznaczny. Np. w [[ciało skończone|ciele skończonym]] <math>\mathbb Z_{11}</math> logarytmem przy podstawie 4 z elementu 9 jest liczba 3 (ale też 8). W tym ciele nie istnieje logarytm przy podstawie 4 z elementu 7.

Znalezienie logarytmu dyskretnego jest zaskakująco trudnym problemem. O ile potęgowanie wymaga <math>O\left(\log c\right)</math> operacji – liczymy <math>a, a^2, a^4, a^8, \dots,</math> po czym wymnażamy te z nich, dla których bity c są równe 1, to jedyną ''prostą'' metodą rozwiązywania problemu logarytmu dyskretnego jest przeszukanie '''wszystkich''' możliwych <math>c.</math> Istnieją efektywniejsze metody, jednak żadna z ogólnych metod nie ma złożoności wielomianowej wobec ilości bitów wejścia (istnieją takie dla pewnych specyficznych klas [[Liczby pierwsze|liczb pierwszych]], których należy więc w kryptografii unikać). Najszybszy algorytm (sito [[Ciało liczbowe|ciała liczbowego]]) obliczania logarytmu dyskretnego w [[ciało skończone|'''GF('''p''')''']] ma złożoność czasową:
: <math>e^{c\cdot\log^{\frac{1}{3}}_2(p) \cdot \log^{\frac{2}{3}}_2\left(\log_2(p)\right)},</math>

gdzie ''c'' jest pewną stałą. Jedną z metod obliczania logarytmu dyskretnego w [[ciało skończone|'''GF('''p''')''']] jest [[redukcja Pohliga-Hellmana]].

Trudność znalezienia logarytmu dyskretnego jest podstawą istnienia wielu [[algorytm]]ów [[Kryptologia|kryptograficznych]], takich jak [[ElGamal]] i [[protokół Diffiego-Hellmana]] czy kryptografia oparta na [[Krzywa eliptyczna|krzywych eliptycznych]].

== Zobacz też ==
* [[schemat identyfikacji Schnorra]]

== Linki zewnętrzne ==
* {{MathWorld | adres = DiscreteLogarithm | tytuł = Discrete Logarithm }} [dostęp 2024-02-02].
* {{otwarty dostęp}} ''[https://encyclopediaofmath.org/index.php?title=Discrete_logarithm&redirect=no Discrete logarithm]'' {{lang|en}}, Encyclopedia of Mathematics, encyclopediaofmath.org [dostęp 2024-02-02].

{{Logarytmy}}

{{Kontrola autorytatywna}}

[[Kategoria:Logarytmy]]
[[Kategoria:Teoria grup skończonych]]
[[Kategoria:Ciała skończone]]
[[Kategoria:Kryptologia]]