TY - GEN

T1 - Improved Supersingularity Testing of Elliptic Curves Using Legendre Form

AU - Hashimoto, Yuji

AU - Nuida, Koji

N1 - Funding Information:
Magma code of Sutherland’s algorithm. We thank Momonari Kudo for his helpful comments. This work was supported by JSPS KAKENHI Grant Number JP19J23395.
Publisher Copyright:
© 2021, Springer Nature Switzerland AG.

PY - 2021

Y1 - 2021

N2 - There are two types of elliptic curves, ordinary elliptic curves and supersingular elliptic curves. In 2012, Sutherland proposed an efficient and almost deterministic algorithm for determining whether a given curve is ordinary or supersingular. Sutherland’s algorithm is based on sequences of isogenies started from the input curve, and computation of each isogeny requires square root computations, which is the dominant cost of the algorithm. In this paper, we reduce this dominant cost of Sutherland’s algorithm to approximately a half of the original. In contrast to Sutherland’s algorithm using j-invariants and modular polynomials, our proposed algorithm is based on Legendre form of elliptic curves, which simplifies the expression of each isogeny. Moreover, by carefully selecting the type of isogenies to be computed, we succeeded in gathering square root computations at two consecutive steps of Sutherland’s algorithm into just a single fourth root computation (with experimentally almost the same cost as a single square root computation). The results of our experiments using Magma are supporting our argument; for cases of characteristic p of 768-bit to 1024-bit lengths, our algorithm runs 43.6% to 55.7% faster than Sutherland’s algorithm.

AB - There are two types of elliptic curves, ordinary elliptic curves and supersingular elliptic curves. In 2012, Sutherland proposed an efficient and almost deterministic algorithm for determining whether a given curve is ordinary or supersingular. Sutherland’s algorithm is based on sequences of isogenies started from the input curve, and computation of each isogeny requires square root computations, which is the dominant cost of the algorithm. In this paper, we reduce this dominant cost of Sutherland’s algorithm to approximately a half of the original. In contrast to Sutherland’s algorithm using j-invariants and modular polynomials, our proposed algorithm is based on Legendre form of elliptic curves, which simplifies the expression of each isogeny. Moreover, by carefully selecting the type of isogenies to be computed, we succeeded in gathering square root computations at two consecutive steps of Sutherland’s algorithm into just a single fourth root computation (with experimentally almost the same cost as a single square root computation). The results of our experiments using Magma are supporting our argument; for cases of characteristic p of 768-bit to 1024-bit lengths, our algorithm runs 43.6% to 55.7% faster than Sutherland’s algorithm.

UR - http://www.scopus.com/inward/record.url?scp=85115121553&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85115121553&partnerID=8YFLogxK

U2 - 10.1007/978-3-030-85165-1_8

DO - 10.1007/978-3-030-85165-1_8

M3 - Conference contribution

AN - SCOPUS:85115121553

SN - 9783030851644

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 121

EP - 135

BT - Computer Algebra in Scientific Computing - 23rd International Workshop, CASC 2021, Proceedings

A2 - Boulier, François

A2 - England, Matthew

A2 - Sadykov, Timur M.

A2 - Vorozhtsov, Evgenii V.

PB - Springer Science and Business Media Deutschland GmbH

T2 - 23rd International Workshop on Computer Algebra in Scientific Computing, CASC 2021

Y2 - 13 September 2021 through 17 September 2021

ER -