by Joppe W. Bos and Thorsten Kleinjung

Abstract. The performance of the elliptic curve method (ECM) for integer factorization plays an important role in the security assessment of RSA-based protocols as a cofactorization tool inside the number field sieve. The efficient arithmetic for Edwards curves found an application by speeding up ECM. This webpage gives addition-subtracting chains which can be used to optimize Edwards ECM in terms of both performance and memory requirements. This makes our approach very suitable for memory-constrained devices such as graphics processing units (GPU). For commonly used ECM parameters we are able to lower the required memory up to a factor 55 compared to the state-of-the-art Edwards ECM approach. Our ECM implementation on a GTX 580 GPU sets a new throughput record, outperforming the best GPU, CPU and FPGA results reported in literature.
See for more details the full-version of our Asiacrypt 2012 paper.

Below a table summarizing our best chains found. The table shows the number of modular multiplications (#M) and squarings (#S) required to calculate A elliptic curve additions and D duplications for various B1 parameters when factoring an integer n with ECM using "a=-1" twisted Edwards curves. The memory required is expressed as the number of residues (#R), integers modulo n, which are kept in memory.

The format of the addition-subtraction chains is almost the same as described in our paper. The only difference are the indices of additions and subtractions: the symbol A_j (resp. S_j) of the file corresponds to A_{i_j} (resp. S_{i_j}) of the paper. Consider for example line 6 of the 256 low-storage file:

211 173 139 103 71 61 #41D+5A: S_1 D^3 A_3 D^4 A_1 D^16 S_0 D^13 S_0 D^5

Beginning at the right with a_0=1 we first compute
a_1=(2^5*a_0)-a_0=31 (S_0 D^5)
next
a_2=(2^13*a_1)-a_0=253951 (S_0 D^13)
next
a_3=(2^16*a2)+a_1=16642932767 (A_1 D^16)
next
a_4=(2^4*a_3)+a_3=282929857039 (A_3 D^4)
and finally
a_5=(2^3*a_4)-a_1=2263438856281 (S_1 D^3)
which is 211*173*139*103*71*61.