Faster cofactorization with ECM using mixed representations


Set of blocks for stage 1 of ECM for B1 = 345
prime factors type cost acpb elliptic operations
DBLDBLεTPLTPLεADDADDεADDMdDBLdADD
331 · 151 · 31 · 11 · 7 · 32 C 230−1 219 M 7.300 2911
241 · 17 · 13 · 7 · 5 · 32 C 224−1 177 M 7.375 2311
337 · 269 · 199 · 73 · 11 C 229· 33−220· 32+1 256 M 7.584 272311
281 · 181 · 109 · 67 · 13 C 229· 32−220· 3−1 244 M 7.585 272211
271 · 157 · 107 · 83 · 79 · 59 C 228· 38−25· 32−1 309 M 7.596 262811
311 · 223 · 139 · 101 · 97 · 41 · 23 C 240· 34+219· 3+29· 3+1 353 M 7.618 373421
293 · 251 · 239 · 211 · 197 · 131 · 113 C 239· 39−236· 34−22· 3+1 406 M 7.622 363921
193 · 191 C 212· 32−1 117 M 7.713 11121
167 · 149 · 5 C 29· 35−1 132 M 7.799 8151
313 · 277 · 227 · 163 · 61 C 228· 36−29· 3−27+1 293 M 7.811 253621
257 · 233 · 229 · 173 · 29 C 223· 38+221· 38−25· 38+22· 34+1 290 M 8.055 194831
317 · 307 · 179 · 127 · 37 · 17 E 234· 34+219−32 305 M 7.561 3223111
283 · 263 · 137 · 103 · 53 · 47 · 43 · 19 E 243· 35−229· 3+213· 33+1 390 M 7.658 4033221
switch to Montgomery, last ADDε is in fact a ADDM -4 M -11
5 M 17 M 7.322 12
7 · 3 M 33 M 7.513 33
89 M 53 M 8.184 18
71 M 52 M 8.456 27
28 M 40 M 5.000 8
Total 3682 M 7.601 34028533151211520

acpb = arithmetic cost per bit