О вычислении логарифмов на эллиптических кривых

Рассматривается задача решения показательного уравнения в циклической подгруппе порядка $m$ группы $E$ точек эллиптической кривой, определенной над конечным полем $F_q$. Доказано, что если $F_{q_1}$ — минимальное расширение $F_q$ такое, что подгруппа точек, рациональных над $F_{q_1}$, группы $E$ содержит подгруппу, изоморфную $\mathbf Z/m\times\mathbf Z/m$, то сложность решения указанного уравнения не превосходит сложности вычисления логарифмов в поле $F_{q_1}$ или сложности $O(\ln m)$ арифметических операций в этом поле. Таким образом, вычисление логарифмов на эллиптических кривых сводится к логарифмированию в конечном поле. С помощью другого подхода эта редукция была получена Менезесом, Окамото и Ванстоуном.