A High-Speed Square Root Algorithm in Extension Fields

摘要

A square root (SQRT) algorithm in GF(p{sup}m) (m=r{sub}0r{sub}1...r{sub}(n-1)2{sup}d, r{sub}i: odd prime, d＞0: integer) is proposed in this paper, First, the Tonelli-Shanks algorithm is modified to compute the inverse SQRT in GF(p{sup}(2{sup}d)), where most of the computations are performed in the corresponding subfields GF(p{sup}(2{sup}i)) for 0≤i≤d-1. Then the Frobenius mappings with an addition chain are adopted for the proposed SQRT algorithm, in which a lot of computations in a given extension field GF(p{sup}m) are also reduce to those in a proper subfield by the norm computations. Those reductions of the field degree increase efficiency in the SQRT implementation. More specifically the Tonelli-Shanks algorithm and the proposed algorithm in GF(p{sup}22), GF(p{sup}44) and GF(p{sup}88) were implemented on a Pentium4 (2.6 GHz) computer using the C++ programming language. The computer simulations showed that, on average, the proposed algorithm accelerates the SQRT computation by 25 times in GF(p{sup}22), by 45 times in GF(p{sup}44), and by 70 times in GF(p{sup}88), compared to the Tonelli-Shanks algorithm, which is supported by the evaluation of the number of computations.