ON MINIMAL EXPANSIONS IN REDUNDANT NUMBER SYSTEMS: ALGORITHMS AND QUANTITATIVE ANALYSIS

CLEMENS HEUBERGER AND HELMUT PRODINGER

Abstract. We consider digit expansions in base q ≥ 2 with arbitrary integer digits such that the length of the expansion plus the sum of the absolute values of the digits is minimal. Since this does not determine a unique minimal representation, we describe some reduced minimal expansions.

We completely characterize its syntactical properties, give a simple algorithm to compute the reduced minimal expansion and a formula to compute a single digit without having to compute the others, and we calculate the average cost of such an expansion.

1. Introduction

On several occasions, representations of integers in redundant number systems have been studied. The motivation usually comes from various applications where “better” representations of an integer result in faster computations.

We give an example from public key cryptography using elliptic curves: These cryptosystems rely on the fact that it is rather easy to compute a multiple nP of a given point on an elliptic curve E(𝔽_{q}), but there is no known efficient way to calculate n from the knowledge of P and nP. Of course, if the computation of nP can be done even faster, larger values of the parameters can be chosen in order to make the system less vulnerable. The usual way to calculate nP is a repeated doubling and addition algorithm, see Knuth [12]. As it was remarked by Morain and Olivos [13], a repeated doubling and addition or subtracting scheme can be applied using a representation n = ∑_{i=0}^{l} ε_{i}2^{i} where ε_{i} ∈ {0, ±1}. The time to compute nP decreases as l + 1 + ∑_{i} |ε_{i}| decreases, since it is as easy to add a point on an elliptic curve as to subtract it.

Additionally, in the last years differential power analysis of cryptosystems has attracted attention: it tries to recover secret keys by monitoring power signals of cryptographic devices. Since in the usual doubling and addition scheme it can easily be detected whether an addition and a doubling or a doubling alone takes place, the binary representation of n can be guessed. But if digits ±1 are used, a potential attacker can gain less information. We refer to Coron [4] for further discussions.

The first author has been partially supported by the Spezialforschungsbereich F 003 “Optimierung und Kontrolle”/Projektbereich Diskrete Optimierung.

This motivates the study of representations of an integer n in base q ≥ 2 with arbitrary digits, and we will denote the set of such representations by

R_{q}(n) := {ε = (ε_{0}, …, ε_{l}) : l ∈ ℕ, ε_{i} ∈ ℤ, n = ∑_{i=0}^{l} ε_{i}q^{i}} . (1.1)

We define the cost of a representation ε ∈ R_{q}(n) as

c(ε) = c(ε_{0}, …, ε_{l}) := l + 1 + ∑_{i=0}^{l} |ε_{i}| (1.2)

and look for representations of n with minimum cost.

At several places in this paper, we will also consider a modified cost function, which we will call relaxed costs, namely

c′(ε) = c′(ε_{0}, …, ε_{l}) := ∑_{i=0}^{l} |ε_{i}| . (1.3)

We note that in general there is no unique minimal representation: Both (−1, 2) ∈ R_{3}(5) and (2, 1) ∈ R_{3}(5) are representations of 5 in base 3 with cost c(−1, 2) = c(2, 1) = 5. It will be a consequence of Theorem 1 that there are no cheaper expansions in R_{3}(5).

Our first aim in Section 2 is to describe a special minimal representation (which we will call a reduced representation), which will be unique (cf. Theorem 1). The proof of uniqueness will immediately give an efficient algorithm to compute the reduced representation (cf. Algorithm 1). The corresponding results for relaxed costs and the conversion rules between the two representations will be discussed in Section 3.

In Sections 4 and 5 we will give an explicit formula for the digits of the reduced representation in the case of odd and even q, respectively. These formulæ will be very useful for the computation of the frequencies of digits and the expected costs of the representations, as will be shown in Section 6.

An overview on previous work in this area is postponed to Section 7, where all required definitions will be available.

We assume without loss of generality that n > 0. The following notations will be used throughout the paper: the set of nonnegative integers is ℕ := {0, 1, … }, by {x} := x−⌊x⌋ we denote the fractional part of a real number x, for a set A, A^{+} is defined as ⋃_{n≥1} A^{n}, and & is the concatenation function & : A^{+} × A → A^{+}; (a_{0}, …, a_{l}) & a_{l+1} := (a_{0}, …, a_{l}, a_{l+1}). As usual, the minimum of the empty set is defined as ∞. We write log_{q}(n) := log(n)/ log(q) for the logarithm to base q. We will use Iverson’s convention as in [7], i. e. for any expression expr, [expr] = 1 if expr is true and = 0 otherwise.

2. Reduced Representations

Let n > 0 and q ≥ 2 be fixed. We will describe “reduction rules” of the shape (η_{0}, …, η_{r}) → (η′_{0}, …, η′_{r}). To apply such a rule to a representation ε means to replace the first occurrence (from the left, i. e. the least significant digits) of (η_{0}, …, η_{r}) in ε by (η′_{0}, …, η′_{s}). Additionally, reduction rules (η_{0}, …, η_{r}) ↠ (η′_{0}, …, η′_{s}) will occur, which we are only allowed to apply at the end of the representation, i. e. if ε = (ε_{0}, …, ε_{l−r−1}, η_{0}, …, η_{r}). Note that in the case of rules at the end, the length of the representation may change. We emphasize that a reduction rule must be applied at the first occurrence of the pattern.

Furthermore, define f : R_{q}(n) → R_{q}(n) in the following way: Given ε = (ε_{0}, …, ε_{l}) ∈ R_{q}(n), try the following reduction rules (in the given order) until ε first changes and return this result.

