Rozwiązywacz logarytmu dyskretnego online

Do czego służy to narzędzie?

Logarytm dyskretny to zagadnienie z teorii liczb: dla danych g, h i p znajdź takie x, że g^x ≡ h (mod p). To narzędzie rozwiązuje je metodą prób i błędów, sprawdzając kolejne wykładniki od 0 do p−1. Jest to przeszukiwanie wyczerpujące o złożoności O(p), przeznaczone do celów edukacyjnych, a nie do łamania rzeczywistych szyfrów.

Przykład działania

Dla domyślnych wartości g=2, h=8, p=13 narzędzie sprawdza: 2^0=1, 2^1=2, 2^2=4, 2^3=8. Ponieważ 8 mod 13 = 8, wynikiem jest x=3. Możesz to zweryfikować: 2^3 = 8, a 8 mod 13 = 8.

Jak działa obliczanie?

Narzędzie zaczyna od wartości 1 dla wykładnika 0, a następnie wielokrotnie mnoży przez g i bierze resztę z dzielenia przez p. Wartość h jest normalizowana modulo p, więc jeśli podasz h większe niż p lub ujemne, porównanie odbywa się z resztą z dzielenia. Jeśli w ciągu p sprawdzeń nie znajdzie dopasowania, wyświetla komunikat o braku rozwiązania.

Ograniczenia i uwagi

• Moduł p nie musi być liczbą pierwszą, ale narzędzie nie sprawdza, czy g generuje grupę multyplikatywną.
• Jeśli g i p nie są względnie pierwsze, ciąg może wejść w krótszy cykl, ale przeszukiwanie i tak zwróci pierwszy pasujący wykładnik.
• Górny limit p to 1 000 000, aby obliczenia nie obciążały zbytnio przeglądarki.
• Obliczenia wykonywane są lokalnie, bez wysyłania danych na serwer.

Często zadawane pytania

Czy narzędzie może znaleźć logarytm dla bardzo dużych modułów?

Nie, moduł p jest ograniczony do 1 000 000. Dla większych wartości obliczenia trwałyby zbyt długo, a rzeczywiste moduły kryptograficzne są celowo poza zasięgiem.

Co się stanie, jeśli podam h większe niż p?

Narzędzie najpierw normalizuje h modulo p, więc porównuje resztę z dzielenia h przez p. Na przykład dla p=13 i h=21, h mod 13 = 8, więc wynik będzie taki sam jak dla h=8.

Czy mogę użyć tego narzędzia do złamania klucza kryptograficznego?

Nie. To narzędzie ma charakter edukacyjny i działa tylko dla małych modułów. Nie nadaje się do analizy bezpieczeństwa rzeczywistych systemów kryptograficznych.