Efficient ECM factorization in parallel with the Lyness map
This work addresses the need for efficient and broadly applicable algorithms in integer factorization and cryptography, though it is incremental as it builds on existing elliptic curve methods with a novel parallel implementation.
The authors tackled the problem of integer factorization and elliptic curve cryptography by developing a scalar multiplication algorithm based on the Lyness map, achieving an effective cost of 4 multiplications per doubling step when implemented in parallel with four processors, compared to 15 multiplications in serial. This method applies to any elliptic curve over rational numbers, unlike some state-of-the-art methods limited to specific curve types.
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 Quispel-Roberts-Thompson (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 elliptic curve, which is represented by one of the curves in the Lyness pencil. In order to avoid field inversion, and require only field multiplication (${\bf M}$), squaring (${\bf S}$) and addition, projective coordinates in $\mathbb{P}^1 \times \mathbb{P}^1$ are used. Neglecting multiplication by curve constants (assumed small), each addition of the chosen point uses $2{\bf M}$, while each doubling step requires $15{\bf M}$. We further show that the doubling step can be implemented efficiently in parallel with four processors, dropping the effective cost to $4{\bf M}$. Our scalar multiplication algorithm should require, on average, roughly twice as many multiplications per bit as the fastest state of the art methods using twisted Edwards curves with small constants, but it can be applied to any elliptic curve over $\mathbb{Q}$, whereas twisted Edwards curves (equivalent to Montgomery curves) correspond to only a subset of all elliptic curves. Hence, if implemented in parallel, our method may have potential advantages for integer factorization or elliptic curve cryptography.