ID 17849
JaLCDOI
Sort Key
13
フルテキストURL
著者
Kato, Hidehiro Graduate School of Natural Science and Technology, Okayama University
Nogami, Yasuyuki Graduate School of Natural Science and Technology, Okayama University Kaken ID publons researchmap
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.
出版物タイトル
Memoirs of the Faculty of Engineering, Okayama University
発行日
2009-01
43巻
出版者
Faculty of Engineering, Okayama University
出版者(別表記)
岡山大学工学部
開始ページ
99
終了ページ
107
ISSN
1349-6115
NCID
AA12014085
資料タイプ
紀要論文
OAI-PMH Set
岡山大学
言語
English
論文のバージョン
publisher
NAID
Eprints Journal Name
mfe
過去1年のアクセス数
アクセス数 : ?
ダウンロード数 : ?

今月のアクセス数
アクセス数 : ?
ダウンロード数 : ?