For Full-Text PDF, please login, if you are a member of IEICE,|
or go to Pay Per View on menu list, if you are a nonmember of IEICE.
An Efficient Square Root Computation in Finite Fields GF(p2d)
Feng WANG Yasuyuki NOGAMI Yoshitaka MORIKAWA
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Publication Date: 2005/10/01
Print ISSN: 0916-8508
Type of Manuscript: Special Section PAPER (Special Section on Information Theory and Its Applications)
Category: Cryptography and Information Security
square root, finite fields, quadratic residue,
Full Text: PDF>>
This paper focuses on developing a square root (SQRT) algorithm in finite fields GF(p2d) (d 0). Examining the Smart algorithm, a well-known SQRT algorithm, we can see that there is some computation overlap between the Smart algorithm and the quadratic residue (QR) test, which must be implemented before a SQRT computation. It makes the Smart algorithm inefficient. In this paper, we propose a new QR test and a new SQRT algorithm in GF(p2d), in which not only there is no computation overlap, but also most of computations required for the proposed SQRT algorithm in GF(p2d) can be implemented in the corresponding subfields GF(p2d-i) for 1 i d, which yields many reductions in the computational time and complexity. The computer simulation also shows that the proposed SQRT algorithm is much faster than the Smart algorithm.