Optimal parameters for ECM

ECM is a probabilistic algorithm. Its probability of success depends on the size of the (usually unknown) factor p to be found, on the step 1 and 2 bounds B1 and B2, and possibly on some other implementation-dependent parameters.

The table below indicates for each factor size what is the optimal step 1 limit B1 to use (first argument of the GMP-ECM program). The column "expected curves" corresponds to the default parameters of GMP-ECM. Those figures can be reproduced using the -v option of GMP-ECM.

digits optimal B1 expected curves
(default parameters for GMP-ECM 6)		 expected curves
(default parameters for GMP-ECM 7)
20 11,000 86107
25 50,000 214261
30 250,000 430513
35 1,000,000 9101,071
40 3,000,000 2,3512,753
45 11,000,000 4,4825,208
50 43,000,000 7,5578,704
55 110,000,000 17,88420,479
60 260,000,000 42,05747,888
65 850,000,000 69,47178,923
70 2,900,000,000 102,212115,153
75 7,600,000,000 188,056211,681
80 25,000,000,000 265,557296,479
Please note that one run of the program performs one curve. For example, if you want to find factors up to 20 digits long, it is reasonable to do up to 86 runs with B1=11,000 (or 107 runs with GMP-ECM 7). If that fails, the probability it remains a factor of 20 digits is about exp(-1) = 0.37, and you can increase B1 to 50,000, and so on.

Update June 5, 2019: Pierrick Gaudry computed experimentally optimal parameters with GMP-ECM 7 (using the output of ecm -v) for a 512-bit input, and for factor size from 30 to 225 bits, by steps of 5 bits. The optimal B1 values he found below follow a regression of the form log(B1) = a*bits+b, with a = 0.0750 and b = 5.332. and the corresponding total effort (B1 times number of curves) follows a regression of the form log(B1*ncurves) = d*bits2+e*bits+f, with d = -0.000203, e = 0.177 and f = 3.097. In terms of the number of curves, one seems to have B1 = 150*ncurves1.5. This table, where the B1 values grow more quickly than in the above one, should be considered as more accurate. The above table is kept for reference.

bits optimal B1 expected curves
30 1358 2
35 1270 5
40 1629 10
45 4537 10
50 12322 9
55 12820 18
60 21905 21
65 24433 41
70 32918 66
75 64703 71
80 76620 119
85 155247 123
90 183849 219
95 245335 321
100 445657 339
105 643986 468
110 1305195 439
115 1305195 818
120 3071166 649
125 3784867 949
130 4572523 1507
135 7982718 1497
140 9267681 2399
145 22025673 1826
150 22025673 3159
155 26345943 4532
160 35158748 6076
165 46919468 8177
170 47862548 14038
175 153319098 7166
180 153319098 12017
185 188949210 16238
190 410593604 13174
195 496041799 17798
200 491130495 29584
205 1067244762 23626
210 1056677983 38609
215 1328416470 49784
220 1315263832 81950
225 2858117139 63461