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 $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$.

  1. Choose $g \in \mathbb{F}^*_q$ at random until $g$ is not a square

  2. let $q-1=2^s t$, $t$ odd

  3. $e \leftarrow 0$

  4. for $i \leftarrow 2$ to $s$ do

    1. if $(a g^{-e})^{(q-1)/2^i} \neq 1$ then $e \leftarrow 2^{i-1}+e$

  5. $h \leftarrow a g^{-e}$

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

  7. return $b$

A nonquadratic residue in $\mathbb{F}_q$ can be found by picking random elements and computing the Legendre symbol.

In general, if $q$ is any prime power, one can 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^{(q-1)/2} \ne 1$. The actual square roots can be found by using a factoring algorithm such as the Cantor-Zassenhaus algorithm, though more efficient methods exist.