Appears in C. Park, S. Chee (Eds.): Information Security and Cryptology – ICISC 2004,
Springer-Verlag LNCS 3506, pp. 137–153, ISBN-13 978-3-540-26226-8, 2005.

Fractional Windows Revisited:
Improved Signed-Digit Representations for
Efficient Exponentiation
Bodo Möller?
University of California, Berkeley
bmoeller@acm.org

Abstract. This paper extends results concerning efficient exponentiation in groups where inversion is easy (e.g. in elliptic curve cryptography).
It examines the right-to-left and left-to-right signed fractional window(RL-SFW and LR-SFW) techniques and shows that both RL-SFW and
LR-SFW representations have minimal weight among all signed-digit
representations with digit set {±1, ±3, . . ., ±m, 0}. (Fractional windows
generalize earlier sliding-window techniques, providing more flexibility
for exponentiation algorithms in order to make best use of the memorythat is available for storing intermediate results.) Then it considers thelength of representations: LR-SFW representations are an improvement
over RL-SFW representations in that they tend to be shorter; further
length improvements are possible by post-processing the representations.
Keywords: Efficient implementations, elliptic curve cryptography.

1

Introduction

Many public-key cryptosystems involve exponentiation in some finite group, andoften (e.g. for elliptic curve cryptography) group elements are represented suchthat the inversion operation is almost immediate. It is well known that signeddigit representations of integers e are useful to perform exponentiations g e insuch groups. A particular signed-digit representation is the right-to-left signed
fractional window (RL-SFW) representation introduced in [14]. Fractional windows provide more flexibility for exponentiation algorithms than the previously
known sliding-window representations; the purpose of this flexibility is to makebest use of the memory that is available for storing intermediate results. The
present paper also considers the left-to-right signed fractional window (LR-SFW)
representation (cf. [19] and [9]); it complements [14] by proving minimality ofweight for both RL-SFW and LR-SFW representations. A general motive forpreferring the left-to-right variant is that it generates the digits in the order inwhich they are usually needed for exponentiation. We also examine the length of?

Supported by a DAAD (German Academic Exchange Service) Postdoc fellowship.

1

