Faster cofactorization with ECM using mixed representations


Set of blocks for stage 1 of ECM for B1 = 464
prime factors type cost acpb elliptic operations
DBLDBLεTPLTPLεADDADDεADDMdDBLdADD
337 · 227 · 127 · 73 · 67 · 17 · 72 C 242· 32−224−1 335 M 7.416 402211
439 · 211 · 107 · 83 · 37 · 19 · 11 · 7 C 239· 34+219· 32−1 338 M 7.455 372411
383 · 277 · 223 · 193 · 167 · 97 · 59 C 244· 35+240· 34+226+1 393 M 7.564 413521
379 · 367 · 331 · 317 · 173 · 113 C 229· 312−218· 39−1 364 M 7.580 2721211
409 · 349 · 313 · 271 · 257 · 181 · 157 · 11 C 255· 33−245· 3+220· 3+28· 3+1 454 M 7.598 514331
251 · 239 · 233 · 149 · 43 · 17 · 13 C 241· 32+225· 3+213· 3−1 336 M 7.607 383221
419 · 347 · 293 · 283 · 137 · 103 · 29 · 19 C 250· 34+248· 32+239· 32−227· 32−1 431 M 7.645 464431
457 · 443 · 401 · 281 · 61 C 234· 34−219· 33+25· 33−1 311 M 7.710 313421
311 · 269 · 131 · 31 C 222· 34+26· 32−1 219 M 7.728 202411
89 · 23 C 211−1 86 M 7.819 1011
433 · 431 C 28· 36−1 137 M 7.824 7161
389 · 179 C 216+212−1 129 M 8.019 14211
463 · 421 · 353 · 79 E 226· 34−28−33 249 M 7.699 2423111
359 · 263 · 241 · 191 · 109 · 47 E 238· 34+218+216· 34−3 343 M 7.736 3532221
307 · 199 · 101 · 71 · 53 E 217· 311+27+311 270 M 7.841 15210111
449 · 373 · 229 · 139 E 229· 32+229−222· 32+3 255 M 7.892 272221
461 · 397 · 197 · 151 E 226· 34+223+22· 33−1 257 M 7.946 2333121
switch to Montgomery, last ADDε is in fact a ADDM -4 M -11
35 M 55 M 6.940 55
53 M 51 M 7.322 36
13 M 29 M 7.837 14
163 · 41 M 109 M 8.578 514
28 M 40 M 5.000 8
Total 5187 M 7.638 48641647251612229

acpb = arithmetic cost per bit