Logarytm dyskretny

Wpisz parametry i zobacz, jak algorytm Shanksa prowadzi krok po kroku do wyniku.
Przejdź do kalkulatora
Rozwiązujemy:

Kalkulator

Wprowadź parametry i przejdź przez obliczenia krok po kroku.

Kalkulator logarytmu dyskretnego (Baby-step Giant-step)

Rozwiązujemy równanie:

BigInt • krok po kroku
Zapis problemu dla podanych wartości
Wpisz dane i uruchom obliczenia
Po obliczeniu pokażę prekomputację baby steps, potem giant steps i dopasowanie prowadzące do wyniku.

Teoria

Czym jest logarytm dyskretny i dlaczego jest ważny?

Problem logarytmu dyskretnego

Logarytm dyskretny to „odwrotność” potęgowania w arytmetyce modularnej. Interesuje nas znalezienie wykładnika x, który spełnia równanie:

W praktyce najczęściej rozważamy grupę multiplikatywną Z_P^*, gdzie P jest liczbą pierwszą, a G jest generatorem. Wtedy dla wielu wartości B istnieje rozwiązanie.

Przykład

Szukamy takiego, że . Widać, że , a , więc .

Problem jest ważny w kryptografii: jego „trudność” jest fundamentem m.in. Diffie–Hellmana oraz ElGamala. Dla dużych parametrów nie znamy algorytmu, który rozwiązuje go w czasie wielomianowym w ogólności.

Baby-step Giant-step

Intuicja meet-in-the-middle oraz złożoność.

Podejście Baby-step Giant-step (Shanks)

Algorytm Baby-step Giant-step (Daniel Shanks, 1971) to klasyczne podejście typu meet-in-the-middle. Zamiast sprawdzać wszystkie wykładniki po kolei, rozbijamy niewiadomą x na dwie części:

Dla grupy multiplikatywnej modulo liczby pierwszej P przyjmujemy zwykle n = P−1. Po podstawieniu i przekształceniu dostajemy równoważny warunek:

Baby steps

Liczymy i zapisujemy tabelę wartości G^j mod P dla j = 0..m−1. To koszt pamięci \(O(√n)\).

Giant steps

Iterujemy po i i liczymy , aż trafimy na wartość obecną w tabeli baby steps.

Złożoność
Czas ~ O(√n) (plus narzut na wyszukiwanie), pamięć O(√n). To duży skok względem brute force O(n), ale nadal rośnie szybko dla kryptograficznie dużych parametrów.

FAQ

Najczęstsze pytania i odpowiedzi.

FAQ