Information Technology Reference
In-Depth Information
Proof.
By Theorems 1 and 2 we have that
p
k
(
a
) if and only if
p
k
|K
|
#
E
p
(
a
). Recall
∈
F
p
m
the Abelian group structure of
that for any
a
E
p
(
a
)is
E
p
(
a
)
Z
n
1
×
Z
n
2
,
p
m
E
p
(
a
)=
n
1
n
2
. Suppose that
p
k
with
n
1
|
n
2
and
n
1
|
−
1, and we have #
|
#
E
p
(
a
).
n
1
, it follows that
p
k
Since
p
|
n
2
and
E
p
(
a
) contains a subgroup
G
isomorphic
Z
p
k
.Ageneratorof
G
is a point of order
p
k
to
in
E
p
(
a
). Conversely, if
E
p
(
a
)
contains a point of order
p
k
,then
p
k
|
#
E
p
(
a
) by the Lagrange Theorem.
2
Divisibility of Kloosterman Sums
We say that
a
∈
F
p
m
is a
zero of the Kloosterman sum,
or a
Kloosterman zero
for short, if
(0) = 0, and we will often implicitly
exclude the case
a
=0anddealonlywith
a
K
(
a
) = 0. It is easy to see that
K
∈
F
p
m
. There is a lot of interest
in finding zeros of Kloosterman sums, see for example [3] for an application to
construction of bent functions.
If we can find an integer
s
such that
s
=0.Thisgives
one of motivations for studying divisibility properties of Kloosterman sums. The
following two results are well known and easy to prove.
K
(
a
), then
K
(
a
)
Lemma 2.
For each a
∈
F
2
m
,
K
(
a
)
is divisible by 4.
Lemma 3.
For each a
∈
F
3
m
,
K
(
a
)
is divisible by 3.
The following theorem was first proved in [7]. There are two proofs given in
[7], and one proof is given in [4]. We give a new proof as an illustration of the
methods applied in this article.
Theorem 4.
[7,4]
Let m
≥
3
. For any a
∈
F
2
m
,
K
(
a
)
is divisible by 8 if and
only if
Tr(
a
)=0
.
∈
F
2
m
.Since
m
Proof.
The result holds for
a
= 0, so let us suppose that
a
≥
3,
by Theorem 3 we have that 8
|K
(
a
) if and only if
E
2
(
a
) contains a point of order
E
2
(
a
2
l
) for any positive integer
l
;let
8. By Lemma 1 we can replace
E
2
(
a
)with
E
2
(
a
8
):
y
2
+
xy
=
x
3
+
a
8
. By Lemma 7.4 in
[12], an
x
0
∈
F
2
m
is the
x
-coordinate of a point of order 8 on
us for simplicity take the curve
E
2
(
a
8
)ifandonly
if
X
=
x
0
is a root of the polynomial (
X
+
a
2
)
2
+
aX
. This happens exactly if
Tr(1
a
4
/a
2
)=Tr(
a
)=0.
·
Lemma 7.4 of [12] used in the previous proof belongs to the theory of
division
polynomials
for elliptic curves. A detailed treatment for characteristic 2 can be
found in Chapter 7 of [12]. The following theorem is new.
Theorem 5.
Let m
(
a
)
is divisible by 16 if and only if
Tr(
a
)=0
and
Tr(
y
)=0
where y
2
+
ay
+
a
3
=0
.
≥
4
. For any a
∈
F
2
m
,
K
∈
F
2
m
.Since
m
Proof.
The result holds for
a
= 0, so let us suppose that
a
≥
4,
by Theorem 3 we have that 16
E
2
(
a
) contains a point of
order 16. As in the previous proof, by Lemma 1 we can replace
|K
(
a
) if and only if
E
2
(
a
)with