Information Technology Reference
In-Depth Information
1.1
Kloosterman Sums
For a prime
p
and a positive integer
m
,let
q
=
p
m
and let
F
q
denote the finite
field of order
q
.LetTr:
F
q
→
F
p
be the absolute trace. The
Kloosterman sum
F
q
is the mapping
K
F
q
→
R
on
:
defined by
K
(
a
):=1+
x∈
F
q
ω
Tr(
x
−
1
+
ax
)
,
(1)
where
ω
=
e
2
πi/p
is a primitive
p
-th root of unity. (In some references the
same mapping is defined by
(
a
):=
x∈
F
q
ω
Tr(
x
−
1
+
ax
)
K
with the proviso that
Tr(0
−
1
)=0.)
Since
ω
+
ω
−
1
=
−
1for
p
= 3, it is easy to see that
K
(
a
) is an integer for
p
∈{
2
,
3
}
. For integers
s, t
let
s
|
t
denote that
s
divides
t
,andlet
s
t
denote
that
s
does not divide
t
.
Applying the Frobenius automorphism
x
x
p
to (1) and using the properties
→
of the trace map yields:
(
a
p
)
.
Lemma 1.
For al l a
∈
F
p
m
we have
K
(
a
)=
K
1.2
Elliptic Curves
Throughout the paper we will use standard definitions and results on elliptic
curves over finite fields and on the Abelian groups associated with them. We
recommend [12] as an accessible reference for these topics. Throughout this paper
for an elliptic curve
E
defined over
F
p
m
-
rational points on
E
. Recall that the
order
of a point
P
on an elliptic curve is
the smallest
r
such that
rP
=
F
p
m
we denote by #
E
the number of
O
and
sP
=
O
for 0
<s<r
,where
O
is the
neutral element of the group of the curve (the point at infinity).
∈
F
2
m
and let
Theorem 1.
[10]
Let a
E
2
(
a
)
be the elliptic curve over
F
2
m
defined by
y
2
+
xy
=
x
3
+
a.
E
2
(
a
):
E
2
(
a
)=2
m
+
Then
#
K
(
a
)
.
∈
F
3
m
and let
Theorem 2.
[13]
Let a
E
3
(
a
)
be the elliptic curve over
F
3
m
defined by
y
2
=
x
3
+
x
2
E
3
(
a
):
−
a.
E
3
(
a
)=3
m
+
Then
#
K
(
a
)
.
Let us now present our first result, which we be used in the next section.
∈
F
p
m
,andlet
0
m.Thenp
k
Theorem 3.
Let p
(
a
)
if
and only if there exists a point of order p
k
on E
p
(
a
)
, where the curves E
2
(
a
)
and
E
3
(
a
)
are defined in Theorems 1 and 2 above.
∈{
2
,
3
}
,leta
≤
k
≤
|K