(2.1) (0) ↠ (). (2.2) For |η_{0}| > q/2, η_{1} ∈ ℤ, and u := ⌈|η_{0}| /q − 1/2⌉: (η_{0}, η_{1}) → (η_{0} − uq sign(η_{0}), η_{1} +

u sign(η_{0})). (2.3) For |η_{0}| > (q + 1)/2 and u := ⌈|η_{0}| /q − 1/2⌉: (η_{0}) ↠ (η_{0} − uq sign(η_{0}), u sign(η_{0})). (2.4) For 2 ∤ q: (−(q − 1)/2, 1) ↠ ((q + 1)/2). (2.5) For 2 | q: (−q/2, −q/2 + 1, 1) ↠ (q/2, q/2). (2.6) For η_{0} < 0 and 2 | q: (q/2, η_{0}) → (−q/2, η_{0} + 1). (2.7) For η_{0} > 0 and 2 | q: (−q/2, η_{0}) → (q/2, η_{0} − 1). (2.8) For η_{0} < q/2 and 2 | q: (q/2, q/2, η_{0}) → (−q/2, −q/2 + 1, η_{0} + 1). (2.9) For −q/2 < η_{0} and 2 | q: (−q/2, −q/2, η_{0}) → (q/2, q/2 − 1, η_{0} − 1). (2.10) For 2 | q: (q/2, q/2, q/2) ↠ (−q/2, −q/2 + 1, −q/2 + 1, 1).

We note that f is well defined since all of the above reduction rules indeed transform representations of n to representations of n.

We say that ε ∈ ℕ^{+} is reduced if f(ε) = ε. This is the case if and only if the following holds:

(2.11) There are no trailing zeros. (2.12) −q/2 ≤ ε_{i} ≤ q/2 for 0 ≤ i ≤ l − 1 and |ε_{l}| ≤ (q + 1)/2. (2.13) The sequence does not end on (−(q − 1)/2, 1) or (−q/2, −q/2 + 1, 1). (2.14) If ε_{i} = q/2 then 0 ≤ ε_{i+1} ≤ q/2 − 1 except when i = l − 1, where only 0 ≤ ε_{i+1} ≤ q is

required, or when i = l. (2.15) If ε_{i} = −q/2 then −q/2 + 1 ≤ ε_{i+1} ≤ 0 (except when i = l).

Lemma 1. Given ε ∈ R_{q}(n). Then the sequence defined by

ε^{(0)} := ε,  ε^{(i+1)} := f(ε^{(i)})  for i ≥ 0

stabilizes, i. e. there is some m ≥ 0 such that ε^{(i)} = ε^{(m)} for all i ≥ m.

Additionally, c(ε^{(i+1)}) ≤ c(ε^{(i)}) for i ≥ 0.

Proof. We define ω : ℤ^{+} → (ℤ ∪ ∞)^{8} by

ε = (ε_{0}, …, ε_{l}) ↦ (c(ε),
− min{0 ≤ i ≤ l : |ε_{i}| > q/2},
− min{0 ≤ i ≤ l : |ε_{i}| > (q + 1)/2},
card{0 ≤ i ≤ l : |ε_{i}| = q/2},
− min{0 ≤ i ≤ l − 1 : (ε_{i}, ε_{i+1}) = (q/2, q/2)},
min{1 ≤ i ≤ l − 1 : ∃η_{0} < q/2 : (ε_{i−1}, ε_{i}, ε_{i+1}) = (q/2, q/2, η_{0})},
− min{0 ≤ i ≤ l − 1 : (ε_{i}, ε_{i+1}) = (−q/2, −q/2)},

min{1 ≤ i ≤ l − 1 : ∃η_{0} > −q/2 : (ε_{i−1}, ε_{i}, ε_{i+1}) = (−q/2, −q/2, η_{0})})

and ≺ to be the relation on ℤ^{+} defined by

ε ≺ ε′ : ⟺ ω(ε) <_{lex} ω(ε′).

It is straightforward to prove that for all ε ∈ R_{q}(n)

f(ε) = ε or f(ε) ≺ ε; (2.16)

we show the most complicate case only, namely the rule (2.9).

Let

ε = (ε_{0}, …, ε_{m−1}, −q/2, −q/2, η_{0}, ε_{m+3}, …, ε_{l}),
ε′ = (ε_{0}, …, ε_{m−1}, q/2, q/2 − 1, η_{0} − 1, ε_{m+3}, …, ε_{l}).

Since rule (2.7) could not be applied (in that case, we would not have been allowed to apply (2.9)), we have η_{0} ≤ 0 and therefore −q/2 ≤ η_{0} − 1 < 0.

We calculate that c(ε′) − c(ε) = −1 + |η_{0} − 1| − |η_{0}| = 0. Since 2 | q and rules (2.2) and (2.3) could not be applied, all |ε_{i}| , |ε′_{i}| ≤ q/2 and ω_{2}(ε) = ω_{2}(ε′) = ω_{3}(ε) = ω_{3}(ε′) = −∞.

We see that ω_{4}(ε′) ≤ ω_{4}(ε) with equality if and only if η_{0} = −q/2 + 1.

We note that ε_{m−1} = q/2 cannot happen (either since m = 0 or since rule (2.6) would have been applied), therefore, the positions of blocks (q/2, q/2) have not been changed, and we obtain ω_{5}(ε′) = ω_{5}(ε) and ω_{6}(ε′) = ω_{6}(ε).

Let s := −ω_{7}(ε). Obviously s ≤ m. If s ≥ m − 1 then we have −ω_{7}(ε′) > s, otherwise, we have −ω_{7}(ε′) = s, but ω_{8}(ε) = m + 1 > ω_{8}(ε′) = m − 1. Therefore, (2.16) is proved for rule (2.9).

Since the maximum length of the occurring representations is bounded by c(ε^{(0)}), ω(ε^{(i)}) lies in the finite set

