Improved supersingularity testing of elliptic curves using Legendre form (Q831974)

The paper improves the computational cost of an algorithm due to \textit{A. V. Sutherland} [LMS J. Comput. Math. 15, 317--325 (2012; Zbl 1307.11072)] which decides if a given elliptic curve \(E\)\, defined over a finite field \(\mathbb{F}_q\)\, of characteristic \(p\ge 5\)\, is ordinary or supersingular. The test of Sutherland is based on the graph of \(l\)-isogenies (\(l\ne p\)) of \(E\). In the ordinary case the graph is a volcano, see [\textit{M. Fouquet} and \textit{F. Morain}, Lect. Notes Comput. Sci. 2369, 276--291 (2002; Zbl 1058.11041)], while in the supersingular case is an expander Ramanujan graph, see [\textit{A. K. Pizer}, Bull. Am. Math. Soc., New Ser. 23, No. 1, 127--137 (1990; Zbl 0752.05035)]. The Sutherland's algorithm take \(l=2\)\, (because it is the case most easy to compute). The algorithm determines which is the type of the 2-graph of E. The computational complexity of the Sutherland's algorithm is dominated by the computation of square roots over \(\mathbb{F}_{p^2}\). The cost of an square root is \(O(n^2(log_2 n)^2);\, n=log_2 p\). The algorithm proposed in the present paper takes Legendre models, instead of Weiertrasse models, for the elliptic curves and it substitutes the computation of two square roots by a quarter root computation. In the authors words ``we reduce this dominant cost of Sutherland's algorithm to approximately a half of the original.'' Sections 2 to 5 summarize the necessary concepts and results on elliptic curves and isogenies. Section 6 describes the Sutherland's algorithm and Section 6 the proposed variant of the supersingular testing algorithm. Sections 8 and 9 shows the comparison of the performances of the Sutherland's algorithm and the present proposal, giving numerical results of an implementation using Magma (Tables 1, 2 and 3). For the entire collection see [Zbl 1482.68009].