Efficient method for finding square roots for elliptic curves over OEF

Abstract

Elliptic curve cryptosystems like others public key encryption schemes, require computing a square roots modulo a prime number. The arithmetic operations in elliptic curve schemes over Optimal Extension Fields (OEF) can be efficiently computed by using an irreducible binomial. This paper provides an overview of the OEF, Frobenius map and embedding points on an elliptic curve. The focus is on describing an efficient method to find a square root over Optimal Extension algorithm which is based on the Frobenius map, in order to simplify the problem of finding the square root over OEF.