| Presentation | 2004-07-20 A Fast Square Root Computation in Some Finite Fields Feng WANG, Yasuyuki NOGAMI, Yoshitaka MORIKAWA, |
|---|---|
| PDF Download Page |  PDF download Page Link |
| Abstract(in Japanese) | (See Japanese page) |
| Abstract(in English) | 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. |
| Keyword(in Japanese) | (See Japanese page) |
| Keyword(in English) | Square root / Finite fields |
| Paper # | ISEC2004-14 |
| Date of Issue |
| Conference Information | |
| Committee | ISEC |
|---|---|
| Conference Date | 2004/7/13(1days) |
| Place (in Japanese) | (See Japanese page) |
| Place (in English) | |
| Topics (in Japanese) | (See Japanese page) |
| Topics (in English) | |
| Chair | |
| Vice Chair | |
| Secretary | |
| Assistant | |
| Paper Information | |
| Registration To | Information Security (ISEC) |
|---|---|
| Language | ENG |
| Title (in Japanese) | (See Japanese page) |
| Sub Title (in Japanese) | (See Japanese page) |
| Title (in English) | A Fast Square Root Computation in Some Finite Fields |
| Sub Title (in English) | |
| Keyword(1) | Square root |
| Keyword(2) | Finite fields |
| 1st Author's Name | Feng WANG |
| 1st Author's Affiliation | Communication Network Engineering, Okayama University() |
| 2nd Author's Name | Yasuyuki NOGAMI |
| 2nd Author's Affiliation | Communication Network Engineering, Okayama University |
| 3rd Author's Name | Yoshitaka MORIKAWA |
| 3rd Author's Affiliation | Communication Network Engineering, Okayama University |
| Date | 2004-07-20 |
| Paper # | ISEC2004-14 |
| Volume (vol) | vol.104 |
| Number (no) | 199 |
| Page | pp.pp.- |
| #Pages | 7 |
| Date of Issue | |