Algorithms for Kloosterman Zeros

Kloosterman sums are exponential sums on finite fields with important applications in Cryptography and Coding Theory. Of particular importance are those field elements at which the Kloosterman sum attains the value 0, which are called Kloosterman zeros. They exist only in fields of characteristic 2 and 3. We prove an upper bound on the density of the classical modular polynomial when it is considered as a polynomial over GF(2). We develop an algorithm to list exhaustively Kloosterman zeros in a given field of characteristic 2. Using this algorithm we list all Kloosterman zeros in fields of order $2^m$ for $m\le 63$, whereas this has been done only for $m\le 14$ in the literature. We develop an algorithm to discover relations satisfied by coefficients of minimal polynomials of Kloosterman zeros in characteristic 2. We rediscover five such relations that have been proved in the literature and we conjecture two new relations.