Logarytm dyskretny

Logarytm dyskretny elementu ${\displaystyle b}$ przy podstawie ${\displaystyle a}$ w danej grupie skończonej – liczba całkowita ${\displaystyle c,}$ dla której zachodzi równość (w notacji multiplikatywnej):

${\displaystyle a^{c}=b.}$

Logarytm dyskretny nie zawsze istnieje, a jeśli istnieje, może nie być jednoznaczny. Np. w ciele skończonym ${\displaystyle \mathbb {Z} _{11}}$ 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 ${\displaystyle O\left(\log c\right)}$ operacji – liczymy ${\displaystyle a,a^{2},a^{4},a^{8},\dots ,}$ 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 ${\displaystyle c.}$ 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ą:

${\displaystyle e^{c\cdot \log _{2}^{\frac {1}{3}}(p)\cdot \log _{2}^{\frac {2}{3}}\left(\log _{2}(p)\right)},}$

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