Share on Facebook Tweet on Twitter Share on LinkedIn Share by email
ECM at Work

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.

 

B1 

#M

#S

#(M+S)

#R

A

D

Download

256, no-storage 

1400

1444

2844

10

38

361

file

256, low-storage 

1383

1448

2831

14

35

362

file

512, no-storage 

2842

2964

5806

10

75

741

file

512, low-storage 

2776

2964

5740

18

65

741

file

960, no-storage 

5224

5484

10708

10

135

1371

file

1024, no-storage 

5596

5912

11508

10

141

1478

file

1024, low-storage 

5471

5904

11375

18

123

1476

file