{−∞, −c(ε^{(0)}), …, 0, …, c(ε^{(0)}), ∞}^{8}

for i ≥ 0 and there must be an m ≥ 0 with the required properties.

Lemma 2. Let n, q be fixed and ε ∈ R_{q}(n) be reduced. Let a := n mod q and b := (n − a)/q mod q. Then

ε_{0} = \begin{cases}a & if a < q/2 or (a = q/2 and b < q/2) or n ∈ \{(q + 1)/2, q/2 + q^{2}/2\}, \\ a − q & otherwise. \end{cases}

Proof. From

a ≡ n ≡ ε_{0} (mod q),

|ε_{0}| < q and rules (2.2) and (2.3) we obtain that either ε_{0} = a or ε_{0} = a − q.

We note that by rules (2.2) and (2.3) and n > 0 we have |ε_{0}| ≤ q/2 except when l = 0 and ε_{0} = n = (q + 1)/2 = a.

Let a < q/2. Since a − q < −q/2, we get ε_{0} = a.

Let a = q/2 and b < q/2. If ε_{0} = a − q = −q/2, then by rule (2.7) we have l = 0 (which is impossible since n > 0) or ε_{1} ≤ 0. Since ε_{1} ≡ b + 1 (mod q), this implies ε_{1} = b + 1 − q < −q/2 + 1 (since n > 0, this implies l ≥ 2) and therefore ε_{1} = −q/2. Rule (2.9) leads to a contradiction, which yields ε_{0} = a.

If n = (q + 1)/2 and ε_{0} = a − q = −(q − 1)/2, then we obtain ∑_{i=0}^{l−1} ε_{i+1}q^{i} = 1. We note that from

q^{l−1} ≤ |ε_{l}q^{l−1}| = |1 − ∑_{i=0}^{l−2} ε_{i+1}q^{i}| ≤ 1 + \frac{q}{2} · \frac{q^{l−1} − 1}{q − 1},

we get l ≤ 1 (because 2 ∤ q and therefore q ≥ 3), which implies l = 1 and ε_{1} = 1. This is a contradiction to rule (2.4), which shows ε_{0} = a.

Consider now the case a > q/2. ε_{0} = a yields l = 0, ε_{0} = n = (q + 1)/2, which has been considered above. Therefore ε_{0} = a − q.

We turn to the case a = q/2 and b ≥ q/2. If ε_{0} = a = q/2 then b ≡ ε_{1} (mod q). By rule (2.6) we get ε_{1} ≥ 0 which implies ε_{1} = b ≥ q/2 and therefore ε_{1} = q/2. By rules (2.8) and (2.10) this leads to n = q/2 + q^{2}/2.

Finally, we have to consider n = q/2 + q^{2}/2. If ε_{0} = a − q = −q/2, then we get ∑_{i=0}^{l−1} ε_{i+1}q^{i} = q/2 + 1, i. e. ε′ = (ε_{1}, …, ε_{l}) ∈ R_{q}(q/2 + 1) and ε′ is reduced. By the proven parts of this lemma, this implies (ε_{1}, …, ε_{l}) = (−q/2 + 1, 1) and therefore ε = (−q/2, −q/2 + 1, 1), which is a contradiction to rule (2.5).

Algorithm 1 Computation of the reduced minimal representation of n Input: n > 0, q ≥ 2 integers. Output: ε ∈ R_{q}(n) such that c(ε) = min{c(ε′) : ε′ ∈ R_{q}(n)} and ε is reduced.

ε ← ()

m ← n

while m > 0 do a ← (m mod q). if not (a < q/2 or (a = q/2 and {m/q^{2}} < 1/2) or m = (q +1)/2 or m = q/2+q^{2}/2) then

a ← a − q end if m ← (m − a)/q ε ← ε & a

end while Theorem 1. Let q ≥ 2 and n > 0 be integers. Then there is a unique reduced representation ε ∈ R_{q}(n); this representation is minimal with respect to (1.2), and it can be computed by Algorithm 1.

Proof. The existence follows from Lemma 1 applied to any representation of n.

Let ε = (ε_{0}, …, ε_{l}) ∈ R_{q}(n) be a reduced representation. By Lemma 2, ε_{0} is uniquely given in terms of n. Additionally, ε′ := (ε_{1}, …, ε_{l}) ∈ R_{q}((n−ε_{0})/q) is reduced. By iterating Lemma 2 we see that all digits are uniquely determined by n, which proves uniqueness.

Since {n/q^{2}} = (a + bq)/q^{2} (where a and b are defined as in Lemma 2), we obtain that {n/q^{2}} < 1/2 if and only if b < q/2 (if 2 | q; otherwise, we never have to consider a digit q/2); and therefore, Algorithm 1 computes the reduced representation of n.

Let ε′ ∈ R_{q}(n) be a representation of n with minimum costs. Construct the sequence ε′^{(i)} as in Lemma 1. By this lemma, there is some m ≥ 0 such that f^{m}(ε′) = ε and c(ε) ≤ c(ε′). Therefore, ε has minimum costs.

3. Relaxed Reduced Representations

If we are looking for minimal representations with respect to (1.3), the main ideas of the previous section remain the same, so we will only sketch the differences.

Since the length of a representation is not important, we may think of a representation as of an infinite sequence of integers with finitely many non-zero entries. This implies that we do not have to consider the reduction rules which could only be applied at the end.

Therefore, we define f′ : R_{q}(n) → R_{q}(n) by the reduction rules (as in the previous section, we have to apply the first rule which matches) (2.2), (2.6), (2.7), (2.8) and (2.9). A representation ε is called relaxed reduced, if f′(ε) = ε and (if written as a finite sequence) ε has no trailing zeros. It is easily seen that ε is relaxed reduced if and only if the following conditions are satisfied: (3.1) There are no trailing zeros. (3.2) −q/2 ≤ ε_{i} ≤ q/2 for i ≥ 0. (3.3) If ε_{i} = q/2 then 0 ≤ ε_{i+1} ≤ q/2 − 1. (3.4) If ε_{i} = −q/2 then −q/2 + 1 ≤ ε_{i+1} ≤ 0.

