prime factors | type | cost | acpb† | elliptic operations | ||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
DBL | DBLε | TPL | TPLε | ADD | ADDε | ADDM | dDBL | dADD | ||||||
109 · 73 · 37 · 19 · 13 · 7 · 5 · 33 | C | 236−1 | 261 M | 7.250 | 35 | 1 | 1 | |||||||
41 · 31 · 11 · 52 · 3 | C | 220−1 | 149 M | 7.450 | 19 | 1 | 1 | |||||||
113 · 107 · 97 · 89 · 67 · 61 · 47 · 43 · 17 · 7 | C | 247· 36+232· 35+227· 35−224· 34+219· 32−1 | 442 M | 7.822 | 42 | 5 | 6 | 4 | 1 | |||||
53 · 29 | C | 29· 3+1 | 84 M | 7.935 | 8 | 1 | 1 | 1 | ||||||
101 · 83 · 79 | C | 213· 34−24· 34+1 | 156 M | 8.067 | 11 | 2 | 4 | 1 | 1 | |||||
71 · 59 · 11 | C | 212· 32+210· 32−1 | 125 M | 8.069 | 10 | 2 | 2 | 1 | 1 | |||||
switch to Montgomery, last ADDε is in fact a ADDM | -4 M | -1 | 1 | |||||||||||
103 | M | 57 M | 8.525 | 3 | 7 | |||||||||
23 | M | 39 M | 8.622 | 3 | 4 | |||||||||
26 | M | 30 M | 5.000 | 6 | ||||||||||
Total | 1339 M | 7.646 | 125 | 12 | 13 | 6 | 5 | 1 | 12 | 11 |
†acpb = arithmetic cost per bit