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 TonelliShanks 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 ≤ d1. 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 TonelliShanks 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 TonelliShanks algorithm.

Published Date  200901

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  13496115

NCID  AA12014085

Content Type 
Departmental Bulletin Paper

language 
英語

File Version  publisher

Refereed 
False

Eprints Journal Name  mfe
