1 132
ID 17849
JaLCDOI
Sort Key
13
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.
Publication Title
Memoirs of the Faculty of Engineering, Okayama University
Published Date
2009-01
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
OAI-PMH Set
岡山大学
language
英語
File Version
publisher
NAID
Eprints Journal Name
mfe