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 \(q-1=2^s t\), \(t\) odd
-
\(e \leftarrow 0\)
-
for \(i \leftarrow 2\) to \(s\) do
-
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 \(\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^{(q-1)/2} \ne 1\). The actual square roots can be found by using a factoring algorithm such as the Cantor-Zassenhaus algorithm.
More efficient methods exist:
-
Gora Adj and Francisco Rodriguez-Henriquez, Square root computation over even extension fields.
-
Daniel J. Bernstein, Faster square roots in annoying finite fields.