Square Root Algorithm in Fq for Special Class of Finite Fields
Namhun Koo, Gooc Hwa Jo, Soonhak Kwon · 한국통신학회논문지 · 2013
$q{\equiv}5$ (mod 8)의 경우에 유한체 $F_q$ 상에서 Atkin의 제곱근 알고리즘과 $q{\equiv}9$ (mod 16)의 경우에 Kong의 알고리즘으로부터 일반적인 제곱근 알고리즘을 제안한다. 우리의 알고리즘은 s가 $2^s|q-1$ 을 만족하는 가장 큰 양의 정수라 할 때, $2^s$ 차 원시근 ${\xi}$ 를 미리 계산하였고 s의 값이 작을 때 적용가능하다. 제시한 알고리즘은 제곱근을 계산하기 위해 한 번의 지수계산이 필요하고, Akin, M $\ddot{u}$ ller, Kong의 알고리즘과 비교해보아도 유리하다. We present a square root algorithm in $F_q$ which generalizes Atkin's square root algorithm [9] for finite field $F_q$ of q elements where $q{\equiv}5$ (mod 8) and Kong et al.'s algorithm [11] for the case $q{\equiv}9$ (mod 16). Our algorithm precomputes ${\xi}$ a primitive $2^s$ -th root of unity where s is the largest positive integer satisfying $2^s|q-1$ , and is applicable for the cases when s is small. The proposed algorithm requires one exponentiation for square root computation and is favorably compared with the algorithms of Atkin, M $\ddot{u}$ ller and Kong et al.