The search functionality is under construction.

The search functionality is under construction.

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

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

The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.

Copy

Yuji HASHIMOTO, Koji NUIDA, "Efficient Supersingularity Testing of Elliptic Curves Using Legendre Curves" in IEICE TRANSACTIONS on Fundamentals,
vol. E106-A, no. 9, pp. 1119-1130, September 2023, doi: 10.1587/transfun.2022DMP0002.

Abstract: 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.

URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/transfun.2022DMP0002/_p

Copy

@ARTICLE{e106-a_9_1119,

author={Yuji HASHIMOTO, Koji NUIDA, },

journal={IEICE TRANSACTIONS on Fundamentals},

title={Efficient Supersingularity Testing of Elliptic Curves Using Legendre Curves},

year={2023},

volume={E106-A},

number={9},

pages={1119-1130},

abstract={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.},

keywords={},

doi={10.1587/transfun.2022DMP0002},

ISSN={1745-1337},

month={September},}

Copy

TY - JOUR

TI - Efficient Supersingularity Testing of Elliptic Curves Using Legendre Curves

T2 - IEICE TRANSACTIONS on Fundamentals

SP - 1119

EP - 1130

AU - Yuji HASHIMOTO

AU - Koji NUIDA

PY - 2023

DO - 10.1587/transfun.2022DMP0002

JO - IEICE TRANSACTIONS on Fundamentals

SN - 1745-1337

VL - E106-A

IS - 9

JA - IEICE TRANSACTIONS on Fundamentals

Y1 - September 2023

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 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.

ER -