ETRI-Knowledge Sharing Plaform

ENGLISH

성과물

논문 검색
구분 SCI
연도 ~ 키워드

상세정보

학술지 Improved Computation of Square Roots in Specific Finite Fields
Cited 12 time in scopus Download 0 time Share share facebook twitter linkedin kakaostory
저자
한동국, 최두호, 김호원
발행일
200902
출처
IEEE Transactions on Computers, v.58 no.2, pp.188-196
ISSN
0018-9340
출판사
IEEE
DOI
https://dx.doi.org/10.1109/TC.2008.201
협약과제
08MS2200, 안전한 RFID/USN을 위한 정보보호 기술 개발, 정교일
초록
In this paper, we study exponentiation in the specific finite fields F q with very special exponents such as those that occur in algorithms for computing square roots. Here, q is a prime power, q = pk, where k > 1, and k is odd. Our algorithmic approach improves the corresponding exponentiation resulted from the better rewritten exponent. To the best of our knowledge, it is the first major improvement to the Tonelli-Shanks algorithm, for example, the number of multiplications can be reduced to at least 60 percent on the average when p = 1 (mod 16). Several numerical examples are given that show the speedup of the proposed methods. © 2006 IEEE.
키워드
Cryptography, Efficient computation, Finite fields, Square roots
KSP 제안 키워드
Algorithmic approach, Efficient computation, Numerical examples, Square root, finite field