access icon free Square root algorithm in 𝔽 q for q ≡ 2 s + 1 (mod 2 s+1)

© The Institution of Engineering and Technology
Received 06/12/2012, Published

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.

Inspec keywords: cryptography; encoding; algebra

Other keywords: coding theory; Atkins square root algorithm; positive integer; cryptography; Müller algorithm; square root computation

Subjects: Cryptography theory; Codes; Cryptography

References

    1. 1)
      • 5. Nishihara, N., Harasawa, R., Sueyoshi, Y., Kudo, A.: ‘A remark on the computation of cube roots in finite fields’, preprint, available at http://eprint.iacr.org/2009/457.pdf.
    2. 2)
      • 7. Müller, S.: ‘On the computation of square roots in finite fields’, Des. Codes Cryptogr., 2004, 31, pp. 301–312 (doi: 10.1023/B:DESI.0000015890.44831.e2).
    3. 3)
      • 8. Kong, F., Cai, Z., Yu, J., Li, D.: ‘Improved generalized Atkin algorithm for computing square roots in finite fields’, Inf. Process. Lett., 2006, 98, 1, pp. 1–5 (doi: 10.1016/j.ipl.2005.11.015).
    4. 4)
      • 1. Shanks, D.: ‘Five number-theoretic algorithms’. Proc. 2nd Manitoba Conf. of Numerical Mathematics, Winnipeg, Manitoba, Canada, 1972, pp. 51–70.
    5. 5)
      • 2. Lehmer, D.H.: ‘Computer technology applied to the theory of numbers’ in Studies in number theory, (Prentice-Hall, Englewood Cliffs, NJ, 1969), pp. 117–151.
    6. 6)
      • 4. Han, D., Choi, D., Kim, H.: ‘Improved computation of square roots in specific finite fields’, IEEE Trans. Comput., 2009, 58, 2, pp. 188–196 (doi: 10.1109/TC.2008.201).
    7. 7)
      • 3. Lindhurst, S.: ‘An analysis for computing square roots in finite fields’, CRM Proc Lect. Notes, 1999, 19, pp. 231–242.
    8. 8)
      • 6. Atkin, A.O.L.: ‘Probabilistic primality testing’, summary by F. Morain, Inria Res. Rep. 1779, 1992, pp. 159–163.
    9. 9)
      • Shanks, D.: `Five number-theoretic algorithms', Proc. 2nd Manitoba Conf. of Numerical Mathematics, Winnipeg, Manitoba, Canada, 1972, p. 51–70.
    10. 10)
    11. 11)
      • N. Nishihara , R. Harasawa , Y. Sueyoshi , A. Kudo . A remark on the computation of cube roots in finite fields.
    12. 12)
    13. 13)
      • S. Lindhurst . An analysis for computing square roots in finite fields. CRM Proc Lect. Notes , 231 - 242
    14. 14)
    15. 15)
      • D.H. Lehmer . (1969) Computer technology applied to the theory of numbers.
    16. 16)
      • A.O.L. Atkin . (1992) Probabilistic primality testing.
http://iet.metastore.ingenta.com/content/journals/10.1049/el.2012.4239
Loading

Related content

content/journals/10.1049/el.2012.4239
pub_keyword,iet_inspecKeyword,pub_concept
6
6
Loading