representations and see that the LR-SFW method actually provides an improvement in this respect, and that further improvements are possible. Finally, weobserve that no finite-state machine can always generate a minimal-length representation among the representations of minimal weight employing a prescribed
set of signed digits.
To motivate and explain the goals of this paper, let us first look at typical
exponentiation techniquesin some detail. Given integers b` , . . ., b0 as digits, wePwrite (b` . . . b0 )2 for 0≤i≤` bi · 2i . For m ≥ 1 odd, let
Bm = {±1, ±3, . . ., ±m}
be the set of odd integers with absolute values up to m. We call b` . . . b0 a
Bm -representation of e if b` , . . ., b0 ∈ Bm ∪ {0} and e = (b` . . . b0 )2 . For example,
for any m, 1001 is a Bm -representation of 7, where we use the convention thatb denotes digit value −b. If we assume that e 6= 0 and that ` is chosen minimal (sothat b` 6= 0), the power g e can be computed by the two-stage algorithm shown in
Fig. 1. This algorithm processes the digits bi from the most significant down to{ LR-exponentiation: compute g e where e = (b` . . . b0 )2 , b` 6= 0 }{ Precomputation stage }A ← g2G1 ← gfor b = 3 to m step 2 do
Gb ← Gb−2 · A { = g b }{ Evaluation stage }`´A ← b` > 0 ? Gb` : G−1|b` |for i = ` − 1 down to 0 do
A ← A2
if bi 6= 0 then`´
A ← A · bi > 0 ? Gbi : G−1|bi |return A
Fig. 1. LR-exponentiation

the least significant one, i.e. left to right assuming big-endian notation; we speakof LR-exponentiation. Let H(b` . . . b0 ) denote the weight (generalized Hamming
weight) of the given Bm -representation, i.e. the number of non-zero digits. The
LR-exponentiation algorithm in Fig. 1 performs the following numbers of group
operations (where we distinguish between squarings and general multiplications
since they will typically have different computational cost, but neglect inversions
as these are assumed to be almost immediate):– In the precomputation stage, one squaring and2

m−1
general multiplications;2

– in the evaluation stage, ` squarings and H(b` . . . b0 ) − 1 general multiplications.1
Increasing parameter m makes additional digit values available, typically allowing for lower-weight representations at the cost of an increased precomputation
stage effort. Parameter m also determines the amount of memory needed forstoring the precomputed values G1 , . . ., Gm , so implementations may have totake into account some upper limit on m.
For given m and e, there is a lower limit on ` (i.e. there is a lower limit on
the length ` + 1 of Bm -representations of e). There is no upper limit on ` (sincee.g. (111 . . . 1)2 = 1), but low-weight Bm -representations never need be morethan one digit longer than the binary representation: the bounds
log2 |e| − blog2 mc ≤ ` ≤ log2 |e|hold for the following well-known representations and for the newer representations that will be discussed afterwards.
– Let w ≥ 1 be an integer parameter and W = w + 1. The width-W nonadjacent form (W -NAF) of e is a specific B2w −1 -representation such thatfor |e| → ∞, on averageH(b` . . . b0 )
1

 ≈
W
+1
log2 |e|assuming that e consists of random bits. As the W -NAF is a signed-digit
equivalent of the well-known sliding-window technique for unsigned digits(cf. [4]), we also call it a right-to-left signed window representation withwindow width W .
(The origin of the 2-NAF is “property M” in [18]; the generalization toarbitrary W ≥ 2 was alluded to in [20] and described independently in [12],in [22] as an improvement of a technique from [21], and in [2].)– Now consider an arbitrary odd m ≥ 1 and let
wm = blog2 mc + 1,
Wm = wm + 1,
2wm − 1 − m∆m =2wm −1(so that 0 ≤ ∆m < 1). Generalizing right-to-left signed window representations, there is a right-to-left signed fractional window (RL-SFW) representation of e, the m-RL-SFW representation (details follow in Section 2). Thisis a Bm -representation such that for |e| → ∞, on average1
H(b` . . . b0 ) ≈W m − ∆m + 1
log2 |e|1

For ` ≥ 1, an immediate optimization to the algorithm as written is to skip thefirst evaluation stage assignment and squaring if b` = 1 (just keep g 2 in A from theprecomputation stage) or b` = −1 (just invert A to obtain g −2 ).

3assuming that e consists of random bits. If m is of the form 2w − 1 (sothat ∆m = 0), the m-RL-SFW representation is the same as the Wm -NAF;
otherwise the effective window width Wm − ∆m is a fraction between wm
and Wm :m
W m − ∆m

1
2

3

5

3

3 12

7

9

11

13

4

4 41

4 24

4 34

15

17

19

···

5

5 18

5 28

···

(The RL-SFW representation was introduced in [14].)The (finite-state) algorithms to obtain these representations given the binary
representation of e read the least significant bit first and output the least significant signed digit first, proceeding towards the most significant input bit andoutput digit. This means they work right to left assuming big-endian notation;
thus we speak of RL-transformations.
The use of an RL-transformation with LR-exponentiation means that usually
the Bm -representation would be computed and stored before the actual exponentiation begins. This is unfortunate if memory is scarce. (Alternatively, theRL-transformation could be used repeatedly to determine the signed digits inthe order in which they are needed, but this would mean an increased computational cost.) It is possible to perform RL-exponentiation instead so that thesigned digits are used in the order in which they are generated (using algorithms
from [23] and [11–exercise 4.6.3-9] as summarized in [14]); however, there are
drawbacks:– The group operation count to perform an RL-exponentiation is slightly
higher than for an LR-exponentiation, given the same Bm -representation.
– The technique of employing mixed coordinates [3] for elliptic curves requires
LR-exponentiation. (This technique uses additional precomputation effort
to convert the elements Gb into a representation that accelerates evaluation
stage operations A · Gb or A · G−1|b| .)– The technique ofinterleaved
exponentiation[13] for efficiently computingQepower products 1≤j≤k gj j applies to LR-exponentiation only.
Hence, left-to-right analogues of the above low-weight representations are calledfor.
A left-to-right analogue of the 2-NAF was described in [8], and recently, general left-to-right analogues of the signed window representation have appearedin [16], [1], and [17]. The latter two publications use an inherently identical LRtransformation, but describe it differently; see also [7–Section 6]. Also recently,
proofs have appeared that the right-to-left signed window representation and its
left-to-right variants are optimal in the sense of always achieving minimal weight([15], [16], [1]): that is, given any e and w, no B2w −1 representation b0`0 . . . b00 of e
can have lower weight than the (w + 1)-NAF or its left-to-right analogues.
We generalize and extend these results by examining the right-to-left signed
fractional window (RL-SFW) technique from [14] as well as its left-to-right variant (LR-SFW) implied by the approach of [17] and [7–Section 6]. (For unsigned
4

windows, right-to-left and left-to-right variants are equally simple: unsigned fractional windows, originally only presented for an RL-transformation in [14], havean immediate left-to-right analogue [5]. Signed-digit representations are trickier
since they involve carries, but the approach of [17] and [7] makes it straightforward to come up with a left-to-right analogue of the RL-transformation from [14];cf. [19] and [9].) We give minimality proofs for the weight of both RL-SFW and
LR-SFW representations, and we examine the length of representations to study
efficiency improvements beyond weight minimization. We always assume that e
is positive: the case e = 0 is trivial; for negative e, apply the technique to −eand replace all resulting digits by their negatives.
Section 2 looks at the RL-SFW representation and proves that it has minimal
weight. Then Section 3 develops the LR-SFW representation and shows that it
too has minimal weight. Section 4 points out that the left-to-right method isadvantageous in that it tends to achieve slightly shorter lengths than the rightto-left method (and never yields a greater length), with details in Appendix A.
It also considers how modified representations can further reduce the length insome cases; however, Appendix B observes that no finite-state transformation
algorithm can always achieve minimal length among the representations of minimal weight.

2

Right-to-Left Signed Fractional Windows (m-RL-SFW)

The right-to-left signed fractional window (RL-SFW) representation was introduced (plainly as the “signed fractional window representation”) in [14]. Here we
describe the technique in a way that encompasses the non-fractional case as well(i.e. the right-to-left signed window representation, often called the W -NAF).
Given any odd m ≥ 1, let wm = blog2 mc + 1 and Wm = wm + 1; then we have
2wm −1 ≤ m < 2wm . The m-RL-SFW representation of any positive integer e is
the Bm -representation b` . . . b0 obtained as follows.
First we define a mapping digit m : {0, 1, . . ., 2Wm − 1} → Bm ∪ {0}.
– If x is even, let digit m (x) = 0;
– otherwise if 0 < x ≤ m, let digit m (x) = x;– otherwise if m < x < 2Wm − m, let digit m (x) = x − 2wm ;– otherwise (i.e. 2Wm − m ≤ x < 2Wm ), let digit m (x) = x − 2Wm .
Observe that if x is odd, then x − digit m (x) ∈ {0, 2wm , 2Wm }. We extend themapping todigit m : Z → Bm ∪ {0}by defining digit m (x) = digit m (x mod 2Wm ); it follows that 2wm | x − digit m (x)for any odd x ∈ Z. The RL-transformation algorithm in Fig. 2 on input any Bm representation b0`0 . . . b00 of a positive integer e (e.g. the binary representation)
generates a Bm -representation b` . . . b0 such that!
Pe − 0≤j<i bj · 2jbi = digit m.
2i
5

{ RL-transformation: determine theright-to-left signed fractional window (m-RL-SFW) representationof (b0`0 . . . b00 )2 }i←0D ← (b0wm . . . b00 )2
while D 6= 0 ∨ i + wm < `0 dod ← digit m (D)bi ← di←i+1
D−dD ← b0i+wm · 2wm +2`←i−1
return (b` , . . ., b0 )Fig. 2. RL-transformation for fractional windows

The algorithm assumes that b0i = 0 for i > `0 . It is easy to verify that thealgorithm in Fig. 2 will always terminate with b` . . . b0 as given above, which
implies e = (b` . . . b0 )2 . (Note that(b0`0 . . . b0i+Wm |0 .{z. . 0} d bi−1 . . . b0 )2 = e
wm zeros

holds as a loop invariant.)
To see that the average weight for |e| → ∞ with e composed of random bits
satisfies1
H(b` . . . b0 )
1

 ≈
=
1+m
2wm − 1 − mlog2 |e|Wm + wm −1 − 1
+1
Wm −
2
2wm −1
as claimed in Section 1, assume that the RL-transformation algorithm has to process an endless sequence of independently uniform random bits b0i . Whenever theloop generates a non-zero digit bi , the current value of D has its least significant
bit set and is an otherwise random Wm -bit integer. Thus from the definition of
1+mdigit m it is clear that with probability p = wm we have 2Wm | D − digit m (D),2and with probability 1 − p we have D − digit m (D) = 2wm . In the latter case, thenext non-zero output digit will follow after exactly Wm − 2 intermediate zeros;in the former case, the next non-zero output digit will follow after Wm intermediate zeros on average. This means that the total average a for the number ofintermediate zeros is
a = pWm + (1 − p)(Wm − 2) = Wm + 2p − 2 = Wm +and thus the density

1+m
− 2,
2wm −11of non-zero digits is as claimed above.
a+1
6

2.1

Minimality of Weight

To prove that the m-RL-SFW representation has minimal weight among all
Bm -representations of any integer e, we show that
H(b` . . . b0 ) ≤ H(b0`0 . . . b00 )always holds if the transformation algorithm is applied to any Bm -representationb0`0 . . . b00 to obtain the corresponding RL-SFW representation b` . . . b0 . For the
analysis, we look at a variant of the algorithm from Fig. 2, shown in Fig. 3. Thisvariant is easily seen to generate results that are identical except for leading
zeros. The algorithm as written assumes that all variables bi are initially zero.
{ RL-transformation (variant): determine theright-to-left signed fractional window (m-RL-SFW) representationof (b0`0 . . . b00 )2 }l ← `0(bl , . . ., b0 ) ← (b0`0 , . . ., b00 )i←0while i ≤ l do
{ b` , . . ., bi+1 , bi−1 , . . ., b0 ∈ Bm ∪ {0} ∧ |bi | ≤ 2m }if bi is even thenbi+1 ← bi+1 + bi /2
bi ← 0{ b` , . . ., bi+2 , bi , . . ., b0 ∈ Bm ∪ {0} ∧ |bi+1 | ≤ 2m }
i←i+1
else
D ← (bi+wm . . . bi )2d ← digit m (D) „(bi+wm , . . ., bi ) ←

D−d
,
2wm

«
0, . . ., 0 , d| {z }

wm − 1 zeros{ b` , . . ., bi+wm +1 , bi+wm −1 , . . ., b0 ∈ Bm ∪ {0} ∧ |bi+wm | ≤ 2m }i ← i + wm
if i > l ∧ bi 6= 0 then
l←i
`←i−1
return (b` , . . ., b0 )Fig. 3. RL-transformation (variant) for fractional windows

While the input and output consist only of digits from Bm ∪ {0}, the variable bi at the beginning of the loop body may contain other values; we call this
digit the current carry digit. We can verify as a loop invariant that at the beginning of the loop body digits bh other than the carry digit (h 6= i) will always
7

satisfy bh ∈ Bm ∪ {0} (thus |bh | ≤ m) while the carry digit will always satisfy|bi | ≤ 2m. This clearly holds for i = 0. If for any i it holds at the beginning of
the loop body, then it will also hold at the end of the loop body:– If at the beginning of the loop body bi is even, then it follows from |bi+1 | ≤ m
and |bi | ≤ 2m that|bi+1 + bi /2| ≤ 2m.
– If at the beginning of the loop body bi is odd, then|D| ≤ m · 2wm + . . . + m · 21 + 2m = m · 2wm +1
and thus|D − d| ≤ m · 2wm +1 + m.
Now because of 2wm | D − d and m < 2wm , it follows that|D − d| ≤ m · 2wm +1
and thus

D−d
≤ 2m.
2wm

So in both cases, the absolute value of the subsequent carry digit indeed cannot
exceed 2m. It is clear that no other digit will be set to values not in Bm ∪ {0}.
Now we consider the valuee = H(bl . . . b0 ) + # h; |bh | > m + 1
H
as observed at the beginning and at the end of the loop body (remember that bi
is the only digit among bl . . . b0 that is not necessarily an element of Bm ∪ {0},e exceeds the weight of bl . . . b0 at most by one). Given the loop invariant,so He will never increase within the loop body. It is clear that the
we can show that H
e if bi is zero. If biloop body will not change any of the digits and thus not H
is non-zero and even, following the algorithm it is easy to see that the changes
e For bi odd, at the beginning of the loop
done to bi and bi+1 cannot increase H.
body define
H = H(bi+wm . . . bi ) + # h; |bh | > m + 1 ∧ i + wm ≥ h ≥ i ;now we can distinguish between the following cases:– H = 1. This implies bi = D = d, so the loop body will not change any of theedigits and thus not H.
– H = 2. If |bi | ≤ m, then there are initially exactly two non-zero digits
among bi+wm . . . bi , both of absolute value at most m, and thus we have
|D| ≤ (2wm + 1) · m. If |bi | > m, then bi is the only non-zero digit amongbi+wm . . . bi , which implies D = bi and thus |D| ≤ 2m. In both cases, ford = digit m (D) it follows that8

(2wm + 2) · m
D−d
,
≤
2wm
2w m
and since 2wm | D − d and m < 2wm ,
 wm



D−d
2m
(2
+ 2) · m= m + wm = m + 1.
≤
2wm
2wm
2
Thus when the loop body overwrites the digits bi+wm . . . bi with new values,
the new carry digit will be of absolute value at most m + 1; and since ate cannot increase.
most two of the new values will be non-zero, H– H ≥ 3. The digits bi+wm . . . bi are overwritten with new values out of which at
most two are non-zero, and at most one is of absolute value larger than m+1;
e This means that Heso these new digit values will contribute at most 3 to H.
cannot increase.
e is the input weight H(b0 0 . . . b0 ); in the end, it is the output weight
Initially, H0`e never increases, so no Bm -representation can have lower weightH(b` . . . b0 ). H
than the RL-SFW representation generated by the transformation algorithm.

3

Left-to-Right Signed Fractional Windows (m-LR-SFW)

To arrive at a left-to-right version, we use an approach from [17] and (building on[6] and [1]) from [7–Section 6]. This provides another way to view the RL-SFW
method, and it yields an LR-SFW method (which was new at time of writing,but meanwhile has independently been described in [19] and [9].)Given the binary representation βλ . . . β0 of any positive integer e, first let`0 = λ + 1 and b0i = βi−1 − βi for i = `0 , . . ., 0 (where β−1 = 0). Since(b0`0 . . . b00 )2 = (βλ . . . β0 0)2 − (βλ . . . β0 )2 = 2e − e = e,this gives us a new B1 -representation b0`0 . . . b00 of e. Observe that this representation can be obtained from the binary representation just as easily in left-to-rightas in right-to-left direction. It is clear from the construction of this new representation that every digit b0i = 1 indicates that βi−1 is the left-most digit in asequence of successive ones in the binary representation (βi = 0, βi−1 = 1), andthat every digit b0i = 1 indicates that βi is the right-most digit in such a sequenceof ones (βi = 1, βi−1 = 0). Thus, there must be an even number of non-zerodigits in b0`0 . . . b00 , and these show the following structure:– The left-most non-zero digit is a 1.
– Skipping any zeros, the neighbors of a 1 digit will always have value 1 andthe neighbors of a 1 digit will always have value 1.
– The right-most non-zero digit is a 1.

9

Because of this structure, we call b0`0 . . . b00 a sign-alternating B1 -representation.
(This representation has previously been called “reversed binary representation” [10–exercise 4.1-27], “alternating greedy expansion” [6], and “mutual opposite form” [17].) If we write ∗ for any digit of value either 1 or 1, we geta simplified form from which the B1 -representation b0`0 . . . b00 can unequivocallybe reconstructed due to its structure. We call ∗ and 0 compressed digits. The
compressed-digit form of any subsequence of digits b0i . . . b0h allows reconstructing the digits except for possible sign reversal (i.e. reconstruction would yield asequence of digits that is identical to either b0i . . . b0h or b0i . . . b0h ).
The approach from [17] and [7] to obtain related RL- and LR-transformations
is to apply a sliding-window technique to the sign-alternating B1 -representation:
this can be done right to left, giving the well-known right-to-left signed window
representation (W -NAF); or left to right, giving a left-to-right signed window
representation. Generalizing this technique, we describe how a similar approach
can be used with fractional windows. As before, let wm = blog2 mc + 1 and
Wm = wm + 1 given an odd integer m ≥ 1.
The sliding-window technique scans the representation b0`0 . . . b00 in one direction, either right to left (RL-scanning) or left to right (LR-scanning), startinga new window whenever a non-zero digit is encountered. Observe that for awindow b0i+w . . . b0i of any width w + 1 in a sign-alternating B1 -representation,
the window value (b0i+w . . . b0i )2 will have absolute value at most 2w , or 2w − 1
after dividing out powers of two. (In a B1 -representation that is not necessarily
sign-alternating, the maximal absolute window value would be 2w+1 − 1.) To
accommodate fractional windows, the width of the current window is set to Wm
if this is admissible, or wm otherwise (or less than wm when less than wm digits
are left for scanning). Here a window width is considered admissible if the window value is either some digit in Bm or even. (Window widths smaller than Wm
are always admissible.) In any case, the window value will be the product of apower of two and a digit from Bm . Thus, each of the windows requires just oneof the digits from Bm , appropriately positioned, to achieve the proper window
value.
As an illustration of the transformations, we consider an example for m = 5.
We have wm = 3 and Wm = 4. Now windows of the form ∗ 0 0∗ and ∗ 0 ∗∗ arenot admissible while windows of the form ∗ ∗ 0 ∗ and ∗ ∗ ∗ ∗ are admissible (because (1001)2 = (1011)2 = 7 > m but (1101)2 = (1111)2 = 5 ≤ m, and similarly
for the corresponding negative cases). Let e = 22369 = (101011101100001)2 ;the sign-alternating B1 -representation of e obtained by the rule b0i = βi−1 − βi is1111100110100011. RL-scanning does not encounter any inadmissible width-Wm
windows; it yields the window constellation
1 1111 00 1101 0 0011,
resulting in the B5 -representation
1 0005 00 0005 0 0001.
10LR-scanning has to use width wm (= 3) in one instance to avoid the inadmissible
window 1 0 0 1 ; it yields the window constellation
1111 100 1101 000 11,
resulting in the B5 -representation
5 100 0005 000 01.
It is easy to see that this procedure with RL-scanning will always determine
the same Bm -representation as the algorithms shown in Section 2 (ignoring any
leading zeros); that is, this is just another way to view the RL-SFW technique.
With LR-scanning, this is a new technique, giving us a left-to-right signed fractional window (LR-SFW) representation of e, the m-LR-SFW representation.
So far we have seen how to obtain LR-SFW representations using an intermediate sign-alternating B1 -representation (following [17] with appropriatechanges for fractional windows). This intermediate step is helpful for describing
and analyzing the method, but it is not necessary for implementation. Instead,the algorithm in Fig. 4 (following [1] with appropriate changes for fractional windows) can be used to obtain the m-LR-SFW representation b` . . . b0 of a positive
integer directly from the binary representation βλ . . . β0 . The algorithm as written assumes that βλ+1 = 0 and βi = 0 for i < 0; also, all variables bi are initiallyzero. In comments, we use b0i as defined above (b0i = βi−1 − βi ) to show that thisalgorithm expresses exactly the LR-transformation that we have introduced interms of LR-scanning; to verify the correspondence, observe that for i ≥ h(b0i . . . b0h )2 = (βi−1 . . . βh−1 )2 − (βi . . . βh )2= (βi−1 . . . βh )2 · 2 + βh−1 − βi · 2i−h − (βi−1 . . . βh )2= −βi · 2i−h + (βi−1 . . . βh )2 + βh−1
= (βi βi−1 . . . βh )2 + βh−1 .

3.1

Minimality of Weight

As discussed in Section 1, there are general advantages of LR-transformations
over RL-transformations. A natural question to consider is whether despite ofthese advantages, the LR-SFW representation might be worse for exponentiation
than the RL-SFW representation. To address this issue, here we show that forgiven m and e, the weight of the m-LR-SFW representation of e is the same as theweight of the m-RL-SFW representation. Thus, by the result from Section 2.1,
the weight is minimal among all Bm -representations of e. (Later in Section 4 wewill see that the LR-SFW representation actually has advantages beyond thegeneral advantages of LR-transformations.)
Let `0 be a positive integer and
0
S = s ∈ {0, ∗}` | ∗ occurs an even number of times in s
11

{ LR-transformation: determine theleft-to-right signed fractional window (m-LR-SFW) representationof (βλ . . . β0 )2 on binary input }
i←λ+1
`←0
while i ≥ 0 do
if βi = βi−1 then { b0i = 0 }i←i−1else { b0i 6= 0 }W ← Wmd ← (βi βi−1 . . . βi−W +1 )2 + βi−W
if d is odd ∧ |d| > m thenW ← wmd ← (βi βi−1 . . . βi−W +1 )2 + βi−W
{ d = (b0i . . .b0i−W +1 )2 }next i ← i − W
i ← next i + 1
while d is even doi ← i + 1; d ← d/2{ d is odd, |d| ≤ m, d = (b0next i+W −1 . . . b0i )2 }bi ← dif i > ` then`←ii ← next ireturn (b` , . . ., b0 )Fig. 4. LR-transformation for fractional windows

the set of all compressed-digit forms of length `0 . We can examine the scanning
process in terms of compressed-digit forms. For s ∈ S, let #LRm (s) denotethe number of windows that LR-scanning yields; i.e., #LRm (s) = H(b` . . . b0 )where b` . . . b0 is the m-LR-SFW representation of the integer determined by thecompressed-digit form s. Similarly, let #RLm (s) denote the number of windowsthat RL-scanning yields. LR-scanning and RL-scanning are mostly symmetric,
except for admissibility of window width Wm (for example, (b0i+wm . . . b0i )2 may
be a digit in Bm when (b0i . . . b0i+wm )2 is odd bot not in Bm ). However, there issome symmetry that does respect admissibility: When a window is started andthere are Wm compressed digits to look at (the first one of which in scanning
direction is necessarily a ∗), there are 2wm possibilities what these Wm compressed digits might look like; and both for LR-scanning and for RL-scanning,
window width Wm is admissible for exactly m + 1 of these possibilities and notadmissible for the remaining 2wm − m − 1 possibilities. Thus, there is a bijection
α: S → S
12such that the window structure (i.e., the positioning and width of windows, nottaking into account the actual compressed digits in the windows) obtained by
LR-scanning of any s ∈ S is the exact mirror image of the window structure
obtained by RL-scanning of α(s). This implies #LR m (s) = #RLm α(s) .
Now assume that there was some specific s0 ∈ S such that #LR m (s0 ) 6=
#RLm (s0 ). By minimality of weight of the RL-SFW representation (Section 2.1),
this would imply#LR m (s0 ) > #RLm (s0 ),
i.e. #RLm α(s0 ) > #RLm (s0 ). Since α is a bijection, we haveX

 X
#RLm α(s) =#RLm (s),

s∈S

s∈S

so furthermore it would follow that there is some s1 ∈ S such that
#RLm α(s1 ) < #RLm (s1 ). But this would mean
#LR m (s1 ) < #RLm (s1 ),contradicting the minimality of weight of the RL-SFW representation. Thus
no s0 can exist for which #LR m (s0 ) differs from #RLm (s0 ).

4LengthFrom Sections 2.1 and 3.1, we know that both the m-RL-SFW representation andthe m-LR-SFW representation are optimal in the sense of having minimal weight
among all Bm -representations. The efficiency of exponentiation given a Bm representation b` . . . b0 with b` 6= 0 depends not just on the weight H(b` . . . b0 ),but also on ` (see Section 1). Thus we are interested in representations that provide not only low weight, but also a short length `+ 1. Sometimes these goals arein conflict: for example, for B7 -representations of 255 = (10000001)2 = (70071)2 ,minimal weight and minimal length exclude each other; one or the other representation might provide better efficiency for LR-exponentiation depending on
the relative speed of squarings and general multiplications in the group. We prioritize weight over length and consider only ways to reduce the length that do
not increase the weight.
A first observation is that the LR-SFW representation can never belonger than the RL-SFW counterpart: Consider the scanning process on signalternating B1 -representations as described in Section 3, which yields a Bm representation when each window value is expressed through a single non-zerodigit from Bm . The maximal index ` of such a Bm -representation is the index of the right-most non-zero digit within the left-most window over the signalternating B1 -representation. For RL-scanning, the left-most (final) window will
cover some number of non-zero digits of the sign-alternating B1 -representation,
including its most significant digit. All of these non-zero digits, and possibly
13

more, would also be covered by the left-most (first) window obtained by LRscanning. Thus, the maximal index ` cannot increase for LR-scanning comparedwith RL-scanning.
The example in Section 3 has already shown us that the m-LR-SFW representation is indeed shorter than the m-RL-SFW representation in some cases. In
fact, the m-LR-SFW representation is advantageous for every m. For example,
for m = 1, the average length saving for m-LR-SFW representations of long
random integers e compared with m-RL-SFW representations is 1/6; for m = 3,
it is 1/2; for m = 7, it is 37/40. (Consider m = 1. If the left-most window overthe sign-alternating B1 -representation is 1 0 or 1 , the 1-LR-SFW or 1-RL-SFW
representation will be one digit longer than it is for the window 1 1 . The lattercase happens with probability 1/2 for LR-scanning, but only with probability
about 1/3 for RL-scanning. See Appendix A for more details.)
The m-LR-SFW representation does not guarantee minimal length among all
Bm -representations of minimal weight. Substitution rules resulting in a modified(right-to-left) signed fractional window representation have been given in [14–Section 5.1], and these can similarly be applied to the left-to-right case to obtainshorter representations in some cases. Additional rules not mentioned in [14]are possible. For example, if 3 ≤ m ≤ 13, the m-LR-SFW and m-RL-SFW
representations both write e = 15 as (10001)2 ; this can be improved into (303)2 ,or even into (55)2 if 5 ≤ m.
No LR-transformation implemented by a finite-state machine can always
ensure minimal length among all minimal-weight Bm -representations; see Appendix B for examples. With the m-LR-SFW representation and its generally
shorter length, there is less of a need to use modified representations to decrease
the length than with the m-RL-SFW representation, in particular if m is relatively large. However, if program space permits, implementations can include
a table of optimized substitution rules for certain prefixes that can be encountered in m-LR-SFW representations (such as 1001 7→ 31 and 10001 7→ 303 form = 3). While no such table could be complete for arbitrary lengths, this canhelp improve the average efficiency at least by a small margin.

Acknowledgement
Thanks to the anonymous reviewers for making me aware of [10–exercise 4.1-27],[6], and [7].

References
1. Avanzi, R. M. A note on the sliding window integer recoding and its left-toright analogue. In Selected Areas in Cryptography – SAC 2004, Lecture Notes in
Computer Science. To appear.

14

2. Blake, I. F., Seroussi, G., and Smart, N. P. Elliptic Curves in Cryptography, vol. 265 of London Mathematical Society Lecture Note Series. Cambridge
University Press, 1999.
3. Cohen, H., Ono, T., and Miyaji, A. Efficient elliptic curve exponentiation using
mixed coordinates. In Advances in Cryptology – ASIACRYPT ’98 (1998), K. Ohta
and D. Pei, Eds., vol. 1514 of Lecture Notes in Computer Science, pp. 51–65.
4. Gordon, D. M. A survey of fast exponentiation methods. Journal of Algorithms
27 (1998), 129–146.
5. Goriac, I., and Iftene, S. Personal communication, 2003.
6. Grabner, P. J., Heuberger, C., Prodinger, H., and Thuswaldner, J. M.
Analysis of linear combination algorithms in cryptography. Preprint, 2003. Available from http://www.opt.math.tu-graz.ac.at/~cheub/publications/.
7. Heuberger, C., Katti, R., Prodinger, H., and Ruan, X. The alternating
greedy expansion and applications to left-to-right algorithms in cryptography.
Preprint, 2004. Available from http://www.opt.math.tu-graz.ac.at/~cheub/
publications/.
8. Joye, M., and Yen, S.-M. Optimal left-to-right binary signed-digit recoding.
IEEE Transactions on Computers 49 (2000), 740–748.
9. Khabbazian, M., and Gulliver, T. A. A new minimal average weight representation for left-to-right point multiplication methods. Cryptology ePrint Archive
Report 2004/266, 2004. Available from http://eprint.iacr.org/.
10. Knuth, D. E. The Art of Computer Programming – Vol. 2: Seminumerical Algorithms. Addison-Wesley, 1969.
11. Knuth, D. E. The Art of Computer Programming – Vol. 2: Seminumerical Algorithms (3rd ed.). Addison-Wesley, 1998.
12. Miyaji, A., Ono, T., and Cohen, H. Efficient elliptic curve exponentiation. In
International Conference on Information and Communications Security – ICICS’97 (1997), Y. Han, T. Okamoto, and S. Qing, Eds., vol. 1334 of Lecture Notes in
Computer Science, pp. 282–290.
13. Möller, B. Algorithms for multi-exponentiation. In Selected Areas in Cryptography – SAC 2001 (2001), S. Vaudenay and A. M. Youssef, Eds., vol. 2259 of Lecture
Notes in Computer Science, pp. 165–180.
14. Möller, B. Improved techniques for fast exponentiation. In Information Security
and Cryptology – ICISC 2002 (2003), P. J. Lee and C. H. Lim, Eds., vol. 2587 of
Lecture Notes in Computer Science, pp. 298–312.
15. Muir, J. A., and Stinson, D. R. Minimality and other properties of the widthw nonadjacent form. Mathematics of Computation. To appear; preprint available
from http://www.cacr.math.uwaterloo.ca/tech_reports.html.
16. Muir, J. A., and Stinson, D. R. New minimal weight representations for leftto-right window methods. In CT-RSA 2005, Lecture Notes in Computer Science.
To appear; preprint available from http://www.cacr.math.uwaterloo.ca/tech_reports.html.
17. Okeya, K., Schmidt-Samoa, K., Spahn, C., and Takagi, T. Signed binary
representations revisited. In Advances in Cryptology – CRYPTO 2004 (2004),
M. Franklin, Ed., vol. 3152 of Lecture Notes in Computer Science, pp. 123–139.
18. Reitwiesner, G. W. Binary arithmetic. Advances in Computers 1 (1960), 231–308.
19. Schmidt-Samoa, K., Semay, O., and Takagi, T. Analysis of some efficient
window methods and their application to elliptic curve cryptosystems. Technical
Report TI-3/04, 2004. Available from http://www.informatik.tu-darmstadt.
de/ftp/pub/TI/TR/.

15

20. Schroeppel, R., Orman, H., O’Malley, S., and Spatscheck, O. Fast key
exchange with elliptic curve systems. In Advances in Cryptology – CRYPTO’95 (1995), D. Coppersmith, Ed., vol. 963 of Lecture Notes in Computer Science,
pp. 43–56.
21. Solinas, J. A. An improved algorithm for arithmetic on a family of elliptic curves.
In Advances in Cryptology – CRYPTO ’97 (1997), B. S. Kaliski, Jr., Ed., vol. 1294
of Lecture Notes in Computer Science, pp. 357–371.
22. Solinas, J. A. Efficient arithmetic on Koblitz curves. Designs, Codes and Cryptography 19 (2000), 195–249.
23. Yao, A. C.-C. On the evaluation of powers. SIAM Journal on Computing 5(1976), 100–103.

A

LR-SFW versus RL-SFW: Length Comparison

We want to compare the expected lengths of left-to-right and right-to-left signed
fractional window representations of long random integers by looking at LRscanning and RL-scanning as described in Section 3. Assume an `0 -bit integer e
is given (so that b0`0 = 1 in the sign-alternating B1 -representation). By the probabilities below, in the m-LR-SFW representation the expected maximum index `is `0 − 1/2 for m = 1, `0 − 5/4 for m = 3, and `0 − 17/8 for m = 7; in the
m-RL-SFW representation it is about `0 − 1/3 for m = 1, about `0 − 3/4 form = 3, and about `0 − 6/5 for m = 7.
Consider m = 2w − 1 such that windows over the sign-alternating form havewidth w + 1. For LR-scanning over random compressed-digit forms of sufficient
length, the left-most window is– ∗ 0 . . . 0 with probability 2−w ;– ∗ ∗ 0 . . . 0 also with probability 2−w ;– of the form ∗ ? ∗ 0 . . . 0 with probability 21−w ;– . . .;
– of the form ∗ ? . . . ? ∗ with probability 2−1 .
As the resulting Bm -representations will be successively shorter (the maximal
index ` of the Bm -representation is the index of the right-most non-zero digit
within the left-most window over the compressed-digit form), this is in favor ofgenerating short Bm -representations. No m ≥ 2w − 1 will have average lengths
longer than this.
For RL-scanning over long random compressed-digit forms, however, the leftmost window is– ∗ (width 1) with probability about 2/(w + 2);– ∗ ∗ (width 2) with probability about 1/(w + 2);– of the form ∗ ? ∗ (width 3) with probability about 1/(w + 2);– . . .;
– of the form ∗ ? . . . ? ∗ (width w + 1) with probability about 1/(w + 2).
16

