Open AccessSquare root algorithm in 𝔽 q for q ≡ 2 s + 1 (mod 2 s +1 )
Author(s) -
Koo Namhun,
Cho Gook Hwa,
Kwon Soonhak
Publication year - 2013
Publication title -
electronics letters
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.375
H-Index - 146
ISSN - 1350-911X
DOI - 10.1049/el.2012.4239
Subject(s) - square root , mod , mathematics , integer (computer science) , root (linguistics) , square (algebra) , algorithm , combinatorics , computation , discrete mathematics , geometry , computer science , linguistics , philosophy , programming language
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.