1. Square Root Computation over Even Extension Fields.
- Author
-
Adj, Gora and Rodriguez-Henriquez, Francisco
- Subjects
- *
SQUARE root , *FIELD extensions (Mathematics) , *ALGORITHMS , *MATHEMATICAL models , *ROUGH sets , *COMPUTATIONAL complexity - 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 \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\, mod\, 4, whereas the second one handles the case when q \equiv 3\, 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. [ABSTRACT FROM AUTHOR]
- Published
- 2014
- Full Text
- View/download PDF