Toric forms of elliptic curves and their arithmetic (Q548601)

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.