Cryptography Reference
In-Depth Information
The associated addition chain is obtained by considering the exponents to
powers of
a
that arise as intermediate results in this process:
e
k
−
1
,
e
k
−
1
·
2
,
e
k
−
1
·
2+
e
k
−
2
,
(
e
k
−
1
·
2
,
(
e
k
−
1
·
2+
e
k
−
2
)
·
2+
e
k
−
3
,
((
e
k
−
1
·
2+
e
k
−
2
)
·
2+
e
k
−
3
)
·
2
,
.
(
···
((
e
k
−
1
·
2+
e
k
−
2
)
·
2+
e
k
−
3
)
·
2+
···
+
e
1
)
·
2+
e
0
.
Here terms of the sequence are omitted if
e
j
=0
for a particular
j
. For the
number 123, for example, based on the binary method the result is the following
addition chain with 12 elements: 1, 2, 3, 6, 7, 14, 15, 30, 60, 61, 122, 123.
In general, a sequence of numbers
1=
a
0
,a
1
,a
2
,...,a
r
=
e
for which for
every
i
=1
,...,r
there exists a pair
(
j, k
)
with
j ≤ k<i
such that
a
i
=
a
j
+
a
k
holds is called an
addition chain for
e
of length
r
.
The
M
-ary method generalizes this principle for the representation of the
exponent to other bases. Both methods have the goal of producing addition
chains that are as short as possible, in order to minimize the calculational expense
for the exponentiation. The addition chain for 123 produced by the
2
3
-ary
method is 1, 2, 3, 4, 7, 8, 15, 30, 60, 120, 123; with the
2
4
-ary method the addition
chain 1, 2, 3, 4, 7, 11, 14, 28, 56, 112, 123 is created. These last chains are, as
expected, considerably shorter than those obtained by the binary method, which
for larger numbers will have a greater effect than in this example. In view of the
real savings in time one must, however, note that in the course of initialization for
the calculation of
a
e
mod
n
the
M
-ary methods construct the powers
a
2
,
a
3
,
a
5
,
a
M
−
1
also for those exponents that are not needed in the representation of
e
to
the base
M
or for the construction of the addition chain.
Binary exponentiation represents the worst case of an addition chain: By
considering it we obtain a bound on the greatest possible length of an addition
chain of
log
2
e
+
H
(
e
)
2+
e
k
−
2
)
·
1
,where
H
(
e
)
denotes the Hamming weight of
e
.
1
The
length of an addition chain is bounded below by
log
2
e
+ log
2
H
(
e
)
−
2
.
13
,and
so a shorter addition chain for
e
is not to be found (cf. [Scho] or [Knut], Section
4.6.3, Exercises 28, 29). For our example this means that the shortest addition
chain for
e
= 123
haslengthatleast
8
, and so the results of the
M
-ary methods
cited earlier seem not to be the best possible.
−
If
n
possesses a representation
n
=(
n
k
−
1
n
k
−
2
...n
0
)
2
, then
H
(
n
)
is defined as
i
n
i
.
(See [HeQu], Chapter 8.)
1
