Misc.

Jul 20, 2006

Square Root Calculation Algorithm over Type-II All One Polynomial Field

IPSJ SIG Notes
  • KATOU Hidehiro
  • ,
  • WANG FENG
  • ,
  • NOGAMI Yasuyuki
  • ,
  • MORIKAWA Yoshitaka

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
CiNii Articles
http://ci.nii.ac.jp/naid/110004821005
CiNii Books
http://ci.nii.ac.jp/ncid/AA11235941
URL
http://id.ndl.go.jp/bib/8004451
URL
http://id.nii.ac.jp/1001/00044566/
ID information
  • ISSN : 0919-6072
  • CiNii Articles ID : 110004821005
  • CiNii Books ID : AA11235941

Export
BibTeX RIS