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.
Odpowiedzi:
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:
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∈Z×N
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 .)
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
Ś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 q1,q2,… N−1 qj 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≡1(modN) q a N−1 N
źródło
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(log2(N)) P N N−1
źródło
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.
źródło