Cryptography Reference
In-Depth Information
an elliptic curve addition). However, the idea is to represent an integer by a polynomial in
π
. For example, one can verify that
T
5
T
3
9(mod
T
2
−
+
+
1
≡
+
T
+
2)
π
5
(
P
)
and so one can compute [9]
P
(normally taking 3 doublings and an addition) as
−
+
π
3
(
P
)
+
P
using only two elliptic curve additions.
This idea can be extended to any algebraic group
G
(in particular, elliptic curves, divisor
class groups of hyperelliptic curves and algebraic tori) that is defined over a field
F
q
but
for which one works in the group
G
(
F
q
m
).
=
l
i
=
0
a
i
π
i
(
P
)isa
Exercise 11.3.4
Give an algorithm to compute [
a
]
P
when
a
Frobenius expansion. What is the cost of the algorithm?
=
l
i
=
0
a
i
π
i
Definition 11.3.5
Let
S
⊆ Z
such that 0
∈
S
and if
a
∈
S
then
−
a
∈
S
.Let
a
be a Frobenius expansion with
a
i
∈
S
. Then
a
is in
non-adjacent form
if
a
i
a
i
+
1
=
0for
all 0
≤
i<l
. Such an expansion is also called a
π
-NAF
.
An important task is to convert an integer
n
into a Frobenius expansion in non-adjacent
form. In fact, to get short expansions we will need to convert a general element
n
0
+
n
1
π
to a
π
-NAF, so we study the more general problem. The crucial result is the following.
Lemma 11.3.6
Let π satisfy π
2
−
+
=
0
. An element n
0
+
Z
tπ
q
n
1
π in
[
π
]
is divisible
by π if and only if q
|
n
0
. In this case
(
n
0
+
n
1
π
)
/π
=
(
n
1
+
tn
0
/q
)
+
π
(
−
n
0
/q
)
.
(11.1)
Similarly, it is divisible by π
2
tn
0
(mod
q
2
)
.
if and only if q
|
n
0
and qn
1
≡−
Proof
Note that
π
2
=
tπ
−
q
. Since
π
(
m
0
+
m
1
π
)
=−
qm
1
+
π
(
m
0
+
tm
1
)
it follows that
n
0
+
n
1
π
=
π
(
m
0
+
m
1
π
) if and only if
n
0
=−
qm
1
,
and
n
1
=
m
0
+
tm
1
.
Writing
m
1
=−
tm
1
yields equation (
11.1
).
Repeating the argument, one can divide the element in equation (
11.1
)by
π
if and only
if
q
n
0
/q
and
m
0
=
n
1
−
|
(
n
1
+
tn
0
/q
). The result follows.
The idea of the algorithm for computing a
π
-NAF, given
n
0
+
n
1
π
, is to add a suitable
integer so that the result is divisible by
π
2
,divideby
π
2
and then repeat. This approach is
only really practical when
q
=
2, so we restrict to this case.
Lemma 11.3.7
Let π
2
−
tπ
+
2
=
0
where t
=±
1
. Then n
0
+
n
1
π is either divisible by
π or else there is some
=±
1
such that
0(mod
π
2
)
.
(
n
0
+
)
+
n
1
π
≡
Indeed,
=
(
n
0
+
2
n
1
(mod 4))
−
2
if one defines n
0
+
2
n
1
(mod 4)
∈{
1
,
3
}
.