Cryptography Reference
In-Depth Information
±
√
(
A
P
2)
/B
) (which has order 4). Show that the map from Edwards model to
Montgomery model is undefined only for points
P
=
(
−
1
,
−
=
(0
,
±
1) and points at infinity.
Exercise 9.12.23
Show that a non-trivial quadratic twist of the twisted Edwards model
ax
2
y
2
dx
2
y
2
is
aux
2
y
2
dux
2
y
2
∈ k
∗
is a non-square.
+
=
1
+
over
k
+
=
1
+
where
u
Exercise 9.12.24
Show that if an elliptic curve
E
can be written in twisted Edwards model
then the only non-trivial twist of
E
that can also be written in twisted Edwards model is
the quadratic twist.
Example 9.12.25
The curve
x
2
y
2
x
2
y
2
+
=
1
−
ha
s a
n automorphism
ρ
(
x,y
)
=
(
ix,
1
/y
) (which fixes the identity point (0
,
1)) for
i
=
√
−
1. One has
ρ
2
=−
1. Hence, this curve corresponds to a twist of the Weierstrass curve
y
2
x
3
=
+
x
having
j
-invariant 1728.
Example 9.12.26
Elliptic curves with
C
M by
D
=−
3 (equi
va
lently,
j
-
in
variant 0) can
only be written in Edwards model if
√
3
(
√
3
2)
/
(
√
3
∈ F
q
. Taking
d
=
+
−
2) gives the
Edwards curve
E
:
x
2
y
2
dx
2
y
2
,
+
=
1
+
which has
j
-invariant 0. We construct the automorphism corresponding to
ζ
3
in stages. First
we give the isomorphism
φ
:
E
→
M
where
M
:
BY
2
=
X
3
+
AX
2
+
X
is the curve in
=
+
−
=
−
=
Montgomery model with
A
2(1
d
)
/
(1
d
) and
B
4
/
(1
d
). This map is
φ
(
x,y
)
((1
+
y
)
/
(1
−
y
)
,
(1
+
y
)
/
(
x
(1
−
y
))) as in Lemma
9.12.20
. The action of
ζ
3
on
M
is given
by
ζ
3
)
/
√
3
,Y
)
.
ζ
(
X,Y
)
=
(
ζ
3
X
+
(1
−
Then we apply
φ
−
1
(
X,Y
)
=
(
X/Y,
(
X
−
1)
/
(
X
+
1)).
9.13 Statistical properties of elliptic curves over finite fields
There are a number of questions, relevant for cryptography, about the set of all elliptic
curves over
F
q
.
The theory of complex multiplication states that if
<
2
√
q
and gcd(
t,q
)
|
|
=
t
1 then the
F
q
with #
E
(
F
q
)
=
+
−
number of isomorphism classes of elliptic curves
E
over
q
1
t
is given by the Hurwitz class number
H
(
t
2
4
q
). Theorem
9.11.11
gave a simi-
lar result for the supersingular case. As noted in Section 9.10.1, this means that the
number of
−
F
q
-isomorphism classes of e
lliptic c
urves over
F
q
with
q
+
1
−
t
points is
=
4
q
O
(
D
log(
D
) log(log(
D
))), where
D
−
t
2
. We now give Lenstra's bounds on the
number of
F
q
-isomorphism classes of elliptic curves with group orders in a subset of the
Hasse interval.
Since the number of elliptic curves in short Weierstrass form (assuming now that 2
q
)
that are
F
q
-isomorphic to a given curve
E
is (
q
−
1)
/
#Aut(
E
), it is traditional to count the
