Насколько сложно найти дискретный логарифм?

20

Дискретный логарифм такого же , как нахождение в , дан , и . $b$ $a^b=c \bmod N$ $a$ $c$ $N$

Интересно, в каких группах сложности (например, для классических и квантовых компьютеров) это находится, и какие подходы (то есть алгоритмы) являются лучшими для выполнения этой задачи.

Ссылка на википедию, приведенная выше, на самом деле не дает очень конкретного времени выполнения. Я надеюсь на что-то более похожее на то, что наиболее известные методы для поиска таких.

algorithms complexity-theory time-complexity discrete-mathematics Мэтт Грофф
источник

Я не знаю, какой алгоритм лучше, но вы можете найти некоторые алгоритмы в главе 5 этой лекционной заметки Йохана Хастада. Я бы суммировал эти алгоритмы, но я не читал эту главу, поэтому я только предоставляю ссылку;)

Марк Бери

21

Короткий ответ.
Если мы сформулируем подходящую версию задачи решения задачи дискретного логарифма, мы можем показать, что она принадлежит пересечению классов сложности NP , coNP и BQP .

Решение проблемной версии Discrete Log.
Проблема дискретного логарифма чаще всего формулируется как задача функции , отображающая кортежи целых чисел в другое целое число. Такая формулировка проблемы несовместима с классами сложности P , BPP , NP и т. Д., Которые люди предпочитают рассматривать, которые касаются только решения (да / нет) проблем. Мы можем рассмотреть вариант решения проблемы дискретного журнала, который эффективно эквивалентен:

Дискретный журнал (проблема решения). Для простого числа генератор мультипликативных единиц по модулю , целое число и верхняя граница определяют, существует ли такой, что . $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}$

Это позволило бы нам фактически вычислить log _a ( c ) по модулю N с помощью бинарного поиска, если бы мы могли эффективно решить его. Затем мы можем спросить, к каким классам сложности относится эта проблема. Обратите внимание, что мы сформулировали это как проблему обещания: мы можем расширить ее до задачи решения, приостановив требования, что простое число и генератор, но добавив условие, что эти ограничения выполняются для любой «ДА» экземпляр проблемы. $N$ $a \in \mathbb Z_N^\times$

Дискретный журнал находится в BQP.
Используя алгоритм Шора для вычисления дискретного логарифма ( алгоритмы полиномиального времени для простой факторизации и дискретные логарифмы на квантовом компьютере ), мы можем легко содержать дискретный лог в BQP . (Чтобы проверить, действительно ли является генератором, мы можем использовать алгоритм поиска порядка Шора в той же статье, которая является основой для алгоритма дискретного логарифма, чтобы найти порядок и сравните это с .) $a \in \mathbb Z_N^\times$ $a$ $N-1$

Дискретный журнал находится в NP ∩ coNP.
Если на самом деле простое, а - генератор, достаточным сертификатом для экземпляра «YES» или «NO» для решения задачи является уникальное целое число такой, что . Таким образом, достаточно показать, что мы можем подтвердить, выполняются ли условия для иПосле заметки Брассарда о сложности криптографии , если в обоих случаях простое, а - генератор, то это тот случай, когда $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_{N}^{\times}

$\mathbb Z_N^\times$

N - 1

$N-1$

Свидетельство о том , что ограничения на и и удерживать бы список главных факторов разделительного , что позволит нам проверить вышеуказанные ограничения конгруэнции. (Мы можем проверить, является ли каждый простым, используя тест AKS, если мы хотим, и проверить, что это все факторы , пытаясь найти факторизацию первичной мощности только с этими простыми числами.) $N$ $a$ $q_1, q_2, \ldots$ $N-1$ $q_j$ $N-1$ $N-1$
Сертификат, одно из ограничений на или сбой будет целое число , которое делит , таким образом, что . В этом случае нет необходимости проверять на первичность; из этого сразу следует, что порядок меньше , и поэтому он является генератором мультипликативной группы, только если не может быть простым. $N$ $a$ $q$ $N-1$ $a^{(N-1)/q} \equiv 1 \pmod{N}$ $q$ $a$ $N-1$ $N$

Ниль де Бодрап
источник

3

Насколько мне известно, в общем и наихудшем сценариях ответ Ниль де Бодрапа является правильным.

Однако в случае, когда имеет только малые простые множители, алгоритм Pohlig-Hellman находит логарифм за времени. Таким образом, в этом случае, задача дискретного входа в . Таким образом, когда криптографический протокол зависит от сложности этой проблемы, важно выбрать модуль , такой, что имеет большие простые факторы. $N-1$ $O(log^2(N))$ $P$ $N$ $N-1$

danxinnoble
источник

-1

поскольку , то . (Значение грубой силы в EXP.) $|a|=O(N)$ $b=O(N)$

Для недетерминированной машины есть полиномиальный свидетель, поскольку мы можем сделать возведение в модуляр в P. (т.е. проблема в .) $NP$

Теория о том, что дискретные логарифмы есть в а не в является основой современной криптографии, но это явно недоказано. $NP$ $P$

Метод Шора (ссылка на который есть на этой странице википедии) выполняется за полиномиальное время на квантовом компьютере.

Xodarap
источник

Насколько сложно найти дискретный логарифм?

Ответы: