Бумага Связь между взломом протокола Диффи-Хеллмана и вычислением дискретных логарифмов содержит некоторые интересные результаты, хотя они носят несколько технический характер.
В частности, это необходимо:
Предположение о гладкости: За $n\in\mathbb{N}$, определять
$\ню(п)$ быть минимум, свыше $d\in [n-2\sqrt{n}+1, n+2\sqrt{n}+1]$ наибольшего простого множителя $д$.
предположение о гладкости в том, что $\nu(n) = (\log n)^{O(1)}$.
В этой настройке, если у кого-то есть небольшая «цепочка советов», специфичная для $G$ (в документе говорится, что нужны большие простые множители $|G|$ и некоторые параметры эллиптических кривых --- общий совет имеет длину $O(\log |G|)$, тогда:
Следствие 5. Если предположение о гладкости верно, то существует общий (неравномерный) алгоритм с полиномиальным временем вычисления дискретных логарифмов в циклических группах порядка $n$, совершая вызовы оракула DH для той же группы тогда и только тогда, когда все множественные простые множители $n$ в порядке $ (\ журнал п) ^ {О (1)} $.
Здесь «несколько простых множителей» означают средние степени простых чисел. $p^e \mid п$ за $е > 1$.
Если все простые множители $n$ являются «одиночными» (например, $n$ не содержит квадратов), кажется, они могут добиться большего успеха --- их теорема 2 покрывает этот случай и, по-видимому, устраняет требование знания эллиптических кривых + предположение о гладкости (все еще требуется факторизация), и они явно оценить сложность редукции. Я не буду копировать его здесь, так как формулировка теоремы довольно длинная.
Все это говорит о том, что при определенном теоретико-числовом допущении в неравномерной постановке разрыва между DLOG и CDH нет.
