prime factors | type | cost | acpb† | elliptic operations | ||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
DBL | DBLε | TPL | TPLε | ADD | ADDε | ADDM | dDBL | dADD | ||||||
617 · 347 · 331 · 167 · 83 · 17 | C | 236· 35+22+1 | 329 M | 7.490 | 34 | 2 | 5 | 1 | 1 | |||||
643 · 379 · 313 · 193 · 191 · 149 · 101 · 73 · 72 · 52 | C | 259· 38+248· 38−235· 34−1 | 534 M | 7.450 | 56 | 3 | 8 | 2 | 1 | |||||
521 · 409 · 353 · 257 · 173 · 89 · 19 | C | 246· 34−239· 34+215· 32−1 | 395 M | 7.548 | 43 | 3 | 4 | 2 | 1 | |||||
499 · 197 | C | 215· 3−1 | 126 M | 7.597 | 14 | 1 | 1 | 1 | ||||||
467 · 421 | C | 216· 3−1 | 133 M | 7.563 | 15 | 1 | 1 | 1 | ||||||
337 · 317 · 271 · 223 · 179 · 137 | C | 244· 32−230· 32+227· 3−1 | 357 M | 7.568 | 41 | 3 | 2 | 2 | 1 | |||||
359 · 263 · 211 · 199 · 139 · 131 · 71 · 5 | C | 245· 36−238· 34+29· 34−1 | 412 M | 7.558 | 42 | 3 | 6 | 2 | 1 | |||||
439 · 277 · 79 · 37 · 29 · 5 | C | 234· 3−24· 3+1 | 267 M | 7.503 | 32 | 2 | 1 | 1 | 1 | |||||
557 · 367 · 251 · 239 · 181 · 107 | C | 243· 33+225· 33+23· 33+1 | 362 M | 7.580 | 40 | 3 | 3 | 2 | 1 | |||||
613 · 349 · 233 · 41 | C | 223· 35+216· 34+1 | 238 M | 7.695 | 21 | 2 | 5 | 1 | 1 | |||||
587 · 397 · 373 · 283 · 151 | C | 237· 33+227· 33+220· 33−1 | 320 M | 7.664 | 34 | 3 | 3 | 2 | 1 | |||||
647 · 457 · 383 | C | 222· 33−27· 32+1 | 207 M | 7.737 | 20 | 2 | 3 | 1 | 1 | |||||
619 · 541 · 509 · 229 · 47 | C | 228· 38+225· 37+211· 36+1 | 317 M | 7.781 | 25 | 3 | 8 | 2 | 1 | |||||
491 · 487 · 419 · 103 | C | 219· 39+24· 36+1 | 258 M | 7.756 | 17 | 2 | 9 | 1 | 1 | |||||
641 · 607 · 241 · 163 · 13 · 7 | C | 234· 34−223· 34−211· 3−1 | 311 M | 7.710 | 31 | 3 | 4 | 2 | 1 | |||||
563 · 307 · 227 · 127 | C | 229· 32+224· 32+22· 32+1 | 252 M | 7.823 | 26 | 3 | 2 | 2 | 1 | |||||
601 · 23 | C | 29· 33−1 | 108 M | 7.852 | 8 | 1 | 3 | 1 | ||||||
463 · 269 · 109 · 61 | C | 220· 36+218· 35+22· 33−1 | 237 M | 8.000 | 17 | 3 | 6 | 2 | 1 | |||||
577 · 569 · 503 · 449 · 401 · 113 · 59 · 53 · 43 · 31 · 23 · 19 | E | 276· 34−239· 32−210· 34+1 | 609 M | 7.396 | 73 | 3 | 2 | 2 | 2 | 1 | ||||
571 · 461 · 431 · 281 · 97 | E | 238· 32+236· 32+211+32 | 317 M | 7.640 | 35 | 3 | 1 | 1 | 2 | 1 | ||||
631 · 479 · 293 · 157 · 67 · 112 | E | 234· 38−227+220· 36+35 | 363 M | 7.776 | 31 | 3 | 6 | 2 | 2 | 1 | ||||
547 · 443 · 433 · 311 | E | 227· 35+224−212· 3−32 | 278 M | 7.960 | 24 | 3 | 3 | 2 | 2 | 1 | ||||
599 · 593 · 389 | E | 28· 312+25· 33+22· 312−1 | 229 M | 8.468 | 5 | 3 | 10 | 2 | 2 | 1 | ||||
switch to Montgomery, last ADDε is in fact a ADDM | -4 M | -1 | 1 | |||||||||||
34 | M | 44 M | 6.940 | 4 | 4 | |||||||||
3 | M | 11 M | 6.940 | 1 | 1 | |||||||||
13 | M | 29 M | 7.837 | 1 | 4 | |||||||||
17 | M | 34 M | 8.318 | 2 | 4 | |||||||||
523 | M | 80 M | 8.859 | 4 | 10 | |||||||||
29 | M | 45 M | 5.000 | 9 | ||||||||||
Total | 7198 M | 7.635 | 684 | 58 | 96 | 9 | 35 | 22 | 1 | 21 | 23 |
†acpb = arithmetic cost per bit