Piszę funkcję wyznaczania logarytmu dyskretnego na podstawie i książki "HANDBOOK of APPLIED CRYPTOGRAPHY" (, rozd. The discrete logarithm problem).
Wydaje mi się, że błędu w algorytmie nie zrobiłem, a problemem jest chyba analiza i zrozumienie na jakich danych algorytm ma pracować.
Wejście:
a - generator
B - liczba logarytmowana
N - -> \(\displaystyle{ Z ^{*}_{N}}\)
n - rozmiar grupy
Z tego co zrozumiałem, dla liczb pierwszych N, rozmiar grupy to N-1.
Dla danych z książki (a=5, B=35, N=97, n=96) albo (a=2, B=228, N=383, n=191) wyniki się zgadzają, ale wymyślone moje dane np. (a=82, B=68, N=101, N=100, spodziewane 42 - [url=http://www.wolframalpha.com/input/?i=82%5E42+mod+101]WolframAlpha[/url]) nie dają poprawnych wyników. Algorytm tworząc wynik chce obliczyć \(\displaystyle{ 80^{-1}mod 100}\) co nie istnieje:
[url=http://imageshack.us/photo/my-images/43/captureiaj.jpg/][/url]
Czy to zbieg okoliczności, że te kilka przykładów działa a tak naprawdę algorytm jest zły, czy chodzi o jakiś błąd w dobieraniu liczb?
Dzięki.
Grupa cykliczna - logarytm dyskretny
-
- Użytkownik
- Posty: 40
- Rejestracja: 12 paź 2011, o 19:03
- Płeć: Mężczyzna
- Lokalizacja: Wrocław
- Pomógł: 10 razy
Grupa cykliczna - logarytm dyskretny
przecież \(\displaystyle{ 80^{-1}\pmod{100}}\) nie istnieje... bo nie można znaleźć liczby \(\displaystyle{ k\in\mathbb{Z}_{100}}\) takiej, by \(\displaystyle{ 80k=100l+1}\), gdzie \(\displaystyle{ l\in\mathbb{Z}}\).