Fast algorithms for computing isogenies between ordinary elliptic curves in small characteristic (Q2430987): Difference between revisions

The paper discusses the problem of computing isogenies between elliptic curves defined over a finite field \(\mathbb{F}_q,\,\, q=p^d\),\, with characteristic \(p\)\, small. In particular the paper analyzes and improves an algorithm, called \texttt{C2} here, and its variants, which computes the isogeny studying its action on the \(p^k\)-torsion subgroup \(E[p^k]\),\, for \(k\)\, large enough. Section 3 reviews the algorithm \texttt{C2}, due to \textit{J. M. Couveignes} [Proceedings. Berlin: Springer. Lect. Notes Comput. Sci. 1122, 59--65 (1996; Zbl 0903.11030)], and adapts it to characteristic 2 (the original algorithm only worked in odd characteristic). Although Couveignes estimates the complexity of \texttt{C2}, for \(l\)-degree isogenies, as being \(\tilde{O}(l^2\log q)\)\, operations in the prime field \(F_p\)\, (with a precomputation and additional requirements), the present paper argues that in fact the overall complexity is \(\tilde{O}(l^3\log q)\). Section 4 analyzes a later proposal of Couveignes, call here \texttt{C2-AS} (AS meaning Artin-Schreier presumably) giving an alternative approach to the resolution of an Artin-Schreier equation in \texttt{C2}. The complexity analysis of \texttt{C2-AS}, including a new construction of the present author and \textit{Schost} [Fast arithmetics in Artin-Schreier towers over finite fields, \url{arXiv:1002.2594}], concludes that the dependence of \(l\)\, is still cubic. Section 5 gives a new variant \texttt{C2-AS-FI}, which incorporates a new algorithm for the polynomial interpolation step in \texttt{C2-AS}. Theorem 1 shows that \texttt{C2-AS-FI} reaches the quadratic bound in \(l\). Section 6 proposes the final version \texttt{C2-AS-FI-MC}, which uses the Frobenius endomorphism to reduce the number of interpolations in the algorithm. Section 7 shows details and \`\` some tricks'' of a C++ implementation of \texttt{C2-AS-FI-MC}, as well as an implementation in \texttt{MAGMA} of another algorithm LS due to \textit{R. Lercier} and \textit{T. Sirvent} [J. Théor. Nombres Bordx. 20, No. 3, 783--797 (2008; Zbl 1230.11080)], using p-adic methods. The final section 8 presents numerical results of experiments to compare the different variants of \texttt{C2} between themselves and with LS. It become that \`\` LS is asymptotically worse in \(l\)\, than \texttt{C2}'', but \`\` LS is more practical than \texttt{C2} in many circumstances''. The final conclusion is that \`\` the variants derived form \texttt{C2} don't seem to be practical, at least for present day data sizes''.