APPARATUS AND METHOD OF CALCULATING SQUARE ROOT IN FINITE EXTENSION FIELD

摘要

Disclosed is an apparatus and a method of calculating the square root of an element a, which is not zero, belonging to a finite extension field F_pAk (where p is a prime number satisfying p≡3(mod 4) and k is an odd number). The method includes: calculating a common exponentiation formula that is common to an exponentiation formula for calculating a quadratic residue, which is used to determine whether the square root of the element a is present, and an exponentiation formula for calculating the square root of the element a when it is determined that the square root of the element a is present; determining the result obtained by multiplying the square of the common exponentiation formula by the element a as the quadratic residue; and determining the result obtained by multiplying the common exponentiation formula by the element a as the square root of the element a.