High-speed algorithm for taking square root in an extension field by using (x{sup}(m+1) - 1)/(x - 1) as the modulus

摘要

ECC （Elliptic Curve Cryptosystem） is expected as a next generation public-key cryptosystem. Four arithmetic operations on finite field including the inverse operation, quadratic residue test, and square root derivation are necessary to implement ECC. These operations must be enough speedy to make ECC practical. In this paper, we propose a high speed algorithm for taking square root in an extension field AOPE (All One Polynomial Field) by using (x{sup}(m+1) -1)/(x-1) as the modulus.