Jul 20, 2006
Square Root Calculation Algorithm over Type-II All One Polynomial Field
IPSJ SIG Notes
- ,
- ,
- ,
- Volume
- 2006
- Number
- 81
- First page
- 7
- Last page
- 12
- Language
- Japanese
- Publishing type
- Publisher
- Information Processing Society of Japan (IPSJ)
The authors proposes a square root (SQRT) algorithm in F_p^m (m = r_0r_1…r_<n-1>2^d,r_2: odd prime, d>0: integer). We compute the inverse SQRT in F_p^2^d using MW-ST algorithm. Then the Frobenius mappings with an addition chain are adopted for this SQRT algorithm, in which a lot of computations in a given extension field F_p^m are also reduce to those in a proper subfield by the norm computations. Those reductions of the field degree increases efficiency in the SQRT implementation. More specifically the Smart algorithm and proposed algorithm in F_p^6, for example, were implemented on a Pentium4 (3.8FHz) computer using the C++ programming language and NTL Library. The computer simulations showed that, on average, the proposed algoithm accelerates the SQRT computation by 3 times in F_p^6, compared to the Smart algorithm.
- Link information
- ID information
-
- ISSN : 0919-6072
- CiNii Articles ID : 110004821005
- CiNii Books ID : AA11235941