Faster cofactorization with ECM using mixed representations


Set of blocks for stage 1 of ECM for B1 = 626
prime factors type cost acpb elliptic operations
DBLDBLεTPLTPLεADDADDεADDMdDBLdADD
491 · 227 · 109 · 73 · 67 · 232 · 17 C 241· 35+220· 32−1 364 M 7.440 392511
617 · 347 · 331 · 167 · 83 · 17 C 236· 35+22+1 329 M 7.490 342511
503 · 449 · 113 · 59 · 53 · 31 C 238· 32−25· 32−1 307 M 7.457 362211
521 · 409 · 353 · 257 · 173 · 89 · 19 C 246· 34−239· 34+215· 32−1 395 M 7.548 433421
359 · 263 · 211 · 199 · 139 · 131 · 71 · 5 C 245· 36−238· 34+29· 34−1 412 M 7.558 423621
509 · 499 · 241 · 149 · 43 C 229· 36+228· 3+1 292 M 7.582 272611
571 · 487 · 307 · 293 · 11 C 238+228+212+1 291 M 7.658 35321
557 · 367 · 251 · 239 · 181 · 107 C 243· 33+225· 33+23· 33+1 362 M 7.580 403321
479 · 457 · 433 · 431 · 132 · 72 C 234· 39+226· 37+224· 3+1 371 M 7.687 313921
601 · 463 · 397 · 349 C 232· 32−225· 3+217−1 273 M 7.763 293221
229 · 179 · 97 C 214· 35−26· 34−1 175 M 7.983 122511
193 C 26· 3+1 63 M 8.298 5111
619 · 317 C 216· 3−27· 3−1 141 M 8.020 142111
563 · 541 · 467 · 419 · 373 · 197 · 137 · 47 · 37 · 29 E 262· 38−236−232· 38+38 557 M 7.459 5937121
607 · 599 · 523 · 461 · 379 · 277 · 79 E 253· 34−248· 32+216−34 448 M 7.550 5032221
443 · 233 · 163 · 157 · 127 · 7 E 230· 37+216−35 313 M 7.617 2826111
577 · 569 · 439 · 421 · 383 · 223 · 41 · 11 E 242· 312+26· 38+26+312 466 M 7.637 40210221
613 · 587 · 401 · 191 · 101 E 235· 34+227· 3−215−3 320 M 7.741 3233121
593 · 389 · 337 · 269 · 61 E 237· 32+232· 32+25−3 312 M 7.758 343221
313 · 281 · 151 · 103 E 224· 34+223+216· 32+34 245 M 8.073 2132221
311 · 283 · 271 E 215· 36−212· 32+29+3 206 M 8.406 1234221
switch to Montgomery, last ADDε is in fact a ADDM -4 M -11
3 M 11 M 6.940 11
32 M 22 M 6.940 22
5 · 32 M 39 M 7.101 34
52 M 34 M 7.322 24
19 M 35 M 8.239 15
547 M 77 M 8.466 112
29 M 45 M 5.000 9
Total 6901 M 7.622 663538313332011928

acpb = arithmetic cost per bit