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 |
English
|
File Version | publisher
|
NAID | |
Eprints Journal Name | mfe
|