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 💡