Paper 2012/685

Square root computation over even extension fields

Gora Adj and Francisco Rodríguez-Henríquez

Abstract

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 ${\text{F}}_{q^2}$, with $q=p^n,$ $p$ an odd prime and $n\ge 1$. Both algorithms have an associate computational cost roughly equivalent to one exponentiation in ${\text{F}}_{q^2}$. The first algorithm is devoted to the case when $q\equiv 1mod4$, whereas the second one handles the case when $q\equiv 3mod4$. 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.