In the proof of the analogue of Lemma 1, the length of the representations is not bounded a priori by c′(ε_{0}). However, if the sequence does not terminate, then there are some M and i_{0} ∈ ℕ such that c′(ε^{(i)}) = M for all i ≥ i_{0}. We note that there cannot be any j such that |ε_{j}^{(i)}| ≥ q for i ≥ i_{0} since we could apply rule (2.2) and the costs would strictly decrease in this case. Therefore, let l_{i} := max{j ∈ ℕ : ε_{j}^{(i)} ≠ 0}, and we get

q^{l_{i}} ≤ n + (q − 1) ∑_{j=l_{i}−M−1}^{l_{i}−1} q^{j} = n + q^{l_{i}} − q^{l_{i}−M+1}.

This implies l ≤ M − 1 + log_{q} n, i. e. ω(ε^{(i)}) lies in the finite set

{−∞, −c(ε^{(0)}) − ⌊log_{q} |n|⌋ + 1, …, 0, …, c(ε^{(0)}) + ⌊log_{q} |n|⌋ − 1, ∞}^{8}

for i ≥ i_{0}, which leads to a contradiction, and the analogue of Lemma 1 is proved. The analogue of Lemma 2 is

Lemma 3. Let n, q be fixed and ε ∈ R_{q}(n) be relaxed reduced. Let a := n mod q and b := (n − a)/q mod q. Then

ε_{0} = \begin{cases}a & if a < q/2 or (a = q/2 and b < q/2), \\ a − q & otherwise, i. e. if a > q/2 or (a = q/2 and b ≥ q/2). \end{cases}

Algorithm 2 Computation of the relaxed reduced minimal representation of n Input: n > 0, q ≥ 2 integers. Output: ε ∈ R_{q}(n) such that c′(ε) = min{c′(ε′) : ε′ ∈ R_{q}(n)} and ε is relaxed reduced.

ε ← ()

m ← n

while m > 0 do a ← (m mod q). if a > q/2 or (a = q/2 and {m/q^{2}} ≥ 1/2) then

a ← a − q end if m ← (m − a)/q ε ← ε & a

end while

This leads to the following result:

Theorem 2. Let q ≥ 2 and n > 0 be integers. Then there is a unique relaxed reduced representation ε ∈ R_{q}(n); this representation is minimal with respect to (1.3), and it can be computed by Algorithm 2.

Finally, we have to clarify the relation between the relaxed reduced and the reduced representations:

Theorem 3. Let q ≥ 2 and n > 0 be integers and ε = (ε_{0}, …, ε_{l}) and ε′ = (ε′_{0}, …, ε′_{l′}) the reduced and the relaxed reduced representation of n, respectively.

Then we have the following relations

(3.5)  ε = \begin{cases}(ε′_{0}, …, ε_{l′−2}, (q + 1)/2) & if (ε′_{l′−1}, ε′_{l′}) = (−(q − 1)/2, 1), \\ (ε′_{0}, …, ε_{l′−3}, q/2, q/2) & if (ε′_{l′−2}, ε′_{l′−1}, ε′_{l′}) = (−q/2, −q/2 + 1, 1), \\ ε′ & otherwise, \end{cases}

(3.6)  ε′ = \begin{cases}(ε_{0}, …, ε_{l−1}, −(q − 1)/2, 1) & if ε_{l} = (q + 1)/2, \\ (ε_{0}, …, ε_{l−2}, −q/2, −q/2 + 1, 1) & if (ε_{l−1}, ε_{l}) = (q/2, q/2), \\ ε & otherwise. \end{cases}

Proof. It is obvious that f(ε′) = ε′ unless ε′ corresponds to one of the two exceptional cases in (3.5), in which f(ε′) is the expression on the right hand side of (3.5). To see that this expression is indeed reduced, we note that the only rules which might apply are (2.10) and (2.7), but this cannot be the case since ε′ was relaxed reduced which implies that ε′_{l′−3} ∉ {±q/2}. The other direction follows easily.

4. Formula for Odd q

Theorem 4. Let q ≥ 3 be odd and n be a positive integer. Let

ε_{r} := b_{q}^{(r)}(2n) − b_{q}^{(r)}(n), r ≥ 0,

where b_{q}^{(r)}(n) is the r-th digit of the “usual” q-adic expansion of n, i. e.

b_{q}^{(r)}(n) = ⌊\frac{n}{q^{r}} ⌋ − q ⌊\frac{n}{q^{r+1}} ⌋ ,

and l := max{r ≥ 0 : ε_{r} ≠ 0}. Then ε = (ε_{0}, …, ε_{l}) is the relaxed reduced minimal representation.

Proof. By definition, we have

ε_{r} = b_{q}^{(r)}(2n) − b_{q}^{(r)}(n) = ⌊\frac{2n}{q^{r}}⌋ − q ⌊\frac{2n}{q^{r+1}} ⌋ − ⌊\frac{n}{q^{r}} ⌋ + q ⌊\frac{n}{q^{r+1}} ⌋

= ⌊2q \frac{n}{q^{r+1}} ⌋ − q ⌊2\frac{n}{q^{r+1}} ⌋ − ⌊q \frac{n}{q^{r+1}} ⌋ + q ⌊\frac{n}{q^{r+1}} ⌋ .

For any positive integer a and any real number x the relation

⌊ax⌋ = ∑_{i=0}^{a−1} ⌊x + \frac{i}{a}⌋ (4.1)

is well-known (see for instance [7, 3.26]). Setting x := n/q^{r+1} we obtain

