Se știe că, pentru o curbă eliptică $E$ definite peste un câmp prim $\mathbb{F}_p$ astfel încât $E(\mathbb{F}_p)$ este un număr prim, cei mai buni algoritmi (pe lângă unele cazuri specifice) pentru rezolvarea logaritmului discret sunt cei generali pentru un grup abelian: Baby-steps Giant-steps, Pollard rho, Kangaroo.
Pentru curbele eliptice definite pe o extensie de câmp există metode de calcul index.
Doi dintre cei mai eficienți algoritmi sunt
- Cel al lui Gaudry și Diem, care ar trebui să aibă o complexitate, conform celor Joux și Vitse, $O(n!\cdot2^{3n(n-1)}\cdot p^{2-2/n})$. Acest lucru este practic, potrivit lui Joux și Vitse, numai pentru $n\leq 4$.
- Cel al lui Joux si Vitse, care este mai eficient pentru $n\geq 5$: are un cost $\tilde O((n-1)!\cdot (2^{(n-1)(n-2)}\cdot e^n\cdot n^{-1/2})^\omega\cdot p ^2)$.
Probabil că acele estimări sunt aproximative, dar se pare că în cazuri practice sunt mai puțin performante decât algoritmii generali.
De exemplu ia pentru $p\sim 2^{64}$ și $n=4$. Algoritmul Gaudry și Diem ar fi costat $O(4!\cdot 2^{36+96})$, deci în medie mai rău decât $O(\sqrt{p^n})$, care este costul algoritmilor generici.
În mod similar presupune că $\omega=2$ (caz optimist), $p\sim 2^{51}$, $n=5$ în al doilea algoritm, atunci am avea un cost de $O(4!\cdot2^{24}\cdot e^{10}\cdot\frac{1}{5}\cdot 2^{102})\simeq O(2^{142,69})$, care este mai rău decât estimările pentru algoritmul generic.
Deci, întrebarea mea este: îmi scapă ceva? Sunt acest algoritm practic (asimptoc activat $q$ pentru fix $n$ raspunsul este clar da) mai performante decat cele generice? Curbele eliptice definite pe câmpuri de extensie pot fi folosite pentru cripografie dacă sunt alese cu grijă?
