Grupa cykliczna - logarytm dyskretny

Podzielność. Reszty z dzielenia. Kongruencje. Systemy pozycyjne. Równania diofantyczne. Liczby pierwsze i względnie pierwsze. NWW i NWD.
puyo
Użytkownik
Użytkownik
Posty: 11
Rejestracja: 31 paź 2010, o 11:00
Płeć: Mężczyzna
Lokalizacja: Wrocław
Podziękował: 2 razy
Pomógł: 1 raz

Grupa cykliczna - logarytm dyskretny

Post autor: puyo »

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.
eMaerthin
Użytkownik
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

Post autor: eMaerthin »

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}}\).
ODPOWIEDZ