Tonelli’s Algorithm
In a cyclic group of odd order \(t\), it is easy to compute square roots: simply exponentiate by \((t+1)/2\). In general, for an odd prime power \(q\), \(\mathbb{F}_q^*\) is isomorphic to \(\mathbb{Z}_{2^s}^+ \times \mathbb{Z}_t^+\), giving rise to the following procedure to compute \(b = \sqrt{a} \in \mathbb{F}^*_q\).

Choose \(g \in \mathbb{F}^*_q\) at random until \(g\) is not a square

let \(q1=2^s t\), \(t\) odd

\(e \leftarrow 0\)

for \(i \leftarrow 2\) to \(s\) do

if \((a g^{e})^{(q1)/2^i} \neq 1\) then \(e \leftarrow 2^{i1}+e\)


\(h \leftarrow a g^{e}\)

\(b \leftarrow g^{e/2}h^{(t+1)/2}\)

return \(b\)
A nonquadratic residue in \(\mathbb{F}_q\) can be found by picking random elements and computing the Legendre symbol.
We could also determine if an element \(a\) has a square root by seeing if \(x^2  a\) divides \(x^q  x\), which is equivalent to checking that \(a^{(q1)/2} \ne 1\). The actual square roots can be found by using a factoring algorithm such as the CantorZassenhaus algorithm.
More efficient methods exist:

Gora Adj and Francisco RodriguezHenriquez, Square root computation over even extension fields.

Daniel J. Bernstein, Faster square roots in annoying finite fields.