Faster cofactorization with ECM using mixed representations


Set of blocks for stage 1 of ECM for B1 = 531
prime factors type cost acpb elliptic operations
DBLDBLεTPLTPLεADDADDεADDMdDBLdADD
227 · 73 · 67 · 17 C 221· 32+1 180 M 7.447 20121
503 · 449 · 113 · 59 · 53 · 31 C 238· 32−25· 32−1 307 M 7.457 362211
491 · 439 · 109 · 83 · 37 · 232 · 7 C 240· 35−222· 32+1 357 M 7.449 382511
499 · 467 · 421 · 197 C 231· 32−215· 32+1 258 M 7.551 292211
509 · 479 · 433 · 331 · 137 · 127 · 52 C 249· 33−228· 32−24· 32−1 404 M 7.516 463321
359 · 263 · 211 · 199 · 139 · 131 · 71 · 5 C 245· 36−238· 34+29· 34−1 412 M 7.558 423621
419 · 271 · 17 · 11 C 218· 34−1 183 M 7.519 17141
443 · 409 · 337 · 251 · 149 · 13 C 240· 33−223· 33+24+1 341 M 7.619 373321
233 · 191 · 173 · 157 C 227· 32+218· 3−1 230 M 7.623 252211
277 · 257 · 101 · 7 C 224· 3−210−1 197 M 7.700 222111
389 · 269 · 167 · 79 · 7 C 230· 32+213· 3−1 251 M 7.567 282211
521 · 383 · 373 · 97 · 43 C 235· 32+227· 32+28· 32+1 294 M 7.701 323221
487 · 353 · 311 · 241 C 232· 3−29−24+1 261 M 7.771 293121
367 · 349 · 281 · 179 C 231· 3−212−25+1 254 M 7.795 283121
151 · 103 C 26· 35+1 111 M 7.971 5151
463 · 401 · 193 C 214· 37+27· 32−1 199 M 7.930 122711
431 · 379 · 317 C 216· 36+214· 35+213· 3+1 209 M 8.156 133621
307 · 19 C 23· 36+1 102 M 8.153 2161
293 · 47 · 29 C 217· 3+211· 3−1 148 M 7.954 152111
397 · 313 · 223 · 107 · 11 E 227· 35+210+3 268 M 7.674 2524111
523 · 457 · 347 · 239 · 229 · 163 · 13 E 242· 37+236+22· 37+34 407 M 7.666 3935221
461 · 181 · 89 · 61 E 224· 33+214−33 223 M 7.755 2222111
switch to Montgomery, last ADDε is in fact a ADDM -4 M -11
3 M 11 M 6.940 11
3 M 11 M 6.940 11
33 M 33 M 6.940 33
19 M 35 M 8.239 15
41 M 46 M 8.586 26
283 M 70 M 8.595 210
29 M 45 M 5.000 9
Total 5843 M 7.635 56248724262111926

acpb = arithmetic cost per bit