Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)

Request Permissions   Purchase Content 


Analogues of Vélu's formulas for isogenies on alternate models of elliptic curves

Authors: Dustin Moody and Daniel Shumow
Journal: Math. Comp. 85 (2016), 1929-1951
MSC (2010): Primary 14K02; Secondary 14H52, 11G05, 11Y16
Published electronically: September 9, 2015
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: Isogenies are the morphisms between elliptic curves and are, accordingly, a topic of interest in the subject. As such, they have been well studied, and have been used in several cryptographic applications. Vélu's formulas show how to explicitly evaluate an isogeny, given a specification of the kernel as a list of points. However, Vélu's formulas only work for elliptic curves specified by a Weierstrass equation. This paper presents formulas similar to Vélu's that can be used to evaluate isogenies on Edwards curves and Huff curves, which are normal forms of elliptic curves that provide an alternative to the traditional Weierstrass form. Our formulas are not simply compositions of Vélu's formulas with mappings to and from Weierstrass form. Our alternate derivation yields efficient formulas for isogenies with lower algebraic complexity than such compositions. In fact, these formulas have lower algebraic complexity than Vélu's formulas on Weierstrass curves.

References [Enhancements On Off] (What's this?)

Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2010): 14K02, 14H52, 11G05, 11Y16

Retrieve articles in all journals with MSC (2010): 14K02, 14H52, 11G05, 11Y16

Additional Information

Dustin Moody
Affiliation: Computer Security Division, National Institute of Standards and Technology (NIST), Gaithersburg, Maryland 20899

Daniel Shumow
Affiliation: Microsoft Research, Redmond, Washington 98052-6399

Keywords: Elliptic curve, Edwards curve, Huff curve
Received by editor(s): December 16, 2013
Received by editor(s) in revised form: July 10, 2014, and December 23, 2014
Published electronically: September 9, 2015
Article copyright: © Copyright 2015 American Mathematical Society