ε_{r} = ∑_{l=0}^{2q−1} ⌊x + \frac{l}{2q} ⌋ − q (⌊x⌋ + ⌊x + \frac{1}{2}⌋) − ∑_{l=0}^{q−1} ⌊x + \frac{l}{q} ⌋ + q ⌊x⌋

= −(q − 1) ⌊x + \frac{1}{2}⌋ + ∑_{\begin{matrix}m=0 \\ m≠(q−1)/2 \end{matrix}}^{q−1} ⌊x + \frac{2m + 1}{2q}⌋ .

Let 0 ≤ j ≤ q such that

\frac{2j − 1}{2q} ≤ \{x\} < \frac{2j + 1}{2q}.

Then

∑_{m=0}^{q−1} ⌊x + \frac{2m + 1}{2q}⌋ = q ⌊x⌋ + j

q ⌊x + \frac{1}{2}⌋ = q ⌊x⌋ + q [j ≥ \frac{q + 1}{2}] ,

which shows that

−\frac{q − 1}{2} ≤ ε_{r} ≤ \frac{q − 1}{2}. (4.2)

By construction, ε_{r} ∈ R_{q}(n). By (3.2) and (4.2) we see that ε_{r} is the relaxed reduced representation of n.

5. Formula for Even q

We derive a formula for the digits of the relaxed reduced expansion (which yields a formula for the reduced expansion by Theorem 3), which will enable us to study the distribution of the digits in the next section.

Theorem 5. Let q ≥ 2 be even. For r ≥ 0 define

\begin{matrix}ε_{r} := ∑_{i=0}^{q/2−1}( ∑_{j=0}^{q/2−1} & ⌊\frac{n}{q^{r+2}} + \frac{1 + \frac{q}{2} + (q + 1)(iq + j)}{q^{2}(q + 1)}⌋ \\ −(q − 1) & ⌊\frac{n}{q^{r+2}} + \frac{\frac{q}{2} + (q + 1)(iq + q/2)}{q^{2}(q + 1)}⌋ \\ + ∑_{j=q/2+1}^{q−1} & ⌊\frac{n}{q^{r+2}} + \frac{\frac{q}{2} + (q + 1)(iq + j)}{q^{2}(q + 1)}⌋) \\ + ∑_{i=q/2}^{q−1}( ∑_{j=0}^{q/2−2} & ⌊\frac{n}{q^{r+2}} + \frac{1 + \frac{q}{2} + (q + 1)(iq + j)}{q^{2}(q + 1)}⌋ \\ −(q − 1) & ⌊\frac{n}{q^{r+2}} + \frac{1 + \frac{q}{2} + (q + 1)(iq + q/2 − 1)}{q^{2}(q + 1)}⌋ \\ + ∑_{j=q/2}^{q−1} & ⌊\frac{n}{q^{r+2}} + \frac{\frac{q}{2} + (q + 1)(iq + j)}{q^{2}(q + 1)}⌋). \end{matrix} (5.1)

Let l := max{r ≥ 0 : ε_{r} ≠ 0}. Then ε = (ε_{0}, …, ε_{l}) ∈ R_{q}(n) is the relaxed reduced minimal representation.

Example 1. For q = 2, (5.1) is

ε_{r} = ⌊\frac{n}{2^{r+2}} + \frac{5}{6}⌋ − ⌊\frac{n}{2^{r+2}} + \frac{4}{6}⌋ − ⌊\frac{n}{2^{r+2}} + \frac{2}{6}⌋ + ⌊\frac{n}{2^{r+2}} + \frac{1}{6}⌋ , (5.2)

which is the formula also obtained in [14] (cf. Section 7).

Example 2. It is perhaps a good idea to explain what the formula (5.1) does, which we will do for the instance q = 6:

ε_{r} = + ⌊y + \frac{248}{252}⌋ + ⌊y + \frac{241}{252}⌋ + ⌊y + \frac{234}{252}⌋ − 5 ⌊y + \frac{228}{252}⌋ + ⌊y + \frac{221}{252}⌋ + ⌊y + \frac{214}{252}⌋

+ ⌊y + \frac{206}{252}⌋ + ⌊y + \frac{199}{252}⌋ + ⌊y + \frac{192}{252}⌋ − 5 ⌊y + \frac{186}{252}⌋ + ⌊y + \frac{179}{252}⌋ + ⌊y + \frac{172}{252}⌋

+ ⌊y + \frac{164}{252}⌋ + ⌊y + \frac{157}{252}⌋ + ⌊y + \frac{150}{252}⌋ − 5 ⌊y + \frac{144}{252}⌋ + ⌊y + \frac{137}{252}⌋ + ⌊y + \frac{130}{252}⌋

+ ⌊y + \frac{122}{252}⌋ + ⌊y + \frac{115}{252}⌋ − 5 ⌊y + \frac{108}{252}⌋ + ⌊y + \frac{102}{252}⌋ + ⌊y + \frac{95}{252}⌋ + ⌊y + \frac{88}{252}⌋

+ ⌊y + \frac{80}{252}⌋ + ⌊y + \frac{73}{252}⌋ − 5 ⌊y + \frac{66}{252}⌋ + ⌊y + \frac{60}{252}⌋ + ⌊y + \frac{53}{252}⌋ + ⌊y + \frac{46}{252}⌋

+ ⌊y + \frac{38}{252}⌋ + ⌊y + \frac{31}{252}⌋ − 5 ⌊y + \frac{24}{252}⌋ + ⌊y + \frac{18}{252}⌋ + ⌊y + \frac{11}{252}⌋ + ⌊y + \frac{4}{252}⌋ ,

where y = n/6^{r+2}.

