Faster cofactorization with ECM using mixed representations


Set of blocks for stage 1 of ECM for B1 = 125
prime factors type cost acpb elliptic operations
DBLDBLεTPLTPLεADDADDεADDMdDBLdADD
109 · 73 · 37 · 19 · 13 · 7 · 5 · 33 C 236−1 261 M 7.250 3511
41 · 31 · 11 · 52 · 3 C 220−1 149 M 7.450 1911
113 · 107 · 97 · 89 · 67 · 61 · 47 · 43 · 17 · 7 C 247· 36+232· 35+227· 35−224· 34+219· 32−1 442 M 7.822 425641
53 · 29 C 29· 3+1 84 M 7.935 8111
101 · 83 · 79 C 213· 34−24· 34+1 156 M 8.067 112411
71 · 59 · 11 C 212· 32+210· 32−1 125 M 8.069 102211
switch to Montgomery, last ADDε is in fact a ADDM -4 M -11
103 M 57 M 8.525 37
23 M 39 M 8.622 34
26 M 30 M 5.000 6
Total 1339 M 7.646 12512136511211

acpb = arithmetic cost per bit