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   Vol.E88-A   No.10   pp.2792-2799
Publication Date: 2005/10/01
Online ISSN: 
DOI: 10.1093/ietfec/e88-a.10.2792
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>>
Buy this Article

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.