Let us think about y as a real variable. It is plain to see that the expression with q^{2} terms is periodic in y. For y = 0 it is 0; when y reaches \frac{4}{252}, the first term changes to 1; when y reaches \frac{11}{252}, the second term also changes to 1, and so on. Accordingly, the digit changes from 0 to 1, then to 2, then to 3, then to −2, −1, 0. That describes the first line of terms. This patterns repeats twice, but then in the second half the general pattern switches from 0, 1, 2, 3, −2, −1 to 0, 1, 2, −3, −2, −1. The digits 0, 1, 2, 3, −2, −1 are not symmetric around 0, and 0, 1, 2, −3, −2, −1 are not, either. However, in combination, both coming with “probability” \frac{1}{2}, the distribution of the digits becomes symmetric.

Proof. We rewrite (5.1) as

ε_{r} = ∑_{i=0}^{q−1} ∑_{j=0}^{q−1} ⌊\frac{n}{q^{r+2}} + \frac{j}{q^{2}} + \frac{[j < q/2] + q/2}{q^{2}(q + 1)} + \frac{i}{q} ⌋ − q ∑_{i=0}^{q−1} ⌊\frac{n}{q^{r+2}} + \frac{i}{q} + \frac{[i < q/2] + q/2}{q(q + 1)}⌋ . (5.3)

Interchanging the order of summation in the first part, using (4.1), renaming i to j in the second part and collecting the two resulting sums, we get

ε_{r} = ∑_{j=0}^{q−1}(⌊\frac{n}{q^{r+1}} + \frac{j}{q} + \frac{[j < q/2] + q/2}{q(q + 1)}⌋ − q ⌊\frac{n}{q^{r+2}} + \frac{j}{q} + \frac{[j < q/2] + q/2}{q(q + 1)}⌋).

Therefore, we calculate that

∑_{r=0}^{∞} ε_{r}q^{r} = ∑_{j=0}^{q−1} ⌊\frac{n}{q} + \frac{j}{q} + \frac{[j < q/2] + q/2}{q(q + 1)}⌋ . (5.4)

We write n = r + sq for 0 ≤ r < q and observe that for an integer 0 ≤ m < 2q and for σ ∈ {0, 1}

⌊\frac{m}{q} + \frac{σ + q/2}{q(q + 1)}⌋ = [m ≥ q] .

Evaluating (5.4) in this way we obtain

∑_{r=0}^{∞} ε_{r}q^{r} = ∑_{j=0}^{q−1} (s + [j ≥ q − r]) = n, (5.5)

and we proved that ε = (ε_{0}, …, ε_{l}) ∈ R_{q}(n) is indeed a representation of n.

In order to investigate further properties of ε we fix some r ≥ 0, write x := {n/q^{r+2}} and define

ξ_{i,j} := \frac{[j < q/2] + q/2 + (q + 1)(iq + j)}{q^{2}(q + 1)}  and  h_{i,j} := ⌊x + ξ_{i,j}⌋ (5.6)

for i, j ∈ {0, …, q − 1}. We note that for (i, j) <_{lex} (i′, j′) we have 0 < ξ_{i,j} < ξ_{i′,j′} < 1 and rewrite (5.1) as

\begin{aligned}ε_{r} & = & ∑_{i=0}^{\frac{q}{2} −1} & h_{i,0} & + & … & + & h_{i, \frac{q}{2} −2} & + & h_{i, \frac{q}{2} −1} & −(q − 1) & h_{i, \frac{q}{2}} & + & h_{i, \frac{q}{2} +1} & + & … & + & h_{i,q−1} \\ & + & ∑_{i= \frac{q}{2}}^{q−1} & h_{i,0} & + & … & + & h_{i, \frac{q}{2} −2} & −(q − 1) & h_{i, \frac{q}{2} −1} & + & h_{i, \frac{q}{2}} & + & h_{i, \frac{q}{2} +1} & + & … & + & h_{i,q−1}. \end{aligned}

Choose (i_{0}, j_{0}) lexicographically minimal such that x + ξ_{i_{0},j_{0}} ≥ 1 — if x + ξ_{q−1,q−1} < 1 then we set (i_{0}, j_{0}) := (∞, ∞) —, which implies that h_{i,j} = [(i, j) ≥_{lex} (i_{0}, j_{0})] and therefore

(5.7) ε_{r} =

\begin{cases}h_{i_{0},0} & + & … & + & h_{i_{0}, \frac{q}{2} −2} & + & h_{i_{0}, \frac{q}{2} −1} & −(q − 1) & h_{i_{0}, \frac{q}{2}} & + & h_{i_{0}, \frac{q}{2} +1} & + & … & + & h_{i_{0},q−1} & if i_{0} < \frac{q}{2} \\ h_{i_{0},0} & + & … & + & h_{i_{0}, \frac{q}{2} −2} & −(q − 1) & h_{i_{0}, \frac{q}{2} −1} & + & h_{i_{0}, \frac{q}{2}} & + & h_{i_{0}, \frac{q}{2} +1} & + & … & + & h_{i_{0},q−1} & if i_{0} ≥ \frac{q}{2} \\ 0 & & & & & & & & & & & & & & & if i_{0} = ∞. \end{cases}

From (5.7) we see that |ε_{r}| ≤ q/2 and that

\begin{aligned}ε_{r} & = q/2 & ⟺ & j_{0} & = q/2 and i_{0} ≥ q/2 \\ ε_{r} & = −q/2 & ⟺ & j_{0} & = q/2 and i_{0} < q/2. \end{aligned} (5.8)

Assume j_{0} = q/2. By definition of (i_{0}, j_{0}) and by (5.6) this implies that

⌊\frac{n}{q^{2+r}} ⌋ + 1 − \frac{i_{0}}{q} − \frac{q + 2}{2q(q + 1)} ≤ \frac{n}{q^{2+r}} < ⌊\frac{n}{q^{2+r}} ⌋ + 1 − \frac{i_{0}}{q} − \frac{1}{2(q + 1)}.

