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 RSAbased 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 additionsubtracting chains which can be used to optimize Edwards ECM in terms of both performance and memory requirements. This makes our approach very suitable for memoryconstrained 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 stateoftheart 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 fullversion 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 additionsubtraction 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 lowstorage 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.
B1 
#M 
#S 
#(M+S) 
#R 
A 
D 
Download 
256, nostorage 
1400 
1444 
2844 
10 
38 
361 

256, lowstorage 
1383 
1448 
2831 
14 
35 
362 

512, nostorage 
2842 
2964 
5806 
10 
75 
741 

512, lowstorage 
2776 
2964 
5740 
18 
65 
741 

960, nostorage 
5224 
5484 
10708 
10 
135 
1371 

1024, nostorage 
5596 
5912 
11508 
10 
141 
1478 

1024, lowstorage 
5471 
5904 
11375 
18 
123 
1476 
