Cryptography Reference
In-Depth Information
Proof
If
π
(
n
0
+
n
1
π
) then
n
0
is odd and so
n
0
±
1 is even. One can choose the sign such
that 2
n
1
≡−
(
n
0
±
1) (mod 4), in which case the result follows.
The right-to-left algorithm
5
to generate a
π
-NAF is then immediate (see Algorithm
8
;
=−
this algorithm computes
u
in the notation of Lemma 11.3.7). To show that the
algorithm terminates we introduce the norm map: for any
a,b
∈ R
+
=
define N(
a
bπ
)
(
a
+
bπ
)(
a
+
b π
)
=
a
2
+
tab
+
qb
2
where
π, π
∈ C
are the roots of the polynomial
x
2
−
tx
+
q
=
0. This map agrees with the norm map with respect to the quadratic field extension
Q
(
π
)
/
Q
and so is multiplicative. Note also that N(
a
+
bπ
)
≥
0 and equals zero only when
a
=
b
=
0. Meier and Staffelbach [
373
] note that if
n
0
+
n
1
π
is divisible by
π
then
1
N((
n
0
+
n
1
π
)
/π
)
=
2
N(
n
0
+
n
1
π
). This suggests that the length of the
π
-NAF will grow
like log
2
(N(
n
0
+
n
1
π
)
/π
) needs more care. Lemma 3 of
Meier and Staffelbach [
373
] states that if N(
n
0
+
n
1
π
)). The case N((
n
0
±
1
+
n
1
π
)
<
2
n
then there is a corresponding
Frobenius expansion
6
of length at most
n
. Theorem 2 of Solinas gives a formula for the
norm in terms of the length
k
=
l
+
1 of the corresponding
π
-NAF, from which he deduces
(equation (53) of [
517
])
log
2
(N(
n
0
+
n
1
π
))
−
0
.
55
<k<
log
2
(N(
n
0
+
n
1
π
))
+
3
.
52
when
k
≥
30.
Algorithm 8
Convert
n
0
+
n
1
π
to non-adjacent form
INPUT:
n
0
,n
1
∈ Z
OUTPUT:
a
0
,...,a
l
∈{−
1
,
0
,
1
}
1:
while
n
0
=
0 and
n
1
=
0
do
if
n
0
odd
then
2:
u
=
2
−
(
n
0
+
2
n
1
(mod 4))
3:
n
0
=
n
0
−
u
4:
else
5:
=
u
0
6:
end if
7:
Output
u
8:
(
n
0
,n
1
)
=
(
n
1
+
tn
0
/
2
,
−
n
0
/
2)
9:
10:
end while
Example 11.3.8
Suppose
π
2
+
π
+
2
=
0. To convert
−
1
+
π
to a
π
-NAF one writes
n
0
=−
1 and
n
1
=
1. Let
u
=
2
−
(
n
0
+
2
n
1
(mod 4))
=
2
−
(1)
=
1. Output 1 and set
n
0
=
n
0
−
1 to get
−
2
+
π
. Dividing by
π
yields 2
+
π
. One can divide by
π
again (output
π
3
.
0 first) to get
−
π
, output 0 and divide by
π
again to get
−
1. The
π
-NAF is therefore 1
−
5
Solinas states that this algorithm was joint work with R. Reiter.
6
Meier and Staffelbach do not consider Frobenius expansions in non-adjacent form.