Dividing by q, denoting x′ := {n/q^{3+r}} and a_{r+2} := ⌊n/q^{2+r}⌋ − q ⌊n/q^{3+r}⌋ — we remark that 0 ≤ a_{r+2} < q —, we obtain

\frac{a_{r+2} + 1}{q} − \frac{i_{0}}{q^{2}} − \frac{q + 2}{2q^{2}(q + 1)} ≤ x′ < \frac{a_{r+2} + 1}{q} − \frac{i_{0}}{q^{2}} − \frac{1}{2q(q + 1)}. (5.9)

Define

(5.10) (i_{1}, j_{1}) := \begin{cases}(q − 1 − a_{r+2}, i_{0} + 1) & if q/2 ≤ i_{0} < q − 1 \\ (q − a_{r+2}, 0) & if i_{0} = q − 1 and a_{r+2} ≠ 0 \\ (∞, ∞) & if i_{0} = q − 1 and a_{r+2} = 0 \\ (q − 1 − a_{r+2}, i_{0}) & if 0 ≤ i_{0} < q/2. \end{cases}

Using (5.9) we check that in all cases, (i_{1}, j_{1}) is lexicographically minimal such that x′ + ξ_{i_{1},j_{1}} ≥ 1. From (5.8), (5.10), and (5.7) we can deduce that

\begin{aligned}ε_{r} & = q/2 & ⟹ & ε_{r+1} & ∈ \{0, …, q/2 − 1\} \\ ε_{r} & = −q/2 & ⟹ & ε_{r+1} & ∈ \{−q/2 + 1, …, 0\}. \end{aligned} (5.11)

From the fact that |ε_{i}| ≤ q/2, (5.11), (3.2), (3.3), and (3.4), we conclude that ε is indeed the relaxed reduced expansion.

6. Counting Digits in the Minimal Representations

We are interested to count how often a given digit i occurs in the relaxed reduced expansion among the numbers 1, …, n; call that #_{i}(n). By Theorem 3 the corresponding values for the reduced expansion will differ by at most 2n, which will not appear in the main term of the asymptotic formula anyway.

In the case q odd, the reduced representation is actually the (q, d) representation, with d = −\frac{q−1}{2}, and digits d, d + 1, …, d + q − 1. Digit counting in this representation is well known, see [11]. Every digit occurs with the same frequency \frac{1}{q}, and

#_{i}(n) = \frac{1}{q}n log_{q} n + O(n). (6.1)

Actually, more is known about the error term. It can be made fully explicit and is basically given by n times a periodic function in log_{q} n. Here, we don’t bother to compute the periodic functions in detail.

Summing (6.1), (multiplied by |i|), over all possible digits i, we get the average value of c′(ε). It is

(\frac{q}{4} − \frac{1}{4q} ) log_{q} n + O(1);

the constant is computed via

2 ∑_{i=1}^{(q−1)/2} i\frac{1}{q}.

In the instance q even, things are a bit more complicated, but fortunately not by much. The formula (5.1) tells us that digit 0 occurs with frequency \frac{q+2}{q(q+1)}, digits ±1, …, ±\frac{q}{2} − 1 with frequency \frac{1}{q}, digits ±\frac{q}{2} each with frequency \frac{1}{2(q+1)}. So we see that digit 0 appears a bit more often than the other digits, and the digits ±\frac{q}{2} (combined) appear a bit less often than the other digits. In terms of costs, this is fortunate. Anyway, it leads to

#_{0}(n) = \frac{q + 2}{q(q + 1)}n log_{q} n + O(n),
#_{i}(n) = \frac{1}{q}n log_{q} n + O(n),  for i = ±1, …, ±\frac{q}{2} − 1,
#_{i}(n) = \frac{1}{2(q + 1)}n log_{q} n + O(n),  for i = ±\frac{q}{2}.

Again, summing this, (multiplied by |i|), over all possible digits i, we get the average value of ∑ |ε_{i}|:

(\frac{q}{4} − \frac{1}{2(q + 1)}) log_{q} n + O(1).

The computation of the constant is done via

2 ∑_{i=1}^{q/2−1} i\frac{1}{q} + 2\frac{q}{2} \frac{1}{2(q + 1)}.

The average length of the representation is given by log_{q} n + O(1).

We sum up these results in the following theorem:

Theorem 6. Let q ≥ 2 and n ≥ 1. Then the average costs c(ε) of the reduced expansions of the integers 1, …, n are

(1 + \frac{q}{4} − \frac{1}{2(q + 1)}) log_{q} n + O(1)  if q is even,
(1 + \frac{q}{4} − \frac{1}{4q} ) log_{q} n + O(1)  if q is odd.

7. Previous Work

We start our overview on related papers with the relaxed reduced expansion for q = 2. In this case, (3.2), (3.3), and (3.4) are clearly equivalent to ε_{i} ∈ {0, ±1} and ε_{i}ε_{i+1} = 0. This means that for q = 2 our relaxed reduced expansion is the so-called “non-adjacent-form” (NAF) or “sparse signed digit representation” or “balanced binary representation” or “Paul representation” (cf. Güntzer and Paul [8]) which has been studied — at least partly independently — by several authors; we refer to [1, IV.2.4] and [6] for some references. It goes back at least to Reitwiesner [15], who proved existence and uniqueness of a NAF and that it has minimum c′. Jedwab and Mitchell [10] describe an algorithm which computes the NAF from every redundant binary expansion with digits 0, ±1.

Morain and Olivos [13] first applied the idea to elliptic curves as sketched in the introduction and empirically found two algorithms, which yield good results. Actually, the second of these algorithms leads exactly to the NAF, therefore, Morain and Olivos reach the minimum c′ (and by Theorem 3 the minimum c by up to one). They give the main term of the expected costs (as in our calculations in Section 6), whereas Thuswaldner [16] gives a further asymptotic term. Further properties of the NAF have been described by the second author in [14].

