Efficient computation of Jacobsthal matrix / quadratic character in GF(q) Is there an efficient algorithm to compute the quadratic character $\chi$ on GF($q$) in order to get the Jacobsthal matrix
$$
  J_{i,j} = \chi(i-j) = \begin{cases} ~0 & \rm if & i = j\\ ~1 &\rm if& i-j ~~\text{ is a square in GF}(q)\\ -1&\rlap{\rm otherwise}\end{cases}
$$
where $i,j$ run over the elements of GF($q$)? (Unfortunately, when $q=p^n$ with $n>1$, one cannot simply take $i,j\in\mathbb Z$ and check for quadratic residues modulo $q$. In particular, the $J$ matrix isn't even circular in that case.)
So, I'd like to know whether there's a way to determine whether some $x\in{\rm GF}(q)$ is a square without the need for implementing (full) arithmetic in GF($q$). (If I can compute arbitrary products in GF($q$), I can obviously simply compute the set $S=\{x\cdot x~;~ x\in {\rm GF}(q)\}$ of all squares, and check whether the element $i-j$ is in $S$. But implementing general multiplication in GF($q$) is nontrivial. (To start with, I have to find an irreducible polynomial $P\in{\rm GF}(p)_n[X]$ of degree $n$ over GF($p$)...) Is it possible to compute the list of squares in a simpler way?
 A: Normally one shouldn't use $i,j$ since they indicate integers while the elements of $GF(q)$ aren't integers.
I don't know if there is a faster method than the one below.
In any case, choose random elements from $GF(q)$ and test them until you find a primitive element $\alpha$ which generates $GF(q)^\ast.$ Let $q=p^n.$
Then list the quadratic residues
$$
L=[\alpha^{2j}:j \in \{0,1,\ldots,(p^n-1)/2\}],
$$
and we will have $\chi(x)=+1$ for $x\in L.$ For $x\in GF(q)^\ast \setminus L$ we will have $\chi(x)=-1.$
Now you need a fast addition (really subtraction) algorithm. One way to obtain this is by using the Zech logarithm (look it up) $Z_\alpha(k)$ defined by
$$
\alpha^{Z_\alpha(k)}=1+\alpha^k, \quad k \in \{0,\ldots,p^n-2\}
$$
with $Z_\alpha(0)=-\infty.$
If $p=2,$ then you can implement the subtraction as
$$
x-x'=\alpha^{k}-\alpha^{k'}=\alpha{k}+\alpha^{k'}=
\alpha^k(1+\alpha^{k'-k}=\alpha^{k+Z_{\alpha}(k-k'))
$$
and table lookup in $L$ to compute $\chi(x-x').$
For odd characteristic you can define the Zech via $1-\alpha^k$ if you wish, it is a bit simpler.
