Cryptography Reference
In-Depth Information
Tripling
Doche, Icart and Kohel [169] suggested to speed up the computation of [
m
]
P
on
E
for
small
m
by splitting it as
φ
E
is an isogeny of degree
m
. We refer to
Exercise
9.6.30
for an example of this in the case
m
◦
φ
where
φ
:
E
→
=
3, and to [
169
] for the details in
general.
11.3.2 Frobenius expansions
Koblitz (in Section 5 of [
309
]) presented a very efficient doubling formula for
E
:
y
2
+
=
x
3
F
2
(see Exercise
9.1.3
). Defining
π
(
x,y
)
=
(
x
2
,y
2
) one can write this as
y
over
[2]
P
=−
π
2
(
P
) for all
P
∈
E
(
F
2
m
) for any integer
m
. We assume throughout this section
that finite fields
F
p
m
are represented using a normal basis so that raising to the power
p
is very fast. Menezes and Vanstone [
374
] and Koblitz [
311
,
312
] explored further how to
speed up arithmetic on curves over small fields. However, the curves used in [
309
,
374
,
311
]
are supersingular and so are less commonly used for cryptography.
The Frobenius map can be used to speed up elliptic curve exponentiation on more general
curves. For cryptographic applications we assume that
E
is an elliptic curve over
F
q
such
F
q
m
) has a large prime divisor
r
for some
m>
1.
4
Let
π
be the
q
-power Frobenius
map on
E
. The trick is to replace an integer
a
with a sequence
a
0
,...,a
l
of “small” integers
such that
that #
E
(
l
[
a
i
]
π
i
(
P
)
[
a
]
P
=
i
=
0
for the point
P
∈
E
(
F
q
m
) of interest.
Definition 11.3.2
Let
E
be an elliptic curve over
F
q
and let
π
be the
q
-power Frobenius
⊂ Z
∈
map. Let
S
S
(the set
S
is usually obvious from the context).
A
Frobenius expansion
with
digit set
S
is an endomorphism of the form
be a finite set such that 0
l
[
a
i
]
π
i
i
=
0
where
a
i
∈
S
and
a
l
=
0. The
length
of a Frobenius expansion is
l
+
1. The
weight
of a
Frobenius expansion is the number of non-zero
a
i
.
Many papers write
τ
for the Frobenius map and speak of
τ
-adic expansions, but we will
call them
π
-adic expansions
in this topic.
Let
E
:
y
2
x
3
ax
2
Example 11.3.3
+
xy
=
+
+
1 over
F
2
where
a
∈{
0
,
1
}
. Consider
(
x
2
,y
2
). From Exercise
9.10.10
we know that
the group
E
(
F
2
m
) and write
π
(
x,y
)
=
π
2
1)
a
π
+
(
−
+
2
=
0. Hence, one can replace the computation [2]
P
by
−
π
(
π
(
P
))
−
1)
a
π
(
P
). At first sight, there is no improvement here (we have replaced a doubling with
(
−
4
Note that, for any fixed elliptic curve
E
over
F
q
and any fixed
c
∈ R
>
0
, it is not known if there are infinitely many
m
∈ N
such
that #
E
(
F
q
m
) has a prime factor
r
such that
r>cq
m
. However, in practice one finds a sufficient quantity of suitable examples.
