Square Root Computation over Even Extension Fields
Gora Adj, Francisco Rodríguez‐Henríquez · IEEE Transactions on Computers · 2013
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${\BBF_{{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${\BBF_{{q^2}}}$. The first algorithm is devoted to the case when$q \equiv 1\, {\rm mod}\, 4$, whereas the second one handles the case when$q \equiv 3\, {\rm mod}\,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.