Again the resulting Bm -representations will be successively shorter, but here theprobabilities are in favor of generating long Bm -representations. No m ≤ 2w − 1
will have average lengths shorter than this. (To derive these estimates, assume
that RL-scanning is applied to a long sequence of independently uniformly random compressed digits. Any given ∗ in a width-w window well within such asequence, after earlier windows have provided plenty of randomization of window positions, will be at the right-most position of its window with probability
about 2/(w + 2), and at any other position of its window with probability about
1/(w + 2) each. This is seen by counting how many of the 2w possibilities forthe content of a width-(w + 1) window in RL-scanning have a ∗ in the respective position: the right-most position sees twice the proportion of ∗’s as eachother position. Since the start of a window does not depend on what follows, theleft-most ∗ in a [finite but long] compressed-digit form is similar except that thewindow abruptly ends there.)

B

Limitations of Length Reduction

Let hmi be a shorthand notation for a digit string consisting of wm − 1 zeros
concatenated with the digit m, and hmi for wm zeros (e.g. h5i = 005, h5i = 000).
Now consider the integers with Bm -representations either of the form
m1 0hmi 0hmi . . . 0hmi 0hmi hmi
or of the form
m1 0hmi 0hmi . . . 0hmi 0hmi hmi.
The m-LR-SFW representation for an integer of the first form is longer than theabove representation and has lower weight; this is a weight minimization thatwould not be possible without the length increase. For example, for m = 1,
(11 01 01 . . . 01 01 1)2
is rewritten with lower weight as(100 10 10 . . . 10 10 1)2 .
The m-LR-SFW representation for an integer of the second form is longer as
well, but the weight remains unchanged; the original representation as given
above already has minimal weight. For example,(11 01 01 . . . 01 01 0)2
has no B1 -representation of lower weight. There is no bound on the number ofdigits that one might have to examine to distinguish between such cases, so no
finite-state machine could always generate the shortest representation among
those of minimal weight.

17