このエントリーをはてなブックマークに追加
ID 17849
Eprint ID
17849
FullText URL
Author
Kato, Hidehiro
Morikawa, Yoshitaka
Abstract
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.
Published Date
2009-01
Publication Title
Memoirs of the Faculty of Engineering, Okayama University
Publication Title Alternative
岡山大学工学部紀要
Volume
volume43
Publisher
Faculty of Engineering, Okayama University
Publisher Alternative
岡山大学工学部
Start Page
99
End Page
107
ISSN
1349-6115
NCID
AA12014085
Content Type
Departmental Bulletin Paper
language
英語
File Version
publisher
Refereed
False
Eprints Journal Name
mfe