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) to find a factor of a given number of bits, with the corresponding number of expected curves. These data were computed experimentally by Pierrick in June 2019 with GMP-ECM 7 (using the output of ecm -v) for a 512-bit input. 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 as the table below, which is kept for reference.
bits digits optimal B1 expected curves
30 9 1358 2
35 11 1270 5
40 12 1629 10
45 14 4537 10
50 15 12322 9
55 17 12820 18
60 18 21905 21
65 20 24433 41
70 21 32918 66
75 23 64703 71
80 24 76620 119
85 26 155247 123
90 27 183849 219
95 29 245335 321
100 30 445657 339
105 32 643986 468
110 33 1305195 439
115 35 1305195 818
120 36 3071166 649
125 38 3784867 949
130 39 4572523 1507
135 41 7982718 1497
140 42 9267681 2399
145 44 22025673 1826
150 46 22025673 3159
155 47 26345943 4532
160 49 35158748 6076
165 50 46919468 8177
170 52 47862548 14038
175 53 153319098 7166
180 55 153319098 12017
185 56 188949210 16238
190 58 410593604 13174
195 59 496041799 17798
200 61 491130495 29584
205 62 1067244762 23626
210 64 1056677983 38609
215 65 1328416470 49784
220 67 1315263832 81950
225 68 2858117139 63461
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.