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

Ben Lynn blynn@cs.stanford.edu 💡