Cryptology ePrint Archive: Report 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 $\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.

Category / Keywords: Modular square root, finite field arithmetic, Legendre symbol

Date: received 4 Dec 2012, last revised 18 Jul 2013

Contact author: francisco at cs cinvestav mx

Available format(s): PDF | BibTeX Citation

Version: 20130718:212254 (All versions of this report)

Short URL: ia.cr/2012/685

Discussion forum: Show discussion | Start new discussion