Toric forms of elliptic curves and their arithmetic
type: Item
instance of: scholarly article
title: Toric forms of elliptic curves and their arithmetic
zbMATH Open document ID: 1228.14024
author: Wouter Castryck
author: Frederik Vercauteren
published in: Journal of Symbolic Computation
publication date: 2011-06-29T00:00:00Z
review text: Since the discovery of the elliptic curve factorization method [\textit{H. W. Lenstra jun.}, Ann. Math. (2) 126, 649--673 (1987; Zbl 0629.10006)] and the introduction of elliptic curve cryptography by \textit{V. S. Miller} [in: Advances in Cryptology -- Crypto'85, Springer-Verlag, Lect. Notes Comput. Sci. 218, 417--426 (1986; Zbl 0589.94005)] and \textit{N. Koblitz} [Math. Comput. 48, 203--209 (1987; Zbl 0622.94015)], there has been a continuous interest in speeding up addition/doubling and (multi)-scalar multiplication on elliptic curves. The goal of this paper is to provide new forms of equations of elliptic curves leading to efficient arithmetic. The paper analyzes a large class of forms over a field of sufficiently large characteristic. The class is inspired by classical results from toric geometry that give a natural classification of elliptic curves based on the Newton polytope of the defining polynomial. The class consists of over 50\,000 one-parameter families of elliptic curves, all of which were scanned for efficient arithmetic by using an algorithm that combines interpolation techniques and lattice reduction. As a conclusion, some optimality results on Edwards and Montgomery doubling are presented and it is illustrated how toric geometry might serve as a source of inspiration in finding good projective coordinate systems and in finding elliptic curve shapes allowing for complete group operation formulas.
Mathematics Subject Classification ID: 14G50
Mathematics Subject Classification ID: 14H52
Mathematics Subject Classification ID: 14Q05
Mathematics Subject Classification ID: 11G20
zbMATH DE Number: 5915027
zbMATH Keywords: elliptic curve
zbMATH Keywords: cryptography
zbMATH Keywords: Newton polytope
zbMATH Keywords: toric geometry
reviewed by: Enric Nart
describes a project that uses: EFD
describes a project that uses: Curve25519
describes a project that uses: Magma
MaRDI profile type: Publication
full work available at URL: j.jsc.2011.02.003
OpenAlex ID: W2078045580
cites work: Q3533253
cites work: Variations of the mixed Hodge structure of affine hypersurfaces in algebraic tori
cites work: A generalization of Baker's theorem
cites work: Public Key Cryptography - PKC 2006
cites work: Twisted Edwards Curves
cites work: Faster Addition and Doubling on Elliptic Curves
cites work: Q4426682
cites work: The Magma algebra system. I: The user language
cites work: Q3043950
cites work: A Shortened Classical Proof of the Quadratic Reciprocity Law
cites work: Computing zeta functions of nondegenerate curves
cites work: The distribution of the number of points modulo an integer on elliptic curves over finite fields
cites work: Sequences of numbers generated by addition in formal groups and new primality and factorization tests
cites work: Handbook of Elliptic and Hyperelliptic Curve Cryptography
cites work: Q4249254
cites work: Q4669638
cites work: The arithmetic of characteristic 2 Kummer surfaces and of elliptic Kummer lines
cites work: Q4293510
cites work: Q4002797
cites work: Q4370894
cites work: New Formulae for Efficient Elliptic Curve Arithmetic
cites work: Twisted Edwards Curves Revisited
cites work: Q4169005
cites work: Q4797815
cites work: The resultant of an unmixed bivariate system
cites work: Elliptic Curve Cryptosystems
cites work: A criterion for the ideal of a projectively embedded toric surface to be generated by quadrics
cites work: Factoring integers with elliptic curves
cites work: Q4797814
cites work: Q3718617
cites work: Rational simplification modulo a polynomial ideal
cites work: Speeding the Pollard and Elliptic Curve Methods of Factorization
cites work: Q4950049
cites work: Lattice Polygons and the Number 12
cites work: On the number of distinct elliptic curves in some families
cites work: Q4797388
cites work: Q3596012
DOI: 10.1016/J.JSC.2011.02.003
description: scientific article; zbMATH DE number 5915027