Information Technology Reference
In-Depth Information
E
2
(
a
16
):
y
2
+
xy
=
x
3
+
a
16
. By Lemma 7.4 in [12], an
x
0
∈
F
2
m
is the
x
-
E
2
(
a
16
) if and only if
X
=
x
0
is a root of the
polynomial ((
a
4
+
X
)
2
+
a
2
X
)
2
+
aX
(
a
4
+
X
)
2
. This simplifies to the equation
coordinate of a point of order 16 on
X
4
+
aX
3
+
a
4
X
2
+
a
9
X
+
a
16
=0
.
(2)
Using the known theory of solvability of quartic polynomials in characteristic
2, see for example [10], some straightforward calculations show that (2) has a
solution in
F
2
m
if and only if Tr(
a
)=0andTr(
y
0
)=0where
y
0
is any of the
solutions of the quadratic equation
y
2
+
ay
+
a
3
=0.
Let us just remark that in the ternary case, one can prove using very similar
ideas that for any
a
(
a
) is divisible by 9 if and only if Tr(
a
)=0.The
necessary background on division polynomials in characteristic 3 can be found
for example in the topic [5].
One proof technique that has been used several times in the literature is to
associate the value of the Kloosterman sum with the number of solutions to a
certain system of equations; then a combinatorial argument (typically exploiting
some symmetry present in the system of equations) is used to show that the
number of solutions has to be divisible by some constant. This then yields a
divisibility result for the associated Kloosterman sum and/or some other kind of
exponential sum. For illustration let us quote our recent result obtained in this
way, which appears in a different article.
∈
F
3
m
,
K
Theorem 6.
[6]
Let a
∈
F
3
m
. Then exactly one of the following cases occurs:
1. a
=0
or a is a square,
Tr(
√
a
)
=0
and
K
(
a
)
≡
0(mod2
.
2. a
=
t
2
−
t
3
for some t
∈
F
3
m
\{
0
,
1
}
,atleastoneoft and
1
−
t is a square
and K
(
a
)
≡
2
m −
1(mod4
.
3. a
=
t
2
t
3
for some t
−
∈
F
3
m
\{
0
,
1
}
,botht and
1
−
t are non-squares and
K
(
a
)
≡
2
m
+1 (mod 4)
.
3
Computation of Zeros of Kloosterman Sums
As we have already mentioned, there is a significant interest in finding
a ∈
F
p
m
for which
K
(
a
) = 0. In the binary case, the existence of such
a ∈
F
2
m
for
each
m>
1 was the famous Dillon conjecture (related to the construction of
bent functions) that was settled armatively by Lachaud and Wolfmann in [9].
More recently, Charpin and Gong [3] related the zeros of Kloosterman sums
with hyperbent functions. Numerical examples found in the literature appear
to be limited to relatively small field orders. Table 1 in [3] gives a complete
classification of Kloosterman zeros in
14.
It is sometimes overlooked that the existence of very fast algorithms for count-
ing points on elliptic curves [11], such as variants of the Schoof-Elkies-Atkin al-
gorithm, allows one to compute binary and ternary Kloosterman sums on fields
of very large orders by Theorems 1 and 2. For example, using the point counting
procedure implemented in the computer algebra system Magma 2.14 running
F
2
m
for
m
≤
