  We propose a simple deterministic test for deciding whether or not an element
$a \in \F_{2^n}^{\times}$ or $\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 interest, this
represents an O(n) speedup over the previous fastest test. By repeatedly
invoking the test on random elements of $\F_{2^n}^{\times}$ we obtain the most
efficient probabilistic method to date to find non-trivial Kloosterman sum
zeros. The analysis depends on the distribution of Sylow $p$-subgroups in the
two families of associated elliptic curves, which we ascertain using a theorem
due to Howe.
