Cryptography Reference
In-Depth Information
that
a
i
+
2
=
0but
a
i
+
3
=
0is1
/
4, and so on. Hence, the expected number of zeroes after
the non-zero
a
i
is
∞
1
1
1
i
2
i
=
·
2
+
·
4
+
·
8
+···=
E
1
2
3
i
=
1
(at least approximately, since the expansion is not infinite).
Now
∞
∞
∞
i
2
i
−
1
i
2
i
1
2
j
E
=
2
E
−
E
=
−
=
1
+
=
2
.
i
=
1
i
=
1
j
=
1
Hence, on average, there are two zeroes between adjacent non-zero coefficients and the
density tends to 1
/
3.
Exercise 11.1.15
Prove that the number of distinct NAFs of length
k
is (2
k
+
2
−
−
1)
k
)
/
3.
(
Exercise 11.1.16
Write down an algorithm to list all NAFs of length
k
.
For some applications it is desired to compute a low-density signed expansion from left
to right; Joye and Yen [
287
] give an algorithm to do this.
Generalisations of the NAF are the width-
w
non-adjacent form (
w
-NAF) and fractional
window NAFs. We refer to Miyaji, Ono and Cohen [
386
], Section IV.2.5 of Blake, Seroussi
and Smart [
60
] and Section 3.2 of Solinas [
517
] for the former, and M oller [
388
,
389
]for
the latter. For fast exponentiation, one can perform sliding windows over fractional NAFs
or sliding fractional windows over NAFs.
11.2 Multi-exponentiation
An
n
-dimensional
multi-exponentiation
(also called
simultaneous multiple exponenti-
ation
) is the problem of computing a product
g
a
1
1
g
a
n
. The question of how efficiently
this can be done was asked by Richard Bellman as problem 5125 of volume 70, number
6ofthe
American Mathematical Monthly
in 1963. A solution was given by E. G. Straus
2
in [
534
]; the idea was re-discovered by Shamir and is often attributed to him. We only give
a brief discussion of this topic and refer to Section 9.1.5 of [
16
] and Section 3.3.3 of [
248
]
for further details.
Algorithm
7
computes an
n
-dimensional multi-exponentiation. We write
a
i,j
for the
j
th
bit of
a
i
(where, as usual in this topic, the least significant bit is
a
i,
0
); if
j>
log
2
(
a
i
) then
a
i,j
=
···
0. The main idea is to use a single accumulating variable (in this case called
h
)
and to perform only one squaring. If a value
g
i
does not change between executions of the
algorithm then we call it a
fixed base
and otherwise it is a
variable base
(the precomputation
can be improved when some of the
g
i
are fixed). We assume that the integers
a
i
all vary.
2
Straus had the remarkable ability to solve crossword puzzles in English (his third language) using only the horizontal clues; see
his commemorative issue of the
Pacific Journal of Mathematics
.
