Jul 13, 2004
A Fast Square Root Computation in Some Finite Fields
Technical report of IEICE. ISEC
- ,
- ,
- Volume
- 104
- Number
- 199
- First page
- 7
- Last page
- 13
- Language
- English
- Publishing type
- Publisher
- The Institute of Electronics, Information and Communication Engineers
It is well known that quadratic residue (QR) test should be implemented in advance of a square root (SQRT) computation. Smart algorithm, the previously known fastest algorithm for SQRT computation, only got the idea how to compute SQRT through QR test. However there is a lot of computation overlap in QR test and Smart algorithm. The essence of our proposition is thus to present a new QR test and SQRT algorithm to avoid all the overlapping computations. In this paper the authors devised a SQRT algorithm for which most of the data required have been computed in QR test. This yields many reductions in the computational time and amount. In GF(p) and GF(p^2), we implemented Smart algorithm and the proposed algorithm in C++ language on Pentium4 (2.6GHz), where p=2^<16>+1(4|p-1) and p = 2^<16>+3(4∤p-1). The computer simulations showed that for p=2^<16>+1 the proposed algorithm on average accelerates the SQRT computation 2 times and 10 times faster than Smart algorithm over GF(p) and GF(p^2), respectively and for p=2^<16>+3 the proposed algorithm on average accelerates the SQRT computation 20 times and 6 times faster than Smart algorithm over GF(p) and GF(p^2), respectively.
- Link information
-
- CiNii Articles
- http://ci.nii.ac.jp/naid/110003296433
- CiNii Books
- http://ci.nii.ac.jp/ncid/AN10060811
- URL
- http://id.ndl.go.jp/bib/7069541
- ID information
-
- ISSN : 0913-5685
- CiNii Articles ID : 110003296433
- CiNii Books ID : AN10060811