Improved supersingularity testing of elliptic curves using Legendre form
type: Item
instance of: scholarly article
title: Improved supersingularity testing of elliptic curves using Legendre form
zbMATH Open document ID: 1496.14031
DOI: 10.1007/978-3-030-85165-1_8
author: Koji Nuida
author: Yûji Hashimoto
publication date: 2022-03-24T00:00:00Z
review text: 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].
Mathematics Subject Classification ID: 14H52
Mathematics Subject Classification ID: 14K02
Mathematics Subject Classification ID: 94A60
zbMATH DE Number: 7497952
zbMATH Keywords: isogenies
zbMATH Keywords: supersingular elliptic curves
zbMATH Keywords: isogeny graphs
zbMATH Keywords: Legendre form
reviewed by: Juan Tena Ayuso
describes a project that uses: SIDH
MaRDI profile type: Publication
full work available at URL: 978-3-030-85165-1 8
OpenAlex ID: W3195859313
cites work: Legendre elliptic curves over finite fields
cites work: Class numbers of quadratic fields, Hasse invariants of elliptic curves, and the supersingular polynomial
cites work: CSIDH: an efficient post-quantum commutative group action
cites work: Cryptographic hash functions from expander graphs
cites work: Efficient Algorithms for Supersingular Isogeny Diffie-Hellman
cites work: Towards quantum-resistant cryptosystems from supersingular elliptic curve isogenies
cites work: Q4737492
cites work: Mathematics of public key cryptography.
cites work: Improved supersingularity testing of elliptic curves
cites work: Elliptic Curve Cryptosystems
cites work: Q3718617
cites work: An algorithm to compute volcanoes of 2-isogenies of elliptic curves over finite fields
cites work: Group Key Exchange from CSIDH and Its Application to Trusted Setup in Supersingular Isogeny Cryptosystems
cites work: Ramanujan graphs and Hecke operators
cites work: Q3710637
cites work: Computing Hilbert class polynomials with the Chinese remainder theorem
cites work: Identifying supersingular elliptic curves
cites work: Isogeny volcanoes
Recommended article: Identifying supersingular elliptic curves
Recommended article: Computing isogenies between supersingular elliptic curves over \(\mathbb {F}_p\)
Recommended article: An algorithm to compute volcanoes of 2-isogenies of elliptic curves over finite fields
Recommended article: On division polynomial PIT and supersingularity
Recommended article: Improved supersingularity testing of elliptic curves
Recommended article: Q4375597
Recommended article: Isogeny volcanoes
Recommended article: Computing isogeny volcanoes of composite degree
Recommended article: Pairing the volcano
Recommended article: Q3593461
description: scientific article; zbMATH DE number 7497952