Дискретный логарифм в общей групповой модели сложен - Теорема Шоупа

Позволять $К$ быть константой (которая не зависит от $р$) такой, что вероятность ограничена $ К \ гидроразрыва {м ^ 2} {р} $. (такие $К$ существует по определению $\mathcal{O}$).

Это означает, что если противник решит задачу дискретного логарифмирования с вероятностью более $\фракция{1}{2}$, мы получаем.

$$K\frac{m^2}{p}\geq\frac{1}{2}$$.

Это подразумевает, что

$$m\geq\sqrt{\frac{p}{2K}} $$

Таким образом, мы делаем вывод, что $м$ - что на самом деле является функцией $р$, ограничен снизу $K'\sqrt{p}$, с $ К ': = \ sqrt {\ гидроразрыва {1} {2K}} $ константа, не зависящая от $р$.

Это эквивалентно написанию $m\in\Omega(\sqrt{p})$ (согласно обозначение Кнута).

Заметьте теперь, что $\sqrt{p}$ экспоненциально зависит от размера входных данных, и вы сделаете вывод, что любой общий противник неэффективен против DLog.