Faster cofactorization with ECM using mixed representations


Set of blocks for stage 1 of ECM for B1 = 990
prime factors type cost acpb elliptic operations
DBLDBLεTPLTPLεADDADDεADDMdDBLdADD
593 · 269 · 157 · 101 · 53 · 232 C 246+239+1 339 M 7.368 44211
809 · 643 · 541 · 307 · 197 · 67 · 5 C 246· 34+236· 33−1 387 M 7.394 442411
983 · 857 · 653 · 571 · 431 · 271 · 191 · 312 C 263· 36+260· 32−242· 3−1 538 M 7.419 603621
769 · 607 · 331 · 281 · 181 · 17 C 239· 35+223· 33+1 350 M 7.459 372511
673 · 257 · 97 C 224+1 177 M 7.375 2311
761 · 659 · 619 · 139 · 43 C 236· 33+219· 3+1 305 M 7.484 342311
907 · 383 · 163 C 221· 33−1 192 M 7.455 20131
739 · 439 · 367 · 179 · 173 · 107 C 239· 36−233· 36−1 362 M 7.466 372611
691 · 613 · 263 · 239 · 233 · 131 · 19 · 7 C 255· 3+230· 3−224· 3+1 422 M 7.458 523121
751 · 733 · 349 · 151 C 230· 33+221· 32+1 263 M 7.567 282311
661 · 277 · 241 · 73 C 230· 3+24· 3+1 239 M 7.567 282111
977 · 467 · 421 · 353 · 347 · 19 · 17 C 248· 33−231· 33+215· 32−1 397 M 7.525 453321
337 · 127 · 72 C 221−1 156 M 7.429 2011
947 · 829 · 757 · 601 · 311 · 227 · 71 · 47 C 244· 314−226· 311+26· 38−1 501 M 7.569 4131421
853 · 647 · 599 · 509 · 223 C 234· 37−226· 36+28· 33−1 347 M 7.695 313721
709 · 503 · 283 C 225· 3+218+1 204 M 7.672 232111
641 · 631 · 443 · 397 · 313 C 238· 34+221· 33+212· 32+1 339 M 7.645 353421
967 · 827 · 719 · 683 · 113 C 239· 34−234· 32+229· 3+1 346 M 7.632 363421
839 · 787 · 521 · 167 · 109 C 233· 36+29· 32+27· 3−1 328 M 7.716 303621
911 · 877 · 547 · 199 C 230· 34−216· 34−29· 3−1 283 M 7.788 273421
941 · 463 · 389 · 137 C 217· 311−23· 39−1 268 M 7.783 1521111
971 · 823 · 401 · 229 C 225· 37+29· 34+1 276 M 7.647 232711
743 · 523 · 449 · 317 · 211 · 11 C 231· 310+231· 36+23· 36+1 363 M 7.745 2929121
863 · 773 · 499 · 479 C 234· 32+229· 32+210· 32−1 287 M 7.712 313221
919 · 617 · 409 · 83 · 61 C 229· 37+214· 37+25· 32+1 312 M 7.782 263721
491 · 487 · 419 · 103 C 219· 39+24· 36+1 258 M 7.756 172911
821 · 701 · 37 · 13 C 225· 32−223· 3+29· 3+1 224 M 7.987 223221
881 · 811 · 563 C 227· 3−217· 3−29· 3+1 226 M 7.907 243121
929 · 461 · 251 C 214· 38+25· 3−1 211 M 7.909 122811
577 C 26· 32+1 75 M 8.177 5121
953 · 29 C 210· 33−22· 3+1 123 M 8.337 82311
887 · 457 C 214· 33−212· 32−24· 32−1 159 M 8.535 113321
677 · 569 · 379 · 373 · 359 · 41 E 240· 36−227−33 371 M 7.493 3825111
797 · 433 · 79 E 223· 3+221+3 192 M 7.773 212111
859 · 727 · 587 · 293 · 193 · 29 E 238· 37−218· 34+29· 36−1 379 M 7.720 3535221
937 · 557 · 89 · 13 E 226· 32−217+32 225 M 7.714 2421111
switch to Montgomery, last ADDε is in fact a ADDM -4 M -11
52 · 36 M 100 M 7.065 810
5 M 17 M 7.322 12
11 M 28 M 8.094 23
883 M 83 M 8.481 113
59 M 51 M 8.670 36
149 M 63 M 8.727 38
29 M 45 M 5.000 9
Total 10807 M 7.621 1036831506483512742

acpb = arithmetic cost per bit