Cryptography Reference
In-Depth Information
on
E
. Hence, we have shown that
π
p
2
=
[
p
]on
E
. The characteristic polynomial of
π
p
2
is
p
)
2
p
2
therefore (
T
−
and so #
E
(
F
p
2
)
=
−
2
p
+
1.
in End
k
(
E
) the quaternion algebra structure comes from other endo-
morphisms. We already met
ψ
Since
π
p
2
∈ Z
End
F
p
2
(
E
) such that
ψ
2
∈
=−
p
. The endomorphism ring
∈ F
p
2
satisfies
i
2
also contains the map
ξ
(
x,y
)
=
(
−
x,iy
) where
i
=−
1. One can verify
that
ξ
2
ψξ
(since
i
p
=−
1 and
ξψ
=−
=−
i
as
p
≡
3 (mod 4)); as was seen already in
Example
9.9.2
.
We know from Theorem
9.8.1
that the group structure of an elliptic curve over a finite
field
F
q
is of the form
Z
/n
1
Z × Z
/n
2
Z
for some integers
n
1
,n
2
such that
n
1
|
n
2
.Itfollows
from the Weil pairing (see Exercise
26.2.5
or Section 3.8 of [
505
]) that
n
1
|
(
q
−
1).
The following result gives the group structures of elliptic curves.
1
2
√
q and let N
p
m
,lett
Theorem 9.10.13
Let q
=
∈ Z
be such that
|
t
|≤
=
q
−
t
+
1
be
=
l
l
h
l
for
the prime factorisation of N. Then the possible group structures of elliptic curves over
a possible group order for an elliptic curve as in Theorem
9.10.11
. Write N
F
q
with N points are (i.e., only these cases are possible, and every case does arise for every q)
Z
Z
/p
h
p
/l
a
l
/l
h
l
−
a
l
Z
Z ×
Z × Z
l
=
p
where:
1.
if
gcd(
t,p
)
=
1
then
0
≤
a
l
≤
min
{
v
l
(
q
−
1)
,
h
l
/
2
}
where v
l
(
q
−
1)
denotes the inte-
ger b such t
h
at l
b
(
q
−
1)
,
2
√
q then a
l
=
/
(
√
q
)
2
)
,
2.
if t
=±
h
l
/
2
(i.e., the group is
(
Z
±
1)
Z
=±
√
q or t
p
(
m
+
1)
/
2
3.
if t
=±
then the group is cyclic (i.e., all a
l
=
0
),
4.
if t
=
0
then either the group is cyclic (i.e., all a
l
=
0
)oris
Z
/
2
Z × Z
/
((
q
+
1)
/
2)
Z
(i.e., all a
l
=
0
except a
2
=
1
).
Proof
See Voloch [
559
] or Theorem 3 of R uck [
454
] (note that it is necessary to prove that
Ruck's conditions imply those written above by considering possible divisors
d
|
(
q
−
1)
|
−
+
and
d
(
q
t
1) in the supersingular cases).
Exercise 9.10.14
Let
q
be a prime power, gcd(
t,q
)
=
1, and
N
=
q
+
1
−
t
a possible
value for #
E
(
F
q
). Show that there exists an elliptic curve over
F
q
with
N
points and which
is cyclic as a group.
Another useful result, which relates group structures and properties of the endomorphism
ring, is Theorem
9.10.16
.Exercise
9.10.15
shows that the final condition makes sense.
Exercise 9.10.15
Let
E
be an elliptic curve over
F
q
and let
t
=
q
+
1
−
#
E
(
F
q
). Show
that if
n
2
1) then
n
2
(
t
2
|
(
q
+
1
−
t
) and
n
|
(
q
−
|
−
4
q
).
1
This result has been discovered by several authors. Schoof determined the group structures of supersingular elliptic curves in
his thesis. The general statement was given by Tsfasman in 1985, R uck in 1987 and Voloch in 1988.
