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