Faster cofactorization with ECM using mixed representations


Set of blocks for stage 1 of ECM for B1 = 783
prime factors type cost acpb elliptic operations
DBLDBLεTPLTPLεADDADDεADDMdDBLdADD
673 · 257 · 97 C 224+1 177 M 7.375 2311
761 · 659 · 619 · 431 · 139 · 43 · 23 · 17 · 7 C 253· 35−217· 3−1 448 M 7.353 512511
653 · 601 · 479 · 401 · 293 · 277 · 53 C 255· 32−240+216−1 434 M 7.461 523221
617 · 347 · 331 · 167 · 83 · 17 C 236· 35+22+1 329 M 7.490 342511
193 · 191 · 101 · 73 · 5 C 224· 34−1 225 M 7.416 23141
739 · 439 · 367 · 179 · 173 · 107 C 239· 36−233· 36−1 362 M 7.466 372611
499 · 467 · 421 · 197 C 231· 32−215· 32+1 258 M 7.551 292211
751 · 733 · 349 · 151 C 230· 33+221· 32+1 263 M 7.567 282311
773 · 613 · 103 · 11 C 229+22+1 220 M 7.586 27211
523 · 269 · 241 · 19 · 5 C 230· 3−216· 3+1 239 M 7.567 282111
769 · 661 · 647 · 157 · 67 · 59 · 29 · 13 C 245· 37+233· 33−213· 3−1 424 M 7.559 423721
337 · 127 · 72 C 221−1 156 M 7.429 2011
709 · 587 · 353 · 149 · 11 C 222· 310−220· 38+1 291 M 7.697 2021011
577 · 541 · 409 · 227 C 230· 33−220· 32+25· 32−1 271 M 7.798 273321
683 · 461 · 271 C 220· 34+217· 3+1 205 M 7.781 182411
641 · 631 · 443 · 397 · 313 C 238· 34+221· 33+212· 32+1 339 M 7.645 353421
701 · 643 · 131 · 109 C 231· 3−221· 3−26· 3+1 254 M 7.795 283121
317 · 311 · 113 · 61 C 223· 34+210· 34−1 226 M 7.703 212411
727 · 419 · 263 · 229 C 223· 37+29· 34−24−1 270 M 7.919 203721
571 · 547 · 449 · 199 · 71 C 225· 310+220· 34+213· 34+1 320 M 7.834 2231021
719 · 463 · 37 C 214· 36+29· 36+22+1 195 M 8.279 113621
433 C 24· 33+1 73 M 8.335 3131
557 · 251 C 26· 37−2· 34+1 143 M 8.366 42711
677 · 569 · 379 · 373 · 359 · 41 E 240· 36−227−33 371 M 7.493 3825111
743 · 593 · 509 · 281 · 163 · 137 · 79 · 23 · 13 E 249· 310−246· 32+232−37 492 M 7.587 4638221
691 · 283 · 239 · 223 · 211 E 239· 3+239+225· 3+3 311 M 7.585 372121
599 · 503 · 389 · 383 · 31 E 234· 34+214+23· 3−3 313 M 7.759 3133121
757 · 491 · 457 · 233 · 89 E 229· 38−224+211· 38−38 326 M 7.822 2637121
563 · 521 · 307 · 181 E 226· 35−223+29· 33−33 269 M 7.929 2334121
607 · 487 · 47 E 219· 33−218−32 188 M 7.923 1722111
switch to Montgomery, last ADDε is in fact a ADDM -4 M -11
32 M 22 M 6.940 22
5 · 34 M 61 M 7.042 56
5 M 17 M 7.322 12
19 M 35 M 8.239 15
29 M 45 M 5.000 9
Total 8568 M 7.620 821681238392911815

acpb = arithmetic cost per bit