Cryptography Reference
In-Depth Information
To see this directly using the equation
π
2
+
π
+
2
=
0 write
(
π
2
π
3
.
−
+
+
+
+
−
=
−
1
π
π
2)(1
π
)
1
Exercise 11.3.9
Verify that Algorithm
8
does output a
π
-NAF.
Exercise 11.3.10
Let
π
2
−
π
+
2
=
0. Use Algorithm
8
to convert 107
+
126
π
into non-
adjacent form.
Exercise 11.3.11
Show, using the same methods as Lemma
11.1.14
, that the average
density of a
π
-NAF tends to 1
/
3 when
q
=
2.
Reducing the length of Frobenius expansions
As we have seen, N(
n
n
2
, while the norm only decreases by a factor of roughly 2
each time we divide by
π
. Hence, the Frobenius expansions output by Algorithm
8
on input
n
have length roughly 2 log
2
(
n
). Since the density is 1
/
3 it follows that the weight of the
Frobenius expansions is roughly
+
0
π
)
=
2
3
log
2
(
n
). Exponentiation using Frobenius expansions is
therefore faster than using the square-and-multiply algorithm, even with sliding windows
(since the latter method always needs log
2
(
n
) doublings and also some additions). However,
it is a pity that the expansions are so long. It is natural to seek shorter expansions that still
have the same density. The crucial observation, due to Meier and Staffelbach [
373
], is that
Algor
it
hm
8
outputs a Frobenius expansion
i
[
a
i
]
π
i
that acts the same as [
n
] on all points
in
E
(
F
q
), whereas, for a given application, one only needs a Frobenius expansion that acts
the same as [
n
] on the specific subgroup
P
of prime order
r
.
Definition 11.3.12
Let
E
be an elliptic curve over
F
p
m
), and let
π
be the
p
-
power Frobenius map on
E
. We say that two Frobenius expansions
a
(
π
)
,b
(
π
)
F
p
,
P
∈
E
(
∈ Z
[
π
]are
equivalent
with respect to
P
if
a
(
π
)(
P
)
=
b
(
π
)(
P
)
.
Exercise 11.3.13
Let the notation be as in Definition
11.3.12
. Show that if
a
(
π
)
≡
b
(
π
)(mod
π
m
−
1) then
a
(
π
) and
b
(
π
) are equivalent with respect to
P
.
and
a
(
π
) and
b
(
π
) are equivalent with respect to
P
then
a
(
π
) and
b
(
π
) are equivalent with respect to
Q
.
Show that if
Q
∈
P
A simple idea is to replace all powers
π
i
by
π
i
(mod
m
)
. This will reduce the length of a
Frobenius expansion, but it does not significantly change the weight (and hence the cost of
exponentiation does not change).
The goal is therefore to find an element
n
0
+
n
1
π
of “small” norm that is equivalent
to [
n
] with respect to
P
. Then one applies Algorithm
8
to the pair (
n
0
,n
1
), not to (
n,
0).
There are two simple ways to find an element of small norm, both of which apply the Babai
rounding method (see Section
18.2
) in a suitable lattice. They differ in how one expresses
the fact that (
n
0
+
n
1
π
)
P
=
[
n
]
P
for the point
P
of interest.
