An Efficient Square Root Computation in Finite Fields GF(p^<2d>)(Cryptography and Information Security, <Special Section>Information Theory and Its Applications)

概要

論文の詳細を見る
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(p^<2d-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.
社団法人電子情報通信学会の論文
2005-10-01