Jak trudno jest znaleźć dyskretny logarytm?

20

bab=cmodNacN

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

Odpowiedzi:

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 .NaZN×N0<c<NbN1LbaLc(modN)

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”.NaZN×


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 .)aZN×aN1


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 NaZN×0L<N1aLc(modN)aNNaZN×

rN11(modN)andr(N1)/q1(modN)  for primes q dividing N1
z definicji (korzystając z faktu, że ma porządek ).ZN×N1
  • Ś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.)Naq1,q2,N1qjN1N1

  • 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ą.NaqN1a(N1)/q1(modN)qaN1N

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.N1O(log2(N))PNN1

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.NPP

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

Xodarap
źródło