Information Technology Reference
In-Depth Information
on Intel Xeon CPU at 3.0 GHz, for a random
a
∈
F
2
800
it takes only about 3
seconds to compute
(
a
).
Moreover, if one is only interested in proving that
K
K
(
a
) = 0 for some given
a
∈
F
p
m
(
p
∈{
2
,
3
}
), then one does not need to use the complicated algorithms
for fast point counting. In this case the group of the elliptic curve must be
isomorphic to
Z
p
m
, and one can simply attempt to guess a generator
P
for the
group. As there are (
p
1)
p
m−
1
generators, there is a good chance of success. If
P
indeed happens to be a generator, then this can be easily verified by computing
p
i
P
for
i
=1
,
2
,...,m
via iterated multiplication by
p
. In the binary case this
process can be further simplified using Lemma 7.4 of [12].
Using the algorithm described in the previous paragraph and starting with
random elements
a
−
∈
F
p
m
, we have found one Kloosterman zero for each field
F
2
m
where
m
34. The computation
took only a few days of CPU time. As was noted earlier, these results are easily
verified for example using the system Magma [1].
≤
64 and for each field
F
3
m
where
m
≤
Example 1.
Let
F
2
[
X
]
/
(
p
(
X
)) where
p
(
X
)=1+
X
+
X
3
+
X
4
+
X
64
.For
a
=1+
X
6
+
X
9
+
X
12
+
X
16
+
X
17
+
X
20
+
X
22
+
X
24
+
X
27
+
X
30
+
X
31
+
X
32
+
X
36
+
X
37
+
X
40
+
X
41
+
X
43
+
X
45
+
X
47
+
X
48
+
X
50
+
X
51
+
X
53
+
X
56
+
X
59
+
X
60
F
2
64
be constructed as
∈
F
2
64
we have
K
(
a
)=0.
4
Existence of Zeros in Subfields
Very recently, Charpin and Gong [3] proved that a Kloosterman zero in
F
2
m
can
not
belong to a certain set that is defined in terms of certain
subfields
of
F
2
m
.
For details please see the statement of Theorem 6 in [3]. Their proof is based
on formulas by Carlitz [2] that express the value of a Kloosterman sum over an
extension field in terms of the Kloosterman sums on subfields. For clarity let
us now use the symbol
with a subscript to denote that the Kloosterman sum
K
q
(
a
) is computed over the field
K
F
q
.
It is interesting to observe that some of the Carlitz formulas, which are proved
by complicated calculations in [2], can be obtained very easily using the asso-
ciated elliptic curves given in Theorems 1 and 2 above. Indeed, if
a
∈
F
p
m
,
then the Hasse-Weil Theorem (see, for example, [8, Theorem 2.26]) applied to
the curves of Theorems 1 and 2 immediately yields a second order linear re-
currence for
K
p
ms
(
a
), where
s
is a positive integer, in terms of
K
p
m
(
a
), where
K
q
(
a
):=
K
q
(
a
)
−
1. This is exactly the recurrence (5.7) of [2]. It would be inter-
esting to see whether this approach can yield some further non-existence results
beyond those quoted in the previous paragraph.
References
1. Bosma, W., Cannon, J., Playoust, C.: The Magma Algebra System. I. The User
Language. J. Symbolic Comput. 24, 235-265 (1997)
2. Carlitz, C.: Kloosterman Sums and Finite Field Extensions. Acta Arithmetica XVI,
179-193 (1969)
