It is known that, for an elliptic curves $E$ defined over a prime field $\mathbb{F}_p$ such that $E(\mathbb{F}_p)$ is a prime number, the best algorithms (beside some specific cases) for solving the discrete logarithm are the general ones for an abelian group: Baby-steps Giant-steps, Pollard rho, Kangaroo.
For elliptic curves defined over a field extension there exist index calculus methods.
Two of the most effective algorithms are
- The one of Gaudry and Diem, which should have a complexity, according to the Joux and Vitse, $O(n!\cdot2^{3n(n-1)}\cdot p^{2-2/n})$. This is practical, according to Joux and Vitse, only for $n\leq 4$.
- The one of Joux and Vitse, which is more effective for $n\geq 5$: it has a cost $\tilde O((n-1)!\cdot (2^{(n-1)(n-2)}\cdot e^n\cdot n^{-1/2})^\omega\cdot p^2)$.
Probably those estimates are rough, but it seems that in practical cases they're less performant than the general algorithms.
For example take for $p\sim 2^{64}$ and $n=4$. The Gaudry and Diem algorithm would have cost $O(4!\cdot 2^{36+96})$, so averagely worse than $O(\sqrt{p^n})$, which is the cost of the generic algorithms.
Similarly assume that $\omega=2$ (optimistic case), $p\sim 2^{51}$, $n=5$ in the second algorithm, then we would have a cost of $O(4!\cdot2^{24}\cdot e^{10}\cdot\frac{1}{5}\cdot 2^{102})\simeq O(2^{142.69})$, which is worse than the estimates for the generic algorithm.
So, my question is: Am I missing something? Are these algorithm practically (asymptocally on $q$ for fixed $n$ the answer is clearly yes) more performant than generic ones? Can elliptic curves defined over extension fields be used for cryprography if chosen carefully?
