Được biết, đối với một đường cong elip $E$ được xác định trên một trường nguyên tố $\mathbb{F}_p$ như vậy mà $E(\mathbb{F}_p)$ là một số nguyên tố, các thuật toán tốt nhất (ngoài một số trường hợp cụ thể) để giải logarit rời rạc là các thuật toán chung cho nhóm abelian: Bước khổng lồ Baby-steps, Pollard rho, Kangaroo.
Đối với các đường cong elip được xác định trên phần mở rộng trường, tồn tại các phương pháp tính chỉ số.
Hai trong số các thuật toán hiệu quả nhất là
- Cái của Gaudry và Diem, nên phức tạp, theo Joux và Vitse, $O(n!\cdot2^{3n(n-1)}\cdot p^{2-2/n})$. Điều này là thực tế, theo Joux và Vitse, chỉ dành cho $n\leq 4$.
- Một trong những Joux và Vitse, hiệu quả hơn cho $n\geq 5$: nó có một chi phí $\tilde O((n-1)!\cdot (2^{(n-1)(n-2)}\cdot e^n\cdot n^{-1/2})^\omega\cdot p ^2)$.
Có thể những ước tính đó là sơ bộ, nhưng có vẻ như trong các trường hợp thực tế, chúng kém hiệu quả hơn các thuật toán chung.
Ví dụ lấy cho $p\sim 2^{64}$ và $n=4$. Thuật toán Gaudry và Diem sẽ có chi phí $O(4!\cdot 2^{36+96})$, vì vậy trung bình kém hơn so với $O(\sqrt{p^n})$, đó là chi phí của các thuật toán chung.
Tương tự giả sử rằng $\omega=2$ (trường hợp lạc quan), $p\sim 2^{51}$, $n=5$ trong thuật toán thứ hai, thì chúng ta sẽ có chi phí là $O(4!\cdot2^{24}\cdot e^{10}\cdot\frac{1}{5}\cdot 2^{102})\simeq O(2^{142,69})$, tệ hơn ước tính cho thuật toán chung.
Vì vậy, câu hỏi của tôi là: Tôi có thiếu thứ gì không? Các thuật toán này có thực tế không (tiệm cận trên $q$ cho cố định $n$ câu trả lời rõ ràng là có) hiệu quả hơn những cái chung? Có thể sử dụng các đường cong elip được xác định trên các trường mở rộng để ghi mật mã nếu được chọn cẩn thận không?
