Quadratic residues in finite field For an integer $a$ and a finite field $F_{q}$ of odd order, what is the efficient algorithm   to determine $a$ is Quadratic residue or not? 
 A: The nonzero $a\in \Bbb F_q$ ($q$ odd) is a square iff $a^{(q-1)/2}=1$.
A: Let $q=p^n$, $p$ odd, $n\geq 1$.
As already stated,
$a\in\mathbb{F}_q^\times$ is a square
if and only if $a^{(q-1)/2}=1$.
Remember the Frobenius automorphism and the definition of the norm $N(a)$
for field extensions? This leads to
$$\begin{align}
    \frac{q-1}{2} &= \frac{p-1}{2}(1+p+p^2+\cdots+p^{n-1})
\\\therefore\quad
    a^{(q-1)/2} &= \Bigl(\underbrace{
    a^1 a^p a^{p^2} \cdots a^{p^{n-1}}
    }_{N(a)\in\mathbb{F}_p}\Bigr)^{(p-1)/2}
\end{align}$$
Accordingly, $a$ is a square if and only if $N(a)$ is
a square in the base field $\mathbb{F}_p$,
therefore if and only if
$$\left(\frac{N(a)}{p}\right)_2=+1$$
and there are efficient Jacobi symbol algorithms for that,
e.g. the binary algorithm by Shallit and Sorenson (1993).
It remains to compute $N(a)$.


*

*If $a$ itself is in the base field $\mathbb{F}_p$ (maybe that is what you meant when you spoke of integer $a$), then $N(a) = a^n$ and
$$\left(\frac{N(a)}{p}\right)_2 =
\left(\frac{a^n}{p}\right)_2 =
\left(\frac{a}{p}\right)_2^n =
\left(\frac{a}{p}\right)_2^{n\bmod{2}}$$
Consequently:


*

*If $n$ is even, then every $a\in\mathbb{F}_p^\times$
is a square of some element in $\mathbb{F}_q^\times$.

*If $n$ is odd, then $a\in\mathbb{F}_p^\times$ is a square
in $\mathbb{F}_q^\times$ if and only if it is a square in
$\mathbb{F}_p^\times$, that is, if and only if
$\bigl(\frac{a}{p}\bigr)_2=+1$.


*If $a$ is not restricted to the base field, then computing $N(a)$
is probably easiest with a
normal basis
which takes the form
$$\left(\beta, \beta^p, \beta^{p^2}, \ldots, \beta^{p^{n-1}}\right)$$
with a suitable $\beta\in\mathbb{F}_q^\times$.
The nice thing about such a basis is that taking $p$-th powers amounts
to nothing more than a cyclic shift of the coefficient vector.
Thus, obtaining the Frobenius conjugates of $a$ is very cheap, and
you just need to multiply those $n$ conjugates together to obtain
$N(a)$.
With other bases, you can still resort to a square-and-multiply scheme,
as suggested by Robert Israel.
But then computing $N(a)$ has roughly the same computational cost
as computing $a^{(q-1)/2}$: Both take $\operatorname{O}(\log q)$
field multiplications. There is probably no point in going via $N(a)$ then.
A: It depends on how you have your finite field elements represented.  Finite fields have cyclic multiplicative groups, which means you have a generator $\alpha$ and then every (nonzero) element can be represented as a power of $\alpha$.  Often there is a built-in table of the elements represented as these powers, if the exponent is even then the element is a quadratic residue.
