The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. ex. Some numerals are expressed as "XNUMX".
Copyrights notice
The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. Copyrights notice
Existem dois tipos de curvas elípticas, curvas elípticas comuns e curvas elípticas supersingulares. Em 2012, Sutherland propôs um algoritmo eficiente e quase determinístico para determinar se uma determinada curva é ordinária ou supersingular. O algoritmo de Sutherland é baseado em sequências de isogenias iniciadas a partir da curva de entrada, e o cálculo de cada isogenia requer cálculos de raiz quadrada, que é o custo dominante do algoritmo. Neste artigo, reduzimos esse custo dominante do algoritmo de Sutherland para aproximadamente metade do original. Em contraste com o algoritmo de Sutherland usando j-invariantes e polinômios modulares, nosso algoritmo proposto é baseado na forma de curvas elípticas de Legendre, o que simplifica a expressão de cada isogenia. Além disso, selecionando cuidadosamente o tipo de isogenias a serem computadas, conseguimos reunir cálculos de raiz quadrada em duas etapas consecutivas do algoritmo de Sutherland em apenas um único cálculo de quarta raiz (com experimentalmente quase o mesmo custo de um cálculo de raiz quadrada única). Os resultados dos nossos experimentos usando Magma apoiam nosso argumento; para casos de característica p de comprimentos de 768 bits a 1024 bits, nosso algoritmo proposto para características p≡1 (mod 4) é executado em cerca de 61.5% do tempo e para características p≡3 (mod 4) também é executado em cerca de 54.9% do tempo em comparação com o algoritmo de Sutherland.
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.
Copiar
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
Copiar
@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},}
Copiar
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 -