Известно, что для эллиптических кривых $Е$ определенный над простым полем $\mathbb{F}_p$ такой, что $E(\mathbb{F}_p)$ является простым числом, лучшими алгоритмами (помимо некоторых частных случаев) решения дискретного логарифма являются общие алгоритмы для абелевой группы: Baby-steps Giant-steps, Pollard rho, Kangaroo.
Для эллиптических кривых, заданных над расширением поля, существуют методы индексного исчисления.
Два наиболее эффективных алгоритма:
- Один из Годри и Дьема, который должен иметь сложность, согласно Жу и Витсе, $O(n!\cdot2^{3n(n-1)}\cdot p^{2-2/n})$. Это практично, по мнению Жукса и Витсе, только для $n\leq 4$.
- Тот из Joux и Vitse, который более эффективен для $n\geq 5$: это имеет цену $\тильда O((n-1)!\cdot (2^{(n-1)(n-2)}\cdot e^n\cdot n^{-1/2})^\omega\cdot p ^2)$.
Вероятно, эти оценки грубы, но кажется, что в практических случаях они менее эффективны, чем общие алгоритмы.
Например взять для $p\sim 2^{64}$ и $n=4$. Алгоритм Годри и Дима стоил бы $O(4!\cdot 2^{36+96})$, так что в среднем хуже, чем $O(\sqrt{p^n})$, что является стоимостью общих алгоритмов.
Точно так же предположим, что $\омега=2$ (оптимистичный случай), $p\sim 2^{51}$, $n=5$ во втором алгоритме, тогда у нас будет стоимость $O(4!\cdot2^{24}\cdot e^{10}\cdot\frac{1}{5}\cdot 2^{102})\simeq O(2^{142,69})$, что хуже, чем оценки для универсального алгоритма.
Итак, мой вопрос: я что-то упустил? Являются ли эти алгоритмы практичными (асимптотически на $q$ для фиксированного $n$ ответ однозначно да) более производительны, чем универсальные? Могут ли эллиптические кривые, заданные над полями расширения, использоваться для криптографии, если их тщательно выбирать?
