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
Search WWH ::




Custom Search