Cryptography Reference
In-Depth Information
the sum of the (weighted) class numbers of the orders containing the order of discriminant
t
2
−
4
q
(see the references mentioned or Section 5.3.2 of Cohen [
127
]).
These results imply that the numbe
r of elli
ptic curves over
F
q
with
q
+
1
−
t
points is
D
)
<
√
D
log(
D
) for fun-
damental discriminants is Exercise 5.27 of Cohen [
127
]; the case of general discriminants
was discussed by Lenstra [
339
] and the best result is due to McKee [
372
].
4
q
O
(
u
log(
u
) log(log(
u
))), where
u
=
−
t
2
. The bound
h
(
−
Example 9.10.20
Let
p
≡
1(mod4) be prime and let
a
4
∈ Z
be such that
p
a
4
.Let
E
:
y
2
x
3
=
+
a
4
x
be an elliptic curve over
Q
and denote by
E
the elliptic curve over
F
p
obtained as the reduction of
E
modulo
p
. We will determine #
E
(
F
p
).
∈ F
p
2
satisfies
i
2
The curve
E
has the endomorphism
ψ
(
x,y
)
=
(
−
x,iy
) (where
i
=
[
ψ
]
=
Z
1) satisfying
ψ
2
−
=
[
−
1] and so End
(
E
) contains
Z
[
i
]. Since
Z
[
i
]isamaximal
Q
order it follows that End
(
E
)
= Z
[
i
].
Q
a
2
b
2
(see
Theorem 1.2 of Cox [
145
]). Note that there are eight choices for the pair (
a,b
)in
p
Note that every prime
p
≡
1 (mod 4) can be written as
p
=
+
for
a,b
∈ Z
=
a
2
b
2
, namely (
+
±
a,
±
b
)
,
(
±
b,
±
a
) with all choices of sign independent (note that
a
=
b
since
p
is odd).
In
where
i
2
other
words,
p
=
(
a
+
b
i
)
(
a
−
bi
)
=−
1.
By
T
he
orem
9.10.18
the
reduction modulo
p
of
E
has #
E
(
F
p
)
=
p
+
1
−
(
π
+
π
) where
ππ
=
p
. Hence,
π
=
a
+
bi
for one of the pairs (
a,b
) and #
E
(
F
p
)
=
p
+
1
−
t
where
t
∈{
2
a,
−
2
a,
2
b,
−
2
b
}
.
Section 4.4 of Washington [
560
] gives much more detail about this case.
In practice, one uses the Cornacchia algorithm to compute the integers
a
and
b
such that
a
2
b
2
p
F
p
) for elliptic curves of this form for
very large primes
p
. This idea can be extended to many other curves and is known as the
complex multiplication method
or
CM method
.
=
+
and so it is efficient to compute #
E
(
Exercise 9.10.21
Determine the number of points on
E
:
y
2
x
3
=
+
a
4
x
modulo
p
=
23
2
30
2
1429
=
+
for
a
4
=
1
,
2
,
3
,
4.
Exercise 9.10.22
Let
p
be an odd prime such that
p
≡
1 (mod 3). Then there exist integers
a
2
b
2
(see Chapter 1 of [
145
] and note that
p
x
2
3
y
2
implies
a,b
such that
p
=
+
ab
+
=
+
y
)
2
(2
y
)
2
). Show that the number of points on
y
2
x
3
p
=
(
x
−
+
(
x
−
y
)(2
y
)
+
=
+
a
6
over
F
p
is
p
+
1
−
t
where
t
∈{±
(2
a
+
b
)
,
±
(2
b
+
a
)
,
±
(
b
−
a
)
}
.
Example 9.10.23
The six values
a
6
=
1
,
2
,
3
,
4
,
5
,
6 all give distinct values for #
E
(
F
7
)for
the curve
E
:
y
2
x
3
=
+
a
6
, namely 12
,
9
,
13
,
3
,
7
,
4 respectively.
