Jak zmierzyć złożoność problemu dyskretnego logarytmu?

Odpowiedzi na to pytanie na Crypto Stack Exchange mówią w zasadzie, że aby zmierzyć złożoność problemu z logarytmem, musimy wziąć pod uwagę długość liczby reprezentującej wielkość grupy. Wydaje się to arbitralne, dlaczego nie wybraliśmy wielkości grupy jako argumentu? Czy istnieje kryterium pozwalające ustalić, który argument wybrać? W rzeczywistości wiem, że przeoczyłem coś ważnego, ponieważ złożoność zmienia się ogromnie, jeśli robimy to ze względu na wielkość grupy.

time-complexity discrete-mathematics cryptography Nassim HADDAM
źródło

Interesujące pytanie! Zredagowałem to, by powiedzieć „zmierzyć złożoność”, a nie „obliczyć”, ponieważ odpowiedzią na to, jak ją obliczamy, jest ¯ \ _ (ツ) _ / ¯. :-)

David Richerby

Myślę, że tak jest lepiej. :)

Nassim HADDAM

Odpowiedzi:

Nie ma znaczenia, czy wybierzesz rozmiar grupylub wielkość liczby całkowitej reprezentującej go jako parametr, ponieważ. Są dwa powody, dla których złożoność jest zwykle opisywana w kategoriach zamiast: $|G|$ $n$ $n \approx \log |G|$ $n$ $|G|$

$n$ to długość danych wejściowych (dokładniej dane wejściowe mają długość $\Theta(n)$ ) i zwykle mierzymy złożoność algorytmów jako funkcję długości wejściowej.
Zazwyczaj $n$ jest małą liczbą, taką jak $1024$ , natomiast $|G|$ to ogromna liczba, taka jak (z grubsza) $2^{1024}$ .

Yuval Filmus
źródło

Rozumiem twój punkt widzenia, ale czy nie stanowi problemu w P, jeśli wybraliśmy wielkość grupy jako parametr?

Nassim HADDAM

W takim przypadku nie można wybrać parametru - parametrem jest zawsze długość wejściowa.

Yuval Filmus

Dziękuję za odpowiedzi. Miałem problem z tym, co może się zdarzyć, jeśli weźmiemy pod uwagę inny przypadek (problemy z przejściem P w NP i odwrotnie). Widzę teraz wyraźnie :) .

Nassim HADDAM

Nie wykonujemy obliczeń pojedynczo, ponieważ naszym celem jest uwzględnienie pewnej liczby lub obliczenie logarytmu dyskretnego i nie obchodzi nas, w jaki sposób liczba jest reprezentowana. Podanie go jako danych wejściowych w formacie binarnym lub jednostkowym nie wpływa na „czas ściany” potrzebny do rozwiązania problemu, a jedynie jego złożoność pod względem wielkości wejściowej (ponieważ zmieniamy wielkość wejściową!).

Yuval Filmus

Poza tym tak naprawdę nie możemy mieć 128-bitowej liczby całkowitej jako jednoznacznego wejścia do algorytmu w świecie rzeczywistym. We wszechświecie atomów jest za mało.

Yuval Filmus