Cryptography Reference
In-Depth Information
Exercise 11.1.2
Prove that Algorithm
6
outputs a NAF.
Example 11.1.3
We compute the NA
F
representation of
a
=
91. Since 91
≡
3(mod4)the
1, which we denote as
1
. Note that 2
2
first digit is
−
92 so the next digit is 0. Now, 92
/
4
=
3 (mod 4) and the nex
t
di
gi
t
is
1. Since 2
3
23
≡
24 the next 2 digits are 0. Continuing one
finds the expansion to be 10100101.
Lemma
11.1.4
shows that a simple way to compute a NAF of an integer
a
is to compute
the binary representation of 3
a
, subtract the binary representation of
a
(writing the result
in signed binary expansion; in other words, performing the subtraction without carries) and
discard the least significant bit. We write this as ((3
a
)
−
a
)
/
2.
Lemma 11.1.4
Let a
∈ N
. Then the signed binary expansion
((3
a
)
−
(
a
))
/
2
is in non-
adjacent form.
Proof
Write
a
in binary as (
a
l
...a
0
)
2
and write 3
a
in binary as (
b
l
+
2
...b
0
)
2
. Set
a
−
1
=
a
l
+
1
=
a
l
+
2
=
0 and
c
−
1
=
0. Then
b
i
=
a
i
+
a
i
−
1
+
c
i
−
1
−
2
c
i
where
c
i
=
(
a
i
+
a
i
−
1
+
c
i
−
1
)
/
2
is the carry from the
i
th addition.
Now consider the signed expansion
s
i
=
∈{
0
,
1
}
b
i
−
a
i
∈{−
1
,
0
,
1
}
. In other words,
s
i
=
a
i
−
1
+
c
i
−
1
−
2
c
i
. Clearly,
b
0
=
a
0
and so
s
0
=
0. We show that
s
i
s
i
+
1
=
0for1
≤
i
≤
l
+
1. Suppose
i
is such that
s
i
=
0. Since
a
i
−
1
+
c
i
−
1
∈{
0
,
1
,
2
}
and
a
i
−
1
+
c
i
−
1
≡
s
i
(mod 2)
it follows that
a
i
−
1
+
c
i
−
1
=
1. This then implies that
c
i
=
(1
+
a
i
)
/
2
=
a
i
. Hence,
c
i
+
1
=
a
i
and
s
i
+
1
=
a
i
+
c
i
−
2
c
i
+
1
=
0.
Example 11.1.5
Taking
a
=
91 again, we have 3
·
91
=
273
=
(100010001)
2
. Computing
(3
a
)
−
a
is
100010001
−
1011011
=
101001010
.
Exercise 11.1.6
Compute NAFs for
a
=
100
,
201
,
302 and 403.
We now state and prove some properties of NAFs.
−
−
−
Exercise 11.1.7
Show that if
a
l
...a
0
is a NAF of
a
then (
a
l
)
...
(
a
0
)isaNAFof
a
.
Lemma 11.1.8
The NAF representation of a
∈ Z
is unique.
Proof
Without loss of generality we may assume
a>
1. Let
a
be the smallest positive
integer such that
a
has two (or more) distinct representations as a NAF, call them
l
i
=
0
a
i
2
i
∈ N
and
l
i
0
a
i
2
i
.If
a
is even then
a
0
=
a
0
=
0 and so we have two distinct NAF represen-
tations of
a/
2, which contradicts the minimality of
a
.If
a
is odd then
a
=
≡±
1(mod4)
a
0
and
a
1
=
a
1
=
and so
a
0
=
0. Hence, we obtain two distinct NAF representations of
(
a
−
a
0
)
/
4
<a
, which again contradicts the minimality of
a
.
Exercise 11.1.9
Let
a
∈ N
. Show that
a
has a length
l
+
1 NAF representation if and
only if 2
l
2
l
−
d
l
≤
a
≤
+
d
l
where
(2
l
−
2)
/
3if
l
is odd
d
l
=
(2
l
−
1)
/
3if
l
is even.
