Cryptography Reference
In-Depth Information
THEOREM 4.3
Let
q
=
p
n
be a pow er ofa prime
p
and let
N
=
q
+1
a
.Thereisane
ll
iptic
curve
E
defined over
F
q
su ch that
#
E
(
F
q
)=
N
ifand onlyif
|
−
2
√
q
and
a
|≤
a
satisfi es on e of the follow ing:
1.
gcd(
a, p
)=1
2
√
q
2.
n
is even and
a
=
±
±
√
q
3.
n
is even,
p
≡
1(mod3)
,and
a
=
4.
n
is odd,
p
=2
or
3
,and
a
=
±p
(
n
+1)
/
2
5.
n
is even,
p
≡
1(mod4)
,and
a
=0
6.
n
is odd and
a
=0
.
THEOREM 4.4
Let
N
be an integer that occurs as the order ofan elliptic curve over a finite
field
F
q
,asin T heorem 4.3. W rite
N
=
p
e
n
1
n
2
with
p
n
1
n
2
and
n
1
|n
2
(possibly
n
1
=1
). T here isanellipticcurve
E
over
F
q
su ch that
E
(
F
q
)
Z
p
e
⊕
Z
n
1
⊕
Z
n
2
ifand onlyif
1.
n
1
|q −
1
in cases (1), (3), (4), (5), (6) of T heorem 4.3
2.
n
1
=
n
2
in case (2) of T heorem 4.3.
Thesearethe onlygroupsthat occur as groups
E
(
F
q
)
.
4.2 The Frobenius Endomorphism
Let
F
q
be a finite field with algebraic closure
F
q
and let
φ
q
:
F
q
−→
F
q
,
x
→ x
q
be the Frobenius map for
F
q
(see Appendix C for a review of finite fields).
Let
E
be an el
lip
tic curve defined over
F
q
.Then
φ
q
acts on the coordinates
of points in
E
(
F
q
):
φ
q
(
x, y
)=(
x
q
,y
q
)
,
φ
q
(
∞
)=
∞.
Search WWH ::
Custom Search