On $r$ -th Root Extraction Algorithm in $\mathbb {F}_q$ for $q\equiv lr^{s}+1\;({\mathrm mod}\; r^{s+1})$ with $0< l< r$ and Small $s$
Namhun Koo, Gook Hwa Cho, Soonhak Kwon · IEEE Transactions on Computers · 2015
We present an r-th root extraction algorithm over a finite field Fq. Our algorithm precomputes a primitive rs-th root of unity ξ where s is the largest positive integer satisfying rs|q -1, and is applicable for the cases when s is small. The proposed algorithm requires one exponentiation for the r-th root computation and is favorably compared to the existing algorithms.