Cryptography Reference
In-Depth Information
Also show that if
a>
0 then
a
l
=
1 and prove that the length of a NAF is at most one more
than the length of the binary expansion of
a
.
Definition 11.1.10
Let
D
⊂ Z
be such that 0
∈
D
.The
weight
of a representation
a
=
l
i
=
0
a
i
2
i
where
a
i
∈
D
is the number of values 0
≤
i
≤
l
such that
a
i
=
0. The weight of
a
is denoted weight(
a
). The
density
of the representation is weight(
a
)
/
(
l
+
1).
a<
2
l
+
1
and represented
using the standard binary expansion then the expected value of the weight is (
l
is uniformly chosen in 2
l
Exercise 11.1.11
Show that if
a
∈ N
≤
+
1)
/
2 and
therefore the expected value of the density is 1
/
2.
Theorem 11.1.12
The NAF of an integer a
∈ N
has minimal weight among all signed
=
l
i
=
0
a
i
2
i
where a
i
∈{−
expansions a
1
,
0
,
1
}
.
=
l
i
=
0
a
i
2
i
where
a
i
∈{−
Proof
Let
a
be any signed expansion of
a
. Perform
the following string re-writing process from right to left (i.e., starting with
a
0
). If
a
i
=
1
,
0
,
1
}
0
or
a
i
+
1
=
0 then do nothing. Otherwise (i.e.,
a
i
=
0 and
a
i
+
1
=
0) there exists an integer
k
≥
1 such that the sequence
a
i
+
k
a
i
+
k
−
1
...a
i
a
i
−
1
is of the form
01
...
10
,
11
...
10
,
11
...
10
,
01
...
10
.
In each case, replace the pattern with the following
10
...
010
,
0
...
010
,
0
...
010
,
10
...
010
.
In each case, the resulting substring has weight less than or equal to the weight of the
previous substring and is in non-adjacent form (at least up to
a
i
+
k
−
1
a
i
+
k
=
0). Continuing
the process therefore yields a NAF expansion of
a
of weight less than or equal to the weight
of the original signed expansion.
Example 11.1.13
We re-compute the NAF representation of
a
91, using the method in
the proof of Theorem
11.1.1
2
. First, note th
a
t the binary expansion of 91 is
10
11011. One
replaces the initial 011 by 101 to get 10
11
1
0
1
.
One then replaces 0111 by 1001. Continuing
one determines the NAF of 91 to be 10100101.
=
We have established that the NAF of an integer
a
is unique, has minimal weight and has
length at most one bit more than the binary expansion of
a
. Finally, we sketch a probabilistic
argument that shows that the density of a NAF is expected to be 1
/
3.
Lemma 11.1.14
Let l
. Define d
l
to be the expected value of the density of the NAF
representation of uniformly chosen integers
2
l
+
1
/
3
<a<
2
l
+
2
/
3
. Then d
l
tends to
1
/
3
as
l goes to infinity.
∈ N
=
l
i
=
0
a
i
2
l
for the NAF representation of
a
Proof
(Sketch) Write
a
∈ N
. Note that Algo-
rithm
6
has the property that if
a
i
=
0, but the value of
a
i
+
2
is independent of
the previous operations of the algorithm. Hence, if the bits of
a
are considered to be chosen
uniformly at random then the probability that
a
i
+
2
=
0 then
a
i
+
1
=
0is1
/
2. Similarly, the probability
