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 |
岡山大学
|
言語 |
英語
|
論文のバージョン | publisher
|
NAID | |
Eprints Journal Name | mfe
|