prime factors | type | cost | acpb† | elliptic operations | ||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
DBL | DBLε | TPL | TPLε | ADD | ADDε | ADDM | dDBL | dADD | ||||||
337 · 227 · 127 · 73 · 67 · 17 · 72 | C | 242· 32−224−1 | 335 M | 7.416 | 40 | 2 | 2 | 1 | 1 | |||||
439 · 211 · 107 · 83 · 37 · 19 · 11 · 7 | C | 239· 34+219· 32−1 | 338 M | 7.455 | 37 | 2 | 4 | 1 | 1 | |||||
383 · 277 · 223 · 193 · 167 · 97 · 59 | C | 244· 35+240· 34+226+1 | 393 M | 7.564 | 41 | 3 | 5 | 2 | 1 | |||||
379 · 367 · 331 · 317 · 173 · 113 | C | 229· 312−218· 39−1 | 364 M | 7.580 | 27 | 2 | 12 | 1 | 1 | |||||
409 · 349 · 313 · 271 · 257 · 181 · 157 · 11 | C | 255· 33−245· 3+220· 3+28· 3+1 | 454 M | 7.598 | 51 | 4 | 3 | 3 | 1 | |||||
251 · 239 · 233 · 149 · 43 · 17 · 13 | C | 241· 32+225· 3+213· 3−1 | 336 M | 7.607 | 38 | 3 | 2 | 2 | 1 | |||||
419 · 347 · 293 · 283 · 137 · 103 · 29 · 19 | C | 250· 34+248· 32+239· 32−227· 32−1 | 431 M | 7.645 | 46 | 4 | 4 | 3 | 1 | |||||
457 · 443 · 401 · 281 · 61 | C | 234· 34−219· 33+25· 33−1 | 311 M | 7.710 | 31 | 3 | 4 | 2 | 1 | |||||
311 · 269 · 131 · 31 | C | 222· 34+26· 32−1 | 219 M | 7.728 | 20 | 2 | 4 | 1 | 1 | |||||
89 · 23 | C | 211−1 | 86 M | 7.819 | 10 | 1 | 1 | |||||||
433 · 431 | C | 28· 36−1 | 137 M | 7.824 | 7 | 1 | 6 | 1 | ||||||
389 · 179 | C | 216+212−1 | 129 M | 8.019 | 14 | 2 | 1 | 1 | ||||||
463 · 421 · 353 · 79 | E | 226· 34−28−33 | 249 M | 7.699 | 24 | 2 | 3 | 1 | 1 | 1 | ||||
359 · 263 · 241 · 191 · 109 · 47 | E | 238· 34+218+216· 34−3 | 343 M | 7.736 | 35 | 3 | 2 | 2 | 2 | 1 | ||||
307 · 199 · 101 · 71 · 53 | E | 217· 311+27+311 | 270 M | 7.841 | 15 | 2 | 10 | 1 | 1 | 1 | ||||
449 · 373 · 229 · 139 | E | 229· 32+229−222· 32+3 | 255 M | 7.892 | 27 | 2 | 2 | 2 | 1 | |||||
461 · 397 · 197 · 151 | E | 226· 34+223+22· 33−1 | 257 M | 7.946 | 23 | 3 | 3 | 1 | 2 | 1 | ||||
switch to Montgomery, last ADDε is in fact a ADDM | -4 M | -1 | 1 | |||||||||||
35 | M | 55 M | 6.940 | 5 | 5 | |||||||||
53 | M | 51 M | 7.322 | 3 | 6 | |||||||||
13 | M | 29 M | 7.837 | 1 | 4 | |||||||||
163 · 41 | M | 109 M | 8.578 | 5 | 14 | |||||||||
28 | M | 40 M | 5.000 | 8 | ||||||||||
Total | 5187 M | 7.638 | 486 | 41 | 64 | 7 | 25 | 16 | 1 | 22 | 29 |
†acpb = arithmetic cost per bit