论文标题
与Lyness图并行的有效ECM分解
Efficient ECM factorization in parallel with the Lyness map
论文作者
论文摘要
Lyness图是平面中的一个生育图，它提供了具有一个自由度，具有保守数量和不变的符号形式的哈密顿系统最简单的离散类似物之一。作为对称的Quispel-Roberts-Thompson（QRT）映射的一个例子，Lyness图的每个通用轨道都在属的曲线上，对应于椭圆曲线上的点序列，该曲线是平面中二Quadratic曲线的纤维纤维中的纤维之一。在这里，我们提出了用于整数分解的椭圆曲线方法（ECM）的版本，该版本基于具有特定初始数据选择的Lyness Map的迭代。更确切地说，我们给出了一种用于椭圆曲线上点标量乘法的算法，该曲线由Lyness Pencile中的一条曲线表示。为了避免现场反转，仅需要字段乘法（$ {\ bf m} $），平方（$ {\ bf s} $）和加法，使用$ \ mathbb {p}^1 \ times \ times \ times \ times \ mathbb {p}^1 $的投射坐标。通过曲线常数忽略乘法（假定为小），所选点的每个添加都使用$ 2 {\ bf m} $，而每个双步骤均需$ 15 {\ bf m} $。我们进一步表明，可以与四个处理器并行有效地实现加倍步骤，从而将有效成本降至$ 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.因此，如果并行实施，我们的方法可能对整数分解或椭圆曲线加密具有潜在的优势。
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.
