prime factors | type | cost | acpb† | elliptic operations | ||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
DBL | DBLε | TPL | TPLε | ADD | ADDε | ADDM | dDBL | dADD | ||||||
593 · 269 · 157 · 101 · 53 · 232 | C | 246+239+1 | 339 M | 7.368 | 44 | 2 | 1 | 1 | ||||||
809 · 643 · 541 · 307 · 197 · 67 · 5 | C | 246· 34+236· 33−1 | 387 M | 7.394 | 44 | 2 | 4 | 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 | |||||
769 · 607 · 331 · 281 · 181 · 17 | C | 239· 35+223· 33+1 | 350 M | 7.459 | 37 | 2 | 5 | 1 | 1 | |||||
673 · 257 · 97 | C | 224+1 | 177 M | 7.375 | 23 | 1 | 1 | |||||||
761 · 659 · 619 · 139 · 43 | C | 236· 33+219· 3+1 | 305 M | 7.484 | 34 | 2 | 3 | 1 | 1 | |||||
907 · 383 · 163 | C | 221· 33−1 | 192 M | 7.455 | 20 | 1 | 3 | 1 | ||||||
739 · 439 · 367 · 179 · 173 · 107 | C | 239· 36−233· 36−1 | 362 M | 7.466 | 37 | 2 | 6 | 1 | 1 | |||||
691 · 613 · 263 · 239 · 233 · 131 · 19 · 7 | C | 255· 3+230· 3−224· 3+1 | 422 M | 7.458 | 52 | 3 | 1 | 2 | 1 | |||||
751 · 733 · 349 · 151 | C | 230· 33+221· 32+1 | 263 M | 7.567 | 28 | 2 | 3 | 1 | 1 | |||||
661 · 277 · 241 · 73 | C | 230· 3+24· 3+1 | 239 M | 7.567 | 28 | 2 | 1 | 1 | 1 | |||||
977 · 467 · 421 · 353 · 347 · 19 · 17 | C | 248· 33−231· 33+215· 32−1 | 397 M | 7.525 | 45 | 3 | 3 | 2 | 1 | |||||
337 · 127 · 72 | C | 221−1 | 156 M | 7.429 | 20 | 1 | 1 | |||||||
947 · 829 · 757 · 601 · 311 · 227 · 71 · 47 | C | 244· 314−226· 311+26· 38−1 | 501 M | 7.569 | 41 | 3 | 14 | 2 | 1 | |||||
853 · 647 · 599 · 509 · 223 | C | 234· 37−226· 36+28· 33−1 | 347 M | 7.695 | 31 | 3 | 7 | 2 | 1 | |||||
709 · 503 · 283 | C | 225· 3+218+1 | 204 M | 7.672 | 23 | 2 | 1 | 1 | 1 | |||||
641 · 631 · 443 · 397 · 313 | C | 238· 34+221· 33+212· 32+1 | 339 M | 7.645 | 35 | 3 | 4 | 2 | 1 | |||||
967 · 827 · 719 · 683 · 113 | C | 239· 34−234· 32+229· 3+1 | 346 M | 7.632 | 36 | 3 | 4 | 2 | 1 | |||||
839 · 787 · 521 · 167 · 109 | C | 233· 36+29· 32+27· 3−1 | 328 M | 7.716 | 30 | 3 | 6 | 2 | 1 | |||||
911 · 877 · 547 · 199 | C | 230· 34−216· 34−29· 3−1 | 283 M | 7.788 | 27 | 3 | 4 | 2 | 1 | |||||
941 · 463 · 389 · 137 | C | 217· 311−23· 39−1 | 268 M | 7.783 | 15 | 2 | 11 | 1 | 1 | |||||
971 · 823 · 401 · 229 | C | 225· 37+29· 34+1 | 276 M | 7.647 | 23 | 2 | 7 | 1 | 1 | |||||
743 · 523 · 449 · 317 · 211 · 11 | C | 231· 310+231· 36+23· 36+1 | 363 M | 7.745 | 29 | 2 | 9 | 1 | 2 | 1 | ||||
863 · 773 · 499 · 479 | C | 234· 32+229· 32+210· 32−1 | 287 M | 7.712 | 31 | 3 | 2 | 2 | 1 | |||||
919 · 617 · 409 · 83 · 61 | C | 229· 37+214· 37+25· 32+1 | 312 M | 7.782 | 26 | 3 | 7 | 2 | 1 | |||||
491 · 487 · 419 · 103 | C | 219· 39+24· 36+1 | 258 M | 7.756 | 17 | 2 | 9 | 1 | 1 | |||||
821 · 701 · 37 · 13 | C | 225· 32−223· 3+29· 3+1 | 224 M | 7.987 | 22 | 3 | 2 | 2 | 1 | |||||
881 · 811 · 563 | C | 227· 3−217· 3−29· 3+1 | 226 M | 7.907 | 24 | 3 | 1 | 2 | 1 | |||||
929 · 461 · 251 | C | 214· 38+25· 3−1 | 211 M | 7.909 | 12 | 2 | 8 | 1 | 1 | |||||
577 | C | 26· 32+1 | 75 M | 8.177 | 5 | 1 | 2 | 1 | ||||||
953 · 29 | C | 210· 33−22· 3+1 | 123 M | 8.337 | 8 | 2 | 3 | 1 | 1 | |||||
887 · 457 | C | 214· 33−212· 32−24· 32−1 | 159 M | 8.535 | 11 | 3 | 3 | 2 | 1 | |||||
677 · 569 · 379 · 373 · 359 · 41 | E | 240· 36−227−33 | 371 M | 7.493 | 38 | 2 | 5 | 1 | 1 | 1 | ||||
797 · 433 · 79 | E | 223· 3+221+3 | 192 M | 7.773 | 21 | 2 | 1 | 1 | 1 | |||||
859 · 727 · 587 · 293 · 193 · 29 | E | 238· 37−218· 34+29· 36−1 | 379 M | 7.720 | 35 | 3 | 5 | 2 | 2 | 1 | ||||
937 · 557 · 89 · 13 | E | 226· 32−217+32 | 225 M | 7.714 | 24 | 2 | 1 | 1 | 1 | 1 | ||||
switch to Montgomery, last ADDε is in fact a ADDM | -4 M | -1 | 1 | |||||||||||
52 · 36 | M | 100 M | 7.065 | 8 | 10 | |||||||||
5 | M | 17 M | 7.322 | 1 | 2 | |||||||||
11 | M | 28 M | 8.094 | 2 | 3 | |||||||||
883 | M | 83 M | 8.481 | 1 | 13 | |||||||||
59 | M | 51 M | 8.670 | 3 | 6 | |||||||||
149 | M | 63 M | 8.727 | 3 | 8 | |||||||||
29 | M | 45 M | 5.000 | 9 | ||||||||||
Total | 10807 M | 7.621 | 1036 | 83 | 150 | 6 | 48 | 35 | 1 | 27 | 42 |
†acpb = arithmetic cost per bit