Logarytm dyskretny
Logarytm dyskretny elementu przy podstawie w danej grupie skończonej – liczba całkowita dla której zachodzi równość (w notacji multiplikatywnej):
Logarytm dyskretny nie zawsze istnieje, a jeśli istnieje, może nie być jednoznaczny. Np. w ciele skończonym 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 operacji – liczymy 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 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 liczb pierwszych, których należy więc w kryptografii unikać). Najszybszy algorytm (sito ciała liczbowego) obliczania logarytmu dyskretnego w GF(p) ma złożoność czasową:
gdzie c jest pewną stałą. Jedną z metod obliczania logarytmu dyskretnego w GF(p) jest redukcja Pohliga-Hellmana.
Trudność znalezienia logarytmu dyskretnego jest podstawą istnienia wielu algorytmów kryptograficznych, takich jak ElGamal i protokół Diffiego-Hellmana czy kryptografia oparta na krzywych eliptycznych.
Zobacz też
- schemat identyfikacji Schnorra
Linki zewnętrzne
- Eric W.E.W. Weisstein Eric W.E.W., Discrete Logarithm, [w:] MathWorld, Wolfram Research (ang.). [dostęp 2024-02-02].
- Discrete logarithm (ang.), Encyclopedia of Mathematics, encyclopediaofmath.org [dostęp 2024-02-02].
- p
- d
- e
pojęcia definiujące |
|
---|---|
funkcje logarytmiczne | |
powiązane funkcje |
|
inne pojęcia | |
uczeni |
- БРЭ: 2008259