The search functionality is under construction.
The search functionality is under construction.

Efficient Supersingularity Testing of Elliptic Curves Using Legendre Curves

Yuji HASHIMOTO, Koji NUIDA

  • Full Text Views

    0

  • Cite this

Summary :

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 proposed algorithm for characteristic p≡1 (mod 4) runs in about 61.5% of the time and for characteristic p≡3 (mod 4) also runs in about 54.9% of the time compared to Sutherland's algorithm.

Publication
IEICE TRANSACTIONS on Fundamentals Vol.E106-A No.9 pp.1119-1130
Publication Date
2023/09/01
Publicized
2023/03/07
Online ISSN
1745-1337
DOI
10.1587/transfun.2022DMP0002
Type of Manuscript
Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)
Category
Cryptography and Information Security

Authors

Yuji HASHIMOTO
  Tokyo Denki University,National Institute of Advanced Industrial Science and Technology
Koji NUIDA
  National Institute of Advanced Industrial Science and Technology,Kyushu University

Keyword