A High-Speed Square Root Algorithm for Extension fields -Especially for Fast Extension Fields-

• Kato Hidehiro

• Nogami Yasuyuki

• Morikawa Yoshitaka

抄録

A square root (SQRT) algorithm in extension field F(p(m))(m = r(0)r(1)･･･r(n−1)･2(d), r(i) : odd prime, d : positive integer) is proposed in this paper. First, a conventional SQRT algorithm, the Tonelli-Shanks algorithm, is modified to compute the inverse SQRT in F(p(2d)), where most of the computations are performed in the corresponding subfields F(p(2i)) for 0 ≤ i ≤ d-1. Then the Frobenius mappings with addition chain are adopted for the proposed SQRT algorithm, in which a lot of computations in a given extension field F(p(m)) are also reduced to those in a proper subfield by the norm computations. Those reductions of the field degree increase efficiency in the SQRT implementation. The Tonelli-Shanks algorithm and the proposed algorithm in F(p(6)) and F(p(10)) were implemented on a Core2 (2.66 GHz) using the C++ programming language. The computer simulations showed that, on average, the proposed algorithm accelerated the SQRT computation by 6 times in F(p(6)), and by 10 times in F(p(10)), compared to the Tonelli-Shanks algorithm.

収録刊行物

• Memoirs of the Faculty of Engineering, Okayama University

  Memoirs of the Faculty of Engineering, Okayama University 43 99-107, 2009-01

  Faculty of Engineering, Okayama University

詳細情報

• CRID: 1390572174548644224
• NII論文ID: 120002308980
• NII書誌ID: AA12014085
• ISSN: 13496115
• DOI: 10.18926/17849
• Web Site: https://ousar.lib.okayama-u.ac.jp/17849
• 本文言語コード: en
• データソース種別:
  • JaLC
  • IRDB
  • CiNii Articles