International Association
for Cryptologic Research

This paper presents a comprehensive study of the computation of square roots over finite extension fields.

We propose two novel algorithms for computing square roots over even field extensions

of the form $\\F_{q^{2}}$, with $q=p^n,$ $p$ an odd prime and $n\\geq 1$. Both algorithms have an associate

computational cost roughly equivalent to one exponentiation in $\\F_{q^{2}}$.

The first algorithm is devoted to the case when $q\\equiv 1 \\bmod 4$, whereas the second one handles the case when

$q\\equiv 3 \\bmod 4$. Numerical comparisons show that the two algorithms presented in this paper are competitive

and in some cases more efficient than the square root methods previously known.