We propose a simple deterministic test for deciding whether or not an element $ a\in\mathbb
{F} _ {2^ n}^{\times} $ or $\mathbb {F} _ {3^ n}^{\times} $ is a zero of the corresponding
Kloosterman sum over these fields, and rigorously analyse its runtime. The test seems to
have been overlooked in the literature. The expected cost of the test for binary fields is a
single point-halving on an associated elliptic curve, while for ternary fields the expected cost
is one-half of a point-thirding on an associated elliptic curve. For binary fields of practical …

Proof: By previous theorems, pk| Kpn (a)⇐⇒ pk|# Epn (a). We also have Epn (a)∼= Zd1×
Zd2 where d1| d2 and d1| pn− 1. Suppose pk|# Epn (a). Since pd 1, we have pk| d2 and by
Sylow's (second) Theorem,∃ G≤ Epn (a) with G∼= Zpk and a generator of G is a point of
order pk in Epn (a). Conversely, if Epn (a) contains a point of order pk, by Lagrange's
Theorem pk|# Epn (a) and hence pk| Kpn (a).