Faster cofactorization with ECM using mixed representations


Set of blocks for stage 1 of ECM for B1 = 1021
prime factors type cost acpb elliptic operations
DBLDBLεTPLTPLεADDADDεADDMdDBLdADD
911 · 787 · 307 · 157 · 149 · 41 C 246· 3+225· 3−1 351 M 7.376 442111
821 · 641 · 557 · 179 · 139 · 107 · 83 · 59 · 29 C 265· 3+257−1 484 M 7.269 632111
673 · 257 · 97 C 224+1 177 M 7.375 2311
601 · 577 · 349 · 79 · 73 · 23 · 13 · 7 · 52 C 236· 312−1 405 M 7.361 351121
953 · 661 · 383 · 223 · 137 · 47 · 13 C 252+217+29−1 389 M 7.481 49321
769 · 607 · 331 · 281 · 181 · 17 C 239· 35+223· 33+1 350 M 7.459 372511
983 · 857 · 653 · 571 · 431 · 271 · 191 · 312 C 263· 36+260· 32−242· 3−1 538 M 7.419 603621
1013 · 929 · 823 · 563 · 109 · 61 · 53 · 29 · 112 · 7 C 259· 38−258· 33+249· 33−1 534 M 7.450 563821
839 · 587 · 523 · 521 · 229 · 211 · 101 · 192 C 255· 38+255+22+1 507 M 7.491 5327121
1009 · 947 · 881 · 877 · 797 · 389 · 17 C 257· 33−233· 33−219· 33−23· 32−1 468 M 7.578 534331
499 · 467 · 421 · 197 C 231· 32−215· 32+1 258 M 7.551 292211
1019 · 887 · 811 · 541 · 379 C 236· 37+222· 37−210· 34+1 361 M 7.665 333721
463 · 439 · 347 · 227 · 103 C 239· 3−226· 3+27−1 310 M 7.638 363121
967 · 827 · 719 · 683 · 113 C 239· 34−234· 32+229· 3+1 346 M 7.632 363421
1021 · 647 · 283 · 7 C 227· 32+225· 3−1 230 M 7.594 252211
941 · 907 · 733 · 619 · 419 · 151 · 67 C 251· 36−228−222+212−1 462 M 7.635 474631
739 · 677 · 457 · 367 · 199 C 236· 35−223· 34+210· 34−1 337 M 7.672 333521
991 · 937 · 809 · 659 · 599 · 443 · 409 · 127 C 244· 318+239· 315−217· 35−24−1 557 M 7.679 4041831
487 · 317 · 163 C 223· 3−211+1 190 M 7.728 212111
761 · 479 · 233 C 220· 34−26· 33−1 205 M 7.783 182411
743 · 359 · 337 · 71 · 23 C 226· 37+215· 36−25· 33+1 291 M 7.845 233721
883 · 503 · 293 · 167 C 228· 34−217· 34−27· 3−1 269 M 7.834 253421
643 · 631 · 593 · 547 C 229· 35+222· 35+219· 35+216· 33−1 296 M 8.014 254531
997 · 727 · 691 · 313 C 234· 32+231−218−214+1 295 M 7.932 304231
919 · 397 · 131 C 216· 36+211· 32+28+1 209 M 8.193 133621
701 · 269 C 28· 36+23· 35+1 145 M 8.274 62611
613 · 311 · 251 C 216· 36+213· 32+211−27+1 217 M 8.506 124631
971 · 751 · 461 · 433 · 353 · 277 · 173 E 250· 37−215· 34+26· 37+1 463 M 7.578 4735221
853 · 773 · 617 · 569 · 509 · 43 E 249· 32−227· 32−27−32 394 M 7.552 4631121
757 · 401 · 239 · 37 E 228· 32+228−32 238 M 7.599 2711111
863 · 829 · 491 · 263 · 241 E 238· 34−228−214· 33−32 343 M 7.736 3532221
977 · 449 · 373 · 89 E 229· 33+226+212−3 266 M 7.879 2632121
859 · 193 E 211· 34−27+33 144 M 8.305 923111
switch to Montgomery, last ADDε is in fact a ADDM -4 M -11
36 M 66 M 6.940 66
52 M 34 M 7.322 24
709 M 82 M 8.659 212
29 M 45 M 5.000 9
Total 11252 M 7.614 1115891439583211922

acpb = arithmetic cost per bit