prime factors | type | cost | acpb† | elliptic operations | ||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
DBL | DBLε | TPL | TPLε | ADD | ADDε | ADDM | dDBL | dADD | ||||||
491 · 227 · 109 · 73 · 67 · 232 · 17 | C | 241· 35+220· 32−1 | 364 M | 7.440 | 39 | 2 | 5 | 1 | 1 | |||||
617 · 347 · 331 · 167 · 83 · 17 | C | 236· 35+22+1 | 329 M | 7.490 | 34 | 2 | 5 | 1 | 1 | |||||
503 · 449 · 113 · 59 · 53 · 31 | C | 238· 32−25· 32−1 | 307 M | 7.457 | 36 | 2 | 2 | 1 | 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 | |||||
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 | |||||
509 · 499 · 241 · 149 · 43 | C | 229· 36+228· 3+1 | 292 M | 7.582 | 27 | 2 | 6 | 1 | 1 | |||||
571 · 487 · 307 · 293 · 11 | C | 238+228+212+1 | 291 M | 7.658 | 35 | 3 | 2 | 1 | ||||||
557 · 367 · 251 · 239 · 181 · 107 | C | 243· 33+225· 33+23· 33+1 | 362 M | 7.580 | 40 | 3 | 3 | 2 | 1 | |||||
479 · 457 · 433 · 431 · 132 · 72 | C | 234· 39+226· 37+224· 3+1 | 371 M | 7.687 | 31 | 3 | 9 | 2 | 1 | |||||
601 · 463 · 397 · 349 | C | 232· 32−225· 3+217−1 | 273 M | 7.763 | 29 | 3 | 2 | 2 | 1 | |||||
229 · 179 · 97 | C | 214· 35−26· 34−1 | 175 M | 7.983 | 12 | 2 | 5 | 1 | 1 | |||||
193 | C | 26· 3+1 | 63 M | 8.298 | 5 | 1 | 1 | 1 | ||||||
619 · 317 | C | 216· 3−27· 3−1 | 141 M | 8.020 | 14 | 2 | 1 | 1 | 1 | |||||
563 · 541 · 467 · 419 · 373 · 197 · 137 · 47 · 37 · 29 | E | 262· 38−236−232· 38+38 | 557 M | 7.459 | 59 | 3 | 7 | 1 | 2 | 1 | ||||
607 · 599 · 523 · 461 · 379 · 277 · 79 | E | 253· 34−248· 32+216−34 | 448 M | 7.550 | 50 | 3 | 2 | 2 | 2 | 1 | ||||
443 · 233 · 163 · 157 · 127 · 7 | E | 230· 37+216−35 | 313 M | 7.617 | 28 | 2 | 6 | 1 | 1 | 1 | ||||
577 · 569 · 439 · 421 · 383 · 223 · 41 · 11 | E | 242· 312+26· 38+26+312 | 466 M | 7.637 | 40 | 2 | 10 | 2 | 2 | 1 | ||||
613 · 587 · 401 · 191 · 101 | E | 235· 34+227· 3−215−3 | 320 M | 7.741 | 32 | 3 | 3 | 1 | 2 | 1 | ||||
593 · 389 · 337 · 269 · 61 | E | 237· 32+232· 32+25−3 | 312 M | 7.758 | 34 | 3 | 2 | 2 | 1 | |||||
313 · 281 · 151 · 103 | E | 224· 34+223+216· 32+34 | 245 M | 8.073 | 21 | 3 | 2 | 2 | 2 | 1 | ||||
311 · 283 · 271 | E | 215· 36−212· 32+29+3 | 206 M | 8.406 | 12 | 3 | 4 | 2 | 2 | 1 | ||||
switch to Montgomery, last ADDε is in fact a ADDM | -4 M | -1 | 1 | |||||||||||
3 | M | 11 M | 6.940 | 1 | 1 | |||||||||
32 | M | 22 M | 6.940 | 2 | 2 | |||||||||
5 · 32 | M | 39 M | 7.101 | 3 | 4 | |||||||||
52 | M | 34 M | 7.322 | 2 | 4 | |||||||||
19 | M | 35 M | 8.239 | 1 | 5 | |||||||||
547 | M | 77 M | 8.466 | 1 | 12 | |||||||||
29 | M | 45 M | 5.000 | 9 | ||||||||||
Total | 6901 M | 7.622 | 663 | 53 | 83 | 13 | 33 | 20 | 1 | 19 | 28 |
†acpb = arithmetic cost per bit