Cryptography Reference
In-Depth Information
groups is easy (see Section
9.1
and Exercises
10.4.2
and
10.4.17
). Hence, one can exploit
inversion when computing exponentiation and it is desirable to consider signed expansions
for exponents.
Signed expansions and addition-subtraction chains have a long history.
1
Morain and
Olivos [
394
] realised that, since inversion is easy for elliptic curve groups, signed expansions
are natural in this context.
11.1.1 Non-adjacent form
We now discuss the non-adjacent form (NAF) of an integer
a
. This is the best signed
expansion in the sense that it has the minimal number of non-zero coefficients and can be
computed efficiently. The non-adjacent form was discussed by Reitwiesner [
449
] (where
it is called “property M”). Reitwiesner proved that the NAF is unique, has minimal weight
among binary expansions with coefficients in
and he gave an algorithm to
compute the NAF of an integer. These results have been re-discovered and simplified
numerous times (we refer to Section IV.2.4 of [
60
] and Section 5 of [
490
] for references).
{−
1
,
0
,
1
}
=
l
i
=
0
a
i
2
i
is a
non-adjacent form
or
Definition 11.1.1
Let
a
∈ N
. A representation
a
NAF
if
a
i
∈{−
1
,
0
,
1
}
for all 0
≤
i
≤
l
and
a
i
a
i
+
1
=
0 for all 0
≤
i<l
.If
a
l
=
0 then the
length
of the NAF is
l
+
1.
One can transform an integer
a
into NAF representation using Algorithm
6
.Thisis
a “right-to-left” algorithm in the sense that it processes the least significant bits first.
We define the operator
a
(mods 2
m
) to be reduction of
a
modulo 2
m
to the range
{−
m
+
1
,...,
−
1
,
0
,
1
,...,m
}
. In particular, if
a
is odd then
a
(mods 4)
∈{−
1
,
1
}
. An alternative
right-to-left algorithm is given in the proof of Theorem
11.1.12
.
Algorithm 6
Convert an integer to non-adjacent form
INPUT:
a
∈ N
OUTPUT: (
a
l
...a
0
)
1:
i
0
2:
while
a
=
=
0
do
if
a
even
then
3:
a
i
=
0
4:
else
5:
a
i
=
a
(mods 4)
6:
end if
7:
=
−
a
(
a
a
i
)
/
2
8:
i
=
i
+
1
9:
10:
end while
11:
return
a
l
...a
0
1
Reitwiesner's long paper [
449
] suggests signed expansions as a way to achieve faster arithmetic (e.g., multiplication and
division), but does not discuss exponentiation. Brickell, in 1982, seems to have been the first to suggest using negative powers of
g
to speed up the computation of
g
a
; this was in the context of computing
m
e
(mod
N
) in RSA and required the precomputation
of
m
−
1
(mod
N
).
