このエントリーをはてなブックマークに追加
ID 17849
Eprint ID
17849
フルテキストURL
著者
Kato, Hidehiro Graduate School of Natural Science and Technology, Okayama University
Nogami, Yasuyuki Graduate School of Natural Science and Technology, Okayama University
Morikawa, Yoshitaka Graduate School of Natural Science and Technology, Okayama University
抄録
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.
発行日
2009-01
出版物タイトル
Memoirs of the Faculty of Engineering, Okayama University
出版物タイトル(別表記)
岡山大学工学部紀要
43巻
出版者
Faculty of Engineering, Okayama University
出版者(別表記)
岡山大学工学部
開始ページ
99
終了ページ
107
ISSN
1349-6115
NCID
AA12014085
資料タイプ
紀要論文
言語
English
論文のバージョン
publisher
査読
無し
Eprints Journal Name
mfe