Jak trudno jest znaleźć dyskretny logarytm?

20

$b$ $a^b=c \bmod N$ $a$ $c$ $N$

Zastanawiam się, w jakich grupach złożoności (np. Dla komputerów klasycznych i kwantowych) to jest i jakie podejścia (tj. Algorytmy) są najlepsze do wykonania tego zadania.

Powyższy link do Wikipedii tak naprawdę nie zapewnia bardzo konkretnych środowisk uruchomieniowych. Mam nadzieję na coś bardziej podobnego do najbardziej znanych metod ich znajdowania.

— Matt Groff
źródło

Nie wiem jaki jest najlepszy algorytm, ale można znaleźć kilka algorytmów w rozdziale 5 tego wykładowych notatek Johan Hastad. Podsumowałbym te algorytmy, ale nie przeczytałem tego rozdziału, więc podaję tylko link;)

— Marc Bury

21

Krótka odpowiedź.
Jeśli sformułować odpowiedni problem decyzyjny wersję problemu logarytm dyskretny, możemy pokazać, że należy do skrzyżowania z klasami złożoności NP , CONP i BQP .

Wersja Discrete Log stanowiąca problem decyzyjny.
Problem logarytmu dyskretnego jest najczęściej formułowany jako problem funkcji , odwzorowujący krotki liczb całkowitych na inną liczbę całkowitą. Takie sformułowanie problemu jest niezgodne z klasami złożoności P , BPP , NP itd., Które ludzie wolą brać pod uwagę, które dotyczą wyłącznie problemów decyzyjnych (tak / nie). Możemy rozważyć wersję problemu z dyskretnym dziennikiem, który jest faktycznie równoważny:

Dyskretny dziennik (problem decyzyjny). Biorąc pod uwagę liczbę pierwszą , generator multiplikatywnych jednostek modulo , liczba całkowita i górna granica , określają, czy istnieje taki, że . $N$ $a \in \mathbb Z_N^\times$ $N$ $0 < c < N$ $b \in \mathbb N$ $1 \leqslant L \leqslant b$ $a^L \equiv c \pmod{N}$

To pozwoliłoby nam faktycznie obliczyć log _a ( c ) modulo N przez wyszukiwanie binarne, gdybyśmy mogli to skutecznie rozwiązać. Możemy wtedy zapytać, do których klas złożoności należy ten problem. Zwróćmy uwagę, że sformułowaliśmy to jako problem obietnicy: możemy rozszerzyć go na problem decyzyjny, zawieszając wymagania, że będzie liczbą pierwszą i generator, ale dodając warunek, że ograniczenia te dotyczą każda instancja problemu „TAK”. $N$ $a \in \mathbb Z_N^\times$

Dyskretny dziennik jest w BQP.
Używając algorytmu Shora do obliczania logarytmu dyskretnego ( algorytmy wielomianowego czasu dla faktoryzacji pierwotnej i logarytmów dyskretnych na komputerze kwantowym ), możemy łatwo zawierać Log dyskretny w BQP . (Aby sprawdzić, czy faktycznie jest generatorem, możemy użyć algorytmu znajdowania porządku Shora w tym samym artykule, który jest podstawą algorytmu dyskretnego logarytmu, aby znaleźć kolejność i porównaj to z .) $a \in \mathbb Z_N^\times$ $a$ $N-1$

Discrete Log jest w NP ∩ coNP.
Jeśli tak naprawdę jest to, że jest liczbą pierwszą, a jest generatorem, wystarczającym certyfikatem dla wystąpienia „TAK” lub „NIE” problemu decyzyjnego jest unikalna liczba całkowita taki, że . Więc wystarczy to, aby pokazać, że możemy zaświadczyć, czy warunki na i zawieszone. Zgodnie z uwagą Brassarda dotyczącą złożoności kryptografii , jeśli zarówno przypadek jest liczbą pierwszą, jak i jest generatorem, to jest tak, że $N$ $a \in \mathbb Z_N^\times$ $0 \leqslant L < N-1$ $a^L \equiv c \pmod{N}$ $a$ $N$ $N$ $a \in \mathbb Z_N^\times$

r^{N - 1} \equiv 1 (\mod N) and r^{(N - 1) / q} ≢ 1 (\mod N) for primes q dividing N - 1

$r^{N-1} \equiv 1 \!\!\!\!\pmod{N} \qquad\text{and}\qquad r^{(N-1)/q} \not\equiv 1 \!\!\!\!\pmod{N} ~~\text{for primes $q$ dividing $N-1$}$ z definicji (korzystając z faktu, że ma porządek ).

Z_{N}^{\times}

$\mathbb Z_N^\times$

N - 1

$N-1$

Świadectwo, że ograniczenia w i zarówno chwyt będzie lista z głównych czynników dzielących , który pozwoli nam przetestować powyższe ograniczenia kongruencji. (Możemy sprawdzić, czy każdy jest liczbą pierwszą za pomocą testu AKS, jeśli chcemy, i przetestować, czy są to wszystkie czynniki pierwsze , próbując znaleźć rozkład na czynniki pierwsze tylko z tymi liczbami pierwszymi.) $N$ $a$ $q_1, q_2, \ldots$ $N-1$ $q_j$ $N-1$ $N-1$
Certyfikat, że jednym z ograniczeń lub nie byłoby całkowita która dzieli , tak, że . W tym przypadku nie jest konieczne testowanie kątem pierwotności; natychmiast oznacza to, że rząd jest mniejszy niż , a zatem jest generatorem grupy multiplikatywnej tylko wtedy, gdy nie jest liczbą pierwszą. $N$ $a$ $q$ $N-1$ $a^{(N-1)/q} \equiv 1 \pmod{N}$ $q$ $a$ $N-1$ $N$

— Niel de Beaudrap
źródło

3

W ogólnych i najgorszych przypadkach odpowiedź Niel de Beaudrap jest poprawna, zgodnie z moją najlepszą wiedzą.

Jednak w przypadku, gdy ma tylko małe czynniki pierwsze, algorytm Pohliga-Hellmana znajduje logarytm w czasie . Dlatego w tym przypadku problemem jest dyskretna Log . Jako taki, gdy protokół kryptograficzny zależy od stopnia trudności tego problemu, ważne jest, aby wybrać moduł , tak aby miał duże czynniki pierwsze. $N-1$ $O(log^2(N))$ $P$ $N$ $N-1$

— Danxinnoble
źródło

-1

ponieważ , a następnie . (To znaczy, że brutalna siła jest w EXP.) $|a|=O(N)$ $b=O(N)$

W przypadku maszyny niedeterministycznej istnieje obserwator wielomianowy, ponieważ możemy przeprowadzić potęgowanie modularne w P. (tzn. Problem jest w .) $NP$

Teoria, że dyskretne logarytmy są w ale nie w jest podstawą współczesnej kryptografii, ale to oczywiście nie jest udowodnione. $NP$ $P$

Metoda Shora (do której link znajduje się na tej stronie wikipedii) działa w czasie wielomianowym na komputerze kwantowym.

— Xodarap
źródło