Programming ECC - Tonelli's Algorithm

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$ , $𝔽_{q}^{*}$ is isomorphic to $ℤ_{2^{s}}^{+} \times ℤ_{t}^{+}$ , giving rise to the following procedure.

Tonelli(+++ $a$ +++) [computes +++ $b = \sqrt{a} \in 𝔽_{q}^{*}$ +++]

Choose $g \in 𝔽_{q}^{*}$ at random until $g$ is not a square
let $q - 1 = 2^{s} t$ , $t$ odd
$e \leftarrow 0$
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$
$h \leftarrow a g^{- e}$
$b \leftarrow g^{e / 2} h^{(t + 1) / 2}$
return $b$

A nonquadratic residue in $𝔽_{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} \neq 1$ . The actual square roots can be found by using a factoring algorithm such as the Cantor-Zassenhaus algorithm, though more efficient methods exist.