{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,28]],"date-time":"2026-06-28T07:20:25Z","timestamp":1782631225183,"version":"3.54.5"},"reference-count":37,"publisher":"American Mathematical Society (AMS)","issue":"300","license":[{"start":{"date-parts":[[2016,9,9]],"date-time":"2016-09-09T00:00:00Z","timestamp":1473379200000},"content-version":"am","delay-in-days":366,"URL":"https:\/\/www.ams.org\/publications\/copyright-and-permissions"}],"funder":[{"DOI":"10.13039\/100006112","name":"Microsoft Research","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100006112","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Math. Comp."],"abstract":"<p>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\u00e9lu\u2019s formulas show how to explicitly evaluate an isogeny, given a specification of the kernel as a list of points. However, V\u00e9lu\u2019s formulas only work for elliptic curves specified by a Weierstrass equation. This paper presents formulas similar to V\u00e9lu\u2019s 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\u00e9lu\u2019s 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\u00e9lu\u2019s formulas on Weierstrass curves.<\/p>","DOI":"10.1090\/mcom\/3036","type":"journal-article","created":{"date-parts":[[2015,9,9]],"date-time":"2015-09-09T11:41:02Z","timestamp":1441798862000},"page":"1929-1951","source":"Crossref","is-referenced-by-count":55,"title":["Analogues of V\u00e9lu\u2019s formulas for isogenies on alternate models of elliptic curves"],"prefix":"10.1090","volume":"85","author":[{"given":"Dustin","family":"Moody","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Daniel","family":"Shumow","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"14","published-online":{"date-parts":[[2015,9,9]]},"reference":[{"issue":"6","key":"1","doi-asserted-by":"publisher","first-page":"1337","DOI":"10.1016\/j.jnt.2011.12.013","article-title":"On isogeny classes of Edwards curves over finite fields","volume":"132","author":"Ahmadi, Omran","year":"2012","journal-title":"J. Number Theory","ISSN":"https:\/\/id.crossref.org\/issn\/0022-314X","issn-type":"print"},{"key":"2","isbn-type":"print","doi-asserted-by":"publisher","first-page":"389","DOI":"10.1007\/978-3-540-68164-9_26","article-title":"Twisted Edwards curves","author":"Bernstein, Daniel J.","year":"2008","ISBN":"https:\/\/id.crossref.org\/isbn\/9783540681595"},{"key":"3","isbn-type":"print","doi-asserted-by":"publisher","first-page":"29","DOI":"10.1007\/978-3-540-76900-2_3","article-title":"Faster addition and doubling on elliptic curves","author":"Bernstein, Daniel J.","year":"2007","ISBN":"https:\/\/id.crossref.org\/isbn\/9783540768999"},{"issue":"5","key":"4","doi-asserted-by":"publisher","first-page":"815","DOI":"10.1016\/j.jnt.2009.11.003","article-title":"Computing the endomorphism ring of an ordinary elliptic curve over a finite field","volume":"131","author":"Bisson, Gaetan","year":"2011","journal-title":"J. Number Theory","ISSN":"https:\/\/id.crossref.org\/issn\/0022-314X","issn-type":"print"},{"issue":"263","key":"5","doi-asserted-by":"publisher","first-page":"1755","DOI":"10.1090\/S0025-5718-08-02066-8","article-title":"Fast algorithms for computing isogenies between elliptic curves","volume":"77","author":"Bostan, A.","year":"2008","journal-title":"Math. Comp.","ISSN":"https:\/\/id.crossref.org\/issn\/0025-5718","issn-type":"print"},{"key":"6","isbn-type":"print","doi-asserted-by":"publisher","first-page":"100","DOI":"10.1007\/978-3-540-85538-5_7","article-title":"Evaluating large degree isogenies and applications to pairing based cryptography","author":"Br\u00f6ker, Reinier","year":"2008","ISBN":"https:\/\/id.crossref.org\/isbn\/9783540855033"},{"issue":"278","key":"7","doi-asserted-by":"publisher","first-page":"1201","DOI":"10.1090\/S0025-5718-2011-02508-1","article-title":"Modular polynomials via isogeny volcanoes","volume":"81","author":"Br\u00f6ker, Reinier","year":"2012","journal-title":"Math. Comp.","ISSN":"https:\/\/id.crossref.org\/issn\/0025-5718","issn-type":"print"},{"issue":"1","key":"8","doi-asserted-by":"publisher","first-page":"93","DOI":"10.1007\/s00145-007-9002-x","article-title":"Cryptographic hash functions from expander graphs","volume":"22","author":"Charles, Denis X.","year":"2009","journal-title":"J. Cryptology","ISSN":"https:\/\/id.crossref.org\/issn\/0933-2790","issn-type":"print"},{"key":"9","unstructured":"H. Debiao, C. Jianhua, and H. Jin, A random number generator based on isogenies operations, Cryptology ePrint Archive Report 2010\/94, (2010). Available at \\url{http:\/\/eprint.iacr.org\/2010\/094}."},{"key":"10","unstructured":"L. De Feo, Algorithmes rapides pour les tours de corps finis et les isogenies, PhD thesis. Ecole Polytechnique X, (2010)."},{"key":"11","isbn-type":"print","doi-asserted-by":"publisher","first-page":"191","DOI":"10.1007\/11745853_13","article-title":"Efficient scalar multiplication by isogeny decompositions","author":"Doche, Christophe","year":"2006","ISBN":"https:\/\/id.crossref.org\/isbn\/9783540338512"},{"issue":"3","key":"12","doi-asserted-by":"publisher","first-page":"393","DOI":"10.1090\/S0273-0979-07-01153-6","article-title":"A normal form for elliptic curves","volume":"44","author":"Edwards, Harold M.","year":"2007","journal-title":"Bull. Amer. Math. Soc. (N.S.)","ISSN":"https:\/\/id.crossref.org\/issn\/0273-0979","issn-type":"print"},{"key":"13","isbn-type":"print","doi-asserted-by":"publisher","first-page":"21","DOI":"10.1090\/amsip\/007\/03","article-title":"Elliptic and modular curves over finite fields and related computational issues","author":"Elkies, Noam D.","year":"1998","ISBN":"https:\/\/id.crossref.org\/isbn\/082180880X"},{"key":"14","unstructured":"R. Farashahi, On the number of distinct Legendre, Jacobi, Hessian and Edwards curves (Extended Abstract), in: Proceedings of the Workshop on Coding theory and Cryptology (WCC 2011), pp. 37\u201346, (2011). Available at \\url{hal.inria.fr\/docs\/00\/60\/72\/79\/PDF\/76.pdf}."},{"issue":"3","key":"15","doi-asserted-by":"publisher","first-page":"597","DOI":"10.1016\/j.ffa.2011.12.004","article-title":"Isomorphism classes of Edwards curves over finite fields","volume":"18","author":"Rezaeian Farashahi, Reza","year":"2012","journal-title":"Finite Fields Appl.","ISSN":"https:\/\/id.crossref.org\/issn\/1071-5797","issn-type":"print"},{"issue":"1","key":"16","doi-asserted-by":"publisher","first-page":"83","DOI":"10.1007\/s10623-009-9310-2","article-title":"On the number of distinct elliptic curves in some families","volume":"54","author":"Farashahi, Reza Rezaeian","year":"2010","journal-title":"Des. Codes Cryptogr.","ISSN":"https:\/\/id.crossref.org\/issn\/0925-1022","issn-type":"print"},{"key":"17","unstructured":"R. Feng, and H. Wu, Elliptic curves in Huff\u2019s model, Cryptology ePrint Archive Report 2010\/390, (2010). Available at \\url{http:\/\/eprint.iacr.org\/2010\/390.pdf}."},{"key":"18","isbn-type":"print","doi-asserted-by":"publisher","first-page":"276","DOI":"10.1007\/3-540-45455-1_23","article-title":"Isogeny volcanoes and the SEA algorithm","author":"Fouquet, Mireille","year":"2002","ISBN":"https:\/\/id.crossref.org\/isbn\/3540438637"},{"key":"19","unstructured":"L. Hitt, G. Mcguire, and R. Moloney, Division polynomials for twisted Edwards curves, Preprint, (2008). Available at \\url{http:\/\/arxiv.org\/pdf\/0907.4347v1.pdf}."},{"key":"20","first-page":"443","article-title":"Diophantine problems in geometry and elliptic ternary forms","volume":"15","author":"Huff, Gerald B.","year":"1948","journal-title":"Duke Math. J.","ISSN":"https:\/\/id.crossref.org\/issn\/0012-7094","issn-type":"print"},{"key":"21","isbn-type":"print","doi-asserted-by":"publisher","first-page":"19","DOI":"10.1007\/978-3-642-25405-5_2","article-title":"Towards quantum-resistant cryptosystems from supersingular elliptic curve isogenies","author":"Jao, David","year":"2011","ISBN":"https:\/\/id.crossref.org\/isbn\/9783642254055"},{"key":"22","isbn-type":"print","doi-asserted-by":"publisher","first-page":"21","DOI":"10.1007\/11593447_2","article-title":"Do all elliptic curves of the same order have the same difficulty of discrete log?","author":"Jao, David","year":"2005","ISBN":"https:\/\/id.crossref.org\/isbn\/9783540306849"},{"key":"23","isbn-type":"print","doi-asserted-by":"publisher","first-page":"219","DOI":"10.1007\/978-3-642-14518-6_19","article-title":"A subexponential algorithm for evaluating large degree isogenies","author":"Jao, David","year":"2010","ISBN":"https:\/\/id.crossref.org\/isbn\/9783642145179"},{"key":"24","isbn-type":"print","doi-asserted-by":"publisher","first-page":"234","DOI":"10.1007\/978-3-642-14518-6_20","article-title":"Huff\u2019s model for elliptic curves","author":"Joye, Marc","year":"2010","ISBN":"https:\/\/id.crossref.org\/isbn\/9783642145179"},{"issue":"5-6","key":"25","doi-asserted-by":"publisher","first-page":"321","DOI":"10.1007\/s00200-011-0153-5","article-title":"Two kinds of division polynomials for twisted Edwards curves","volume":"22","author":"Moloney, Richard","year":"2011","journal-title":"Appl. Algebra Engrg. Comm. Comput.","ISSN":"https:\/\/id.crossref.org\/issn\/0938-1279","issn-type":"print"},{"key":"26","isbn-type":"print","volume-title":"Endomorphism rings of elliptic curves over finite fields","author":"Kohel, David Russell","year":"1996","ISBN":"https:\/\/id.crossref.org\/isbn\/9780591321234"},{"key":"27","isbn-type":"print","doi-asserted-by":"publisher","first-page":"77","DOI":"10.1090\/amsip\/007\/04","article-title":"Algorithms for computing isogenies between elliptic curves","author":"Lercier, R.","year":"1998","ISBN":"https:\/\/id.crossref.org\/isbn\/082180880X"},{"issue":"7","key":"28","doi-asserted-by":"publisher","first-page":"314","DOI":"10.1016\/j.ipl.2010.12.014","article-title":"Using 5-isogenies to quintuple points on elliptic curves","volume":"111","author":"Moody, Dustin","year":"2011","journal-title":"Inform. Process. Lett.","ISSN":"https:\/\/id.crossref.org\/issn\/0020-0190","issn-type":"print"},{"key":"29","unstructured":"A. Rostovtsev and A. Stolbunov, Public-key cryptosystem based on isogenies, Cryptology ePrint Archive, Report 2006\/145, (2006). Available at \\url{http:\/\/eprint.iacr.org\/2006\/145}."},{"key":"30","unstructured":"D. Shumow, Isogenies of elliptic curves: A computational approach, Masters Thesis, University of Washington, (2009)."},{"key":"31","series-title":"Graduate Texts in Mathematics","isbn-type":"print","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4757-1920-8","volume-title":"The arithmetic of elliptic curves","volume":"106","author":"Silverman, Joseph H.","year":"1986","ISBN":"https:\/\/id.crossref.org\/isbn\/0387962034"},{"issue":"170","key":"32","doi-asserted-by":"publisher","first-page":"483","DOI":"10.2307\/2007968","article-title":"Elliptic curves over finite fields and the computation of square roots mod \ud835\udc5d","volume":"44","author":"Schoof, Ren\u00e9","year":"1985","journal-title":"Math. Comp.","ISSN":"https:\/\/id.crossref.org\/issn\/0025-5718","issn-type":"print"},{"issue":"2","key":"33","doi-asserted-by":"publisher","first-page":"215","DOI":"10.3934\/amc.2010.4.215","article-title":"Constructing public-key cryptographic schemes based on class group action on a set of isogenous elliptic curves","volume":"4","author":"Stolbunov, Anton","year":"2010","journal-title":"Adv. Math. Commun.","ISSN":"https:\/\/id.crossref.org\/issn\/1930-5346","issn-type":"print"},{"issue":"273","key":"34","doi-asserted-by":"publisher","first-page":"501","DOI":"10.1090\/S0025-5718-2010-02373-7","article-title":"Computing Hilbert class polynomials with the Chinese remainder theorem","volume":"80","author":"Sutherland, Andrew V.","year":"2011","journal-title":"Math. Comp.","ISSN":"https:\/\/id.crossref.org\/issn\/0025-5718","issn-type":"print"},{"issue":"1","key":"35","doi-asserted-by":"publisher","first-page":"115","DOI":"10.1007\/s00145-004-0328-3","article-title":"An elliptic curve trapdoor system","volume":"19","author":"Teske, Edlyn","year":"2006","journal-title":"J. Cryptology","ISSN":"https:\/\/id.crossref.org\/issn\/0933-2790","issn-type":"print"},{"key":"36","first-page":"A238--A241","article-title":"Isog\u00e9nies entre courbes elliptiques","volume":"273","author":"V\u00e9lu, Jacques","year":"1971","journal-title":"C. R. Acad. Sci. Paris S\\'{e}r. A-B","ISSN":"https:\/\/id.crossref.org\/issn\/0151-0509","issn-type":"print"},{"key":"37","series-title":"Discrete Mathematics and its Applications (Boca Raton)","isbn-type":"print","doi-asserted-by":"publisher","DOI":"10.1201\/9781420071474","volume-title":"Elliptic curves","author":"Washington, Lawrence C.","year":"2008","ISBN":"https:\/\/id.crossref.org\/isbn\/9781420071467","edition":"2"}],"container-title":["Mathematics of Computation"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/www.ams.org\/mcom\/2016-85-300\/S0025-5718-2015-03036-1\/S0025-5718-2015-03036-1.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"},{"URL":"https:\/\/www.ams.org\/mcom\/2016-85-300\/S0025-5718-2015-03036-1\/S0025-5718-2015-03036-1.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,21]],"date-time":"2026-04-21T18:49:47Z","timestamp":1776797387000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.ams.org\/mcom\/2016-85-300\/S0025-5718-2015-03036-1\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,9,9]]},"references-count":37,"journal-issue":{"issue":"300","published-print":{"date-parts":[[2016,7]]}},"alternative-id":["S0025-5718-2015-03036-1"],"URL":"https:\/\/doi.org\/10.1090\/mcom\/3036","archive":["CLOCKSS","Portico"],"relation":{},"ISSN":["1088-6842","0025-5718"],"issn-type":[{"value":"1088-6842","type":"electronic"},{"value":"0025-5718","type":"print"}],"subject":[],"published":{"date-parts":[[2015,9,9]]}}}