Demetrovics, Pethő, and Rónyai [5] take up Morain and Olivos’ motivation and consider c for q = 2. They translate the minimization problem into an infinite graph where minimal expansions correspond to shortest paths and apply Dijkstra’s algorithm to the solution of the problem. This has been generalized to general q by the first author in [9], and it was proved that there exists a minimal expansion such that |ε_{i}| ≤ q/2, which characterizes the case of odd q almost completely. It is worth noting that [9, Algorithm 1] is not guaranteed to yield an expansion with digits |ε_{i}| ≤ q/2 because the choice between two paths of equal length leading to the same vertex is made arbitrarily. If expansions with small digits are preferred, then the algorithm yields the reduced representation of our Algorithm 1. Of course, both algorithms need O(log_{q} n) time, computational experiments show that Algorithm 1 is faster by a factor of 3.

Another generalization of the non-adjacent-form to arbitrary bases is described in Clark and Liang [3]. It is unique, minimizes c′′(ε) := card{i : ε_{i} ≠ 0} and can be computed from the usual q-adic expansions of (q + 1)/q and 1/q, similarly to our Theorem 4. In the case q = 2, this property goes back to Chang and Tsao-Wu [2].

The generalized NAF (GNAF) and our reduced expansions were designed for different cost functions, however, it may be instructive to compare how the two expansions behave with respect to both cost functions. To this aim, we calculate an explicit formula for the r-th digit of the GNAF as we did it for the reduced expansion in Section 4 and we follow the lines of Section 6. The result is shown in Table 1.

Expansion  Expected c′(ε)  Expected c′′(ε)
Clark and Liang  \frac{q − 1}{3} log_{q} n + O(1)  (1 − \frac{2}{q + 1}) log_{q} n + O(1)
Relaxed Reduced, even q (\frac{q}{4} − \frac{1}{2(q + 1)}) log_{q} n + O(1) (1 − \frac{q + 2}{q(q + 1)}) log_{q} n + O(1)
Relaxed Reduced, odd q (\frac{q}{4} − \frac{1}{4q} ) log_{q} n + O(1)  (1 − \frac{1}{q}) log_{q} n + O(1)

Table 1. Comparison of the GNAF and the relaxed reduced expansion

References

[1] I. Blake, G. Seroussi, and N. Smart, Elliptic curves in cryptography, London Mathematical Society Lecture Note Series, vol. 265, Cambridge University Press, 1999.

[2] S. H. Chang and N. Tsao-Wu, Distance and structure of cyclic arithmetic codes, Proc. Hawaii International Conference on System Sciences, vol. 1, 1968, pp. 463–466.

[3] W. Edwin Clark and J. J. Liang, On arithmetic weight for a general radix representation of integers, IEEE Trans. Information Theory IT-19 (1973), 823–826.

[4] J.-S. Coron, Resistance against differential power analysis for elliptic curve cryptosystems, Workshop on Cryptographic Hardware and Embedded Systems (Ç. Koç and Ch. Paar, eds.), Lecture Notes in Computer Science, vol. 1717, Springer, 1999, pp. 292–302.

[5] J. Demetrovics, A. Pethő, and L. Rónyai, On ±1-representations of integers, Acta Cybernet. 14 (1999), 27–36.

[6] D. M. Gordon, A survey of fast exponentiation methods, J. Algorithms 27 (1998), no. 1, 129–146.

[7] R. L. Graham, D. E. Knuth, and O. Patashnik, Concrete mathematics. A foundation for computer science, second ed., Addison-Wesley Publishing Company, Reading, MA, 1994.

[8] U. Güntzer and M. Paul, Jump interpolation search trees and symmetric binary numbers, Inform. Process. Lett. 26 (1987), no. 4, 193–204.

[9] C. Heuberger, Minimal expansions in redundant number systems and shortest paths in graphs, Computing 63 (1999), 341–349.

[10] J. Jedwab and C. J. Mitchell, Minimum weight modified signed-digit representations and fast exponentiation, Electron. Lett. 25 (1989), no. 17, 1171–1172.

[11] P. Kirschenhofer and H. Prodinger, Subblock occurrences in positional number systems and Gray code representation, J. Inform. Optim. Sci. 5 (1984), no. 1, 29–42.

[12] D. E. Knuth, Seminumerical algorithms, The Art of Computer Programming, vol. 2, Addison-Wesley, Bonn, 1998.

[13] F. Morain and J. Olivos, Speeding up the computations on an elliptic curve using addition-subtraction chains, RAIRO Inform. Théor. Appl. 24 (1990), no. 6, 531–543.

[14] H. Prodinger, On binary representations of integers with digits −1, 0, 1, Integers 0 (2000), A08, avail-

able at http://www.integers-ejcnt.org/vol0.html.

[15] G. W. Reitwiesner, Binary arithmetic, Advances in computers, Vol. 1, Academic Press, New York, 1960, pp. 231–308.

[16] J. M. Thuswaldner, Summatory functions of digital sums occurring in cryptography, Period. Math. Hungar. 38 (1999), 111–130.

Institut für Mathematik, Technische Universität Graz, Steyrergasse 30, A-8010 Graz, Austria

E-mail address: cheub@weyl.math.tu-graz.ac.at
URL: http://finanz.math.tu-graz.ac.at/~cheub/

The John Knopfmacher Centre for Applicable Analysis and Number Theory, Department of Mathematics, University of the Witwatersrand, P. O. Wits, 2050 Johannesburg, South Africa

E-mail address: helmut@gauss.cam.wits.ac.za
URL: http://www.wits.ac.za/helmut/index.htm