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.