Computing the Number of Finite Field Elements with Prescribed Trace and Co-trace

In this paper, we address the problem for enumerating the number of finite field elements with prescribed trace and co-trace in case of arbitrary characteristic $p$. We show that this problem can be reduced to solving a system of $p-1$ linear equations with matrix of coefficients a slight modification of circulant matrix formed by the Kloosterman sums over the field ${\text{MF}}_p$. The presented approach is illustrated in the cases of characteristic $p=2,3$ and $5$.