Scott Fluhrer edited untitled.tex  almost 9 years ago

Commit id: beeffeeccb1f1e961c320a74c6189a51573d257d

deletions | additions      

       

Of course, once we consider nonpower-of-2 bases, we lose the two advantages that we formally had; let us examine how bad that makes the situation.  \section{Costs of point multiplying multiplication  using a non-power-of-2 base} The first thing we want to look at is how much more expensive it is to use a base which is not a power of 2. After all, a base which is a power of 2 allows us to implement that fixed multiplication by a handful of doublings, which is the most efficient method  possible. However, it turns out that there are  other bases that  are almost as cheap. To make this comparison concrete, in a concrete comparision, we'll outline the costs with both a power-of-2 base, and a nonpower-of-2 base. In  both cases we'll assume that we're dealing with an Elliptic Curve with a 256 bit subgroup, and that we'll use a 64 bit blinding value $r$, yielding an exponent which is 320 bits long. We'll use the radix method, using a balanced representation of the digits (that is, the digits are values in the range $[-b/2, b/2]$, and we'll assume that the addition-by-0 is masked somehow (whether the low-level addition routines handle it without a special case, or because in that case we'll add by an arbitrary point and discard the result). To implement this using radix $b=32$ (which is optimal over all powers-of-2 in this scenario), we'll first compute the digits $(-16G, -15G, ..., 15G, 16G)$ with 7 doublings, 7 additions\footnote{In some elliptic curve representations, the operation of adding a point to itself (doubling) is cheaper than adding two distinct points (additions), hence we track those two operations separately} and 15 negations\footnote{Negation is such a cheap operation within Elliptic Curves that we typically don't count it}. Then, we implement the actual addition chain; in this case, 320 bits is 64 digits\footnote{Normally, it would be 65, because of the signed representation; however we could assume that r is a signed value as well, and that would bring us to the 64 digit level}; this is 63 rounds of multiplying the current point by 32 (which is 5 doublings), and adding in the next digit (which is a single addition); this step takes us 315 doublings, and 63 additions, for a total of 322 doublings, 70 additions, and 15 negations.