Hone, Andrew N.W. (2020) Efficient ECM Factorization in Parallel with the Lyness Map. In: ISSAC '20: Proceedings of the 45th International Symposium on Symbolic and Algebraic Computation. . ACM ISBN 9781450371001. (doi:10.1145/3373207.3404044) (KAR id:81862)
PDF
Author's Accepted Manuscript
Language: English 

Download (750kB)
Preview

Preview 
This file may not be suitable for users of assistive technology.
Request an accessible format


Official URL: https://doi.org/10.1145/3373207.3404044 
Abstract
The Lyness map is a birational map in the plane which provides one of the simplest discrete analogues of a Hamiltonian system with one degree of freedom, having a conserved quantity and an invariant symplectic form. As an example of a symmetric QuispelRobertsThompson (QRT) map, each generic orbit of the Lyness map lies on a curve of genus one, and corresponds to a sequence of points on an elliptic curve which is one of the fibres in a pencil of biquadratic curves in the plane. Here we present a version of the elliptic curve method (ECM) for integer factorization, which is based on iteration of the Lyness map with a particular choice of initial data. More precisely, we give an algorithm for scalar multiplication of a point on an arbitrary elliptic curve over Q, which is represented by one of the curves in the Lyness pencil. In order to avoid field inversion (I), and require only field multiplication (M), squaring (S) and addition, projective coordinates in P1 × P1 are used. Neglecting multiplication by curve constants (assumed small), each addition of the chosen point uses 2M, while each doubling step requires 15M. We further show that the doubling step can be implemented efficiently in parallel with four processors, dropping the effective cost to 4M. In contrast, the fastest algorithms in the literature use twisted Edwards curves (equivalent to Montgomery curves), which correspond to a subset of all elliptic curves. Scalar muliplication on twisted Edwards curves with suitable small curve constants uses 8M for point addition and 4M+4S for point doubling, both of which can be run in parallel with four processors to yield effective costs of 2M and 1M + 1S, respectively. Thus our scalar multiplication algorithm should require, on average, roughly twice as many multiplications per bit as state of the art methods using twisted Edwards curves. In our conclusions, we discuss applications where the use of Lyness curves may provide potential advantages.
Item Type:  Conference or workshop item (Proceeding) 

DOI/Identification number:  10.1145/3373207.3404044 
Projects:  Cluster algebras with periodicity and discrete dynamics over finite fields, Generalized tau functions and cluster structures for birational difference equations 
Uncontrolled keywords:  Lyness map, elliptic curve method, scalar multiplication 
Subjects:  Q Science > QA Mathematics (inc Computing science) 
Divisions:  Divisions > Division of Computing, Engineering and Mathematical Sciences > School of Mathematics, Statistics and Actuarial Science 
Funders: 
Engineering and Physical Sciences Research Council (https://ror.org/0439y7842)
Royal Society (https://ror.org/03wnrjx87) 
Depositing User:  Andrew Hone 
Date Deposited:  25 Jun 2020 09:14 UTC 
Last Modified:  12 Jul 2022 10:41 UTC 
Resource URI:  https://kar.kent.ac.uk/id/eprint/81862 (The current URI for this page, for reference purposes) 
Hone, Andrew N.W.:  https://orcid.org/0000000197807369 
 Link to SensusAccess
 Export to:
 RefWorks
 EPrints3 XML
 BibTeX
 CSV
 Depositors only (login required):