© The Institution of Engineering and Technology
Presented is a square root algorithm in 𝔽_{ q } which generalises Atkins's square root algorithm [see reference 6] for q ≡ 5 (mod 8) and Müller's algorithm [see reference 7] for q ≡ 9 (mod 16). The presented algorithm precomputes 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 favourably compared with the algorithms of Atkin, Müuller and Kong et al.
References


1)

Shanks, D.: `Five numbertheoretic algorithms', Proc. 2nd Manitoba Conf. of Numerical Mathematics, Winnipeg, Manitoba, Canada, 1972, p. 51–70.

2)

D.H. Lehmer
.
(1969)
Computer technology applied to the theory of numbers.

3)

S. Lindhurst
.
An analysis for computing square roots in finite fields.
CRM Proc Lect. Notes
,
231 
242

4)

D.G. Han ,
D. Choi ,
H. Kim
.
Improved computation of square roots in specific finite fields.
IEEE Trans. Comput.
,
2 ,
188 
196

5)

N. Nishihara ,
R. Harasawa ,
Y. Sueyoshi ,
A. Kudo
.
A remark on the computation of cube roots in finite fields.

6)

A.O.L. Atkin
.
(1992)
Probabilistic primality testing.

7)

S. Müller
.
On the computation of square roots in finite fields.
Des. Codes Cryptogr.
,
301 
312

8)

F. Kong ,
Z. Cai ,
J. Yu ,
D. Li
.
Improved generalized Atkin algorithm for computing square roots in finite fields.
Inf. Process. Lett.
,
1 ,
1 
5
http://iet.metastore.ingenta.com/content/journals/10.1049/el.2012.4239
Related content
content/journals/10.1049/el.2012.4239
pub_keyword,iet_inspecKeyword,pub_concept
6
6