Новый алгоритм для дискретного журнала и его значение для квантовых вычислений

Вышла новая статья, утверждающая квазиполиномиальный алгоритм для дискретного логарифма. http://arxiv.org/abs/1306.4244

Если все верно, значит ли это, что у нас больше нет экспоненциального разделения по сложности классического алгоритма и его квантовой версии для задачи дискретного логарифма? Имеет ли это какое-либо значение для квантовой теории сложности?

Что ж, одно важное наблюдение заключается в том, что новый алгоритм, очевидно, работает только для групп вида где p мало, - он не дает ускорения для групп вида Z p . Последнее является гораздо более распространенным параметром, о котором говорят люди, как для криптографии, так и для алгоритма Шора, и новый алгоритм не угрожает квантовому ускорению там. С другой стороны, да, если я не ошибаюсь, в случае Z p k ускорение значительно уменьшается .$Z_{p^k}$$p$$Z_p$$Z_{p^k}$

$k = O (q)$$n^{O (\log n)}$$F_{q^k}$$k = O (q)$$L_{q^k} (\alpha, O (1))$ в конечных полях $F_{q_k}$ с $q \sim L_{q^k} (\alpha)$, Это превосходит предыдущие классические алгоритмы для$\alpha < 1 / 3$,

Алгоритм Шора все еще намного быстрее, но вопрос об экспоненциальном ускорении действительно зависит от определения «экспоненциального». (Также NFS / FFS были субэкспоненциальным временем.)