An Efficient Square Root Computation in Finite Fields GF(p^2d)

Feng WANG, Yasuyuki NOGAMI, Yoshitaka MORIKAWA

Summary :

This paper focuses on developing a square root (SQRT) algorithm in finite fields GF(p^2d) (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(p^2d), in which not only there is no computation overlap, but also most of computations required for the proposed SQRT algorithm in GF(p^2d) can be implemented in the corresponding subfields GF(p2^d-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.

• Publication: IEICE TRANSACTIONS on Fundamentals Vol.E88-A No.10 pp.2792-2799
• Publication Date: 2005/10/01
• DOI: 10.1093/ietfec/e88-a.10.2792
• Type of Manuscript: Special Section PAPER (Special Section on Information Theory and Its Applications)
• Category: Cryptography and Information Security

Authors

Feng WANG
Yasuyuki NOGAMI
Yoshitaka MORIKAWA

Keyword

square root,  finite fields,  quadratic residue