Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)

 
 

 

Taking roots over high extensions of finite fields


Authors: Javad Doliskani and Éric Schost
Journal: Math. Comp. 83 (2014), 435-446
MSC (2010): Primary 11Y16, 12Y05; Secondary 68W30
DOI: https://doi.org/10.1090/S0025-5718-2013-02715-9
Published electronically: May 28, 2013
MathSciNet review: 3120598
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: We present a new algorithm for computing $ m$-th roots over the finite field $ \mathbb{F}_q$, where $ q = p^n$, with $ p$ a prime, and $ m$ any positive integer. In the particular case $ m=2$, the cost of the new algorithm is an expected $ O(\mathsf {M}(n)\log (p) + \mathsf {C}(n)\log (n))$ operations in $ \mathbb{F}_p$, where $ \mathsf {M}(n)$ and $ \mathsf {C}(n)$ are bounds for the cost of polynomial multiplication and modular polynomial composition. Known results give $ \mathsf {M}(n) = O(n\log (n) \log \log (n))$ and $ \mathsf {C}(n) = O(n^{1.67})$, so our algorithm is subquadratic in $ n$.


References [Enhancements On Off] (What's this?)

  • 1. E. Bach and J. Shallit, Algorithmic number theory; volume I: Efficient algorithms, The MIT Press, 1996. MR 1406794 (97e:11157)
  • 2. P. Barreto and J. Voloch, Efficient computation of roots in finite fields, Designs, Codes and Cryptography 39 (2006), 275-280. MR 2209942 (2006j:12014)
  • 3. P. S. L. M. Barreto, H. Y. Kim, B. Lynn, and M. Scott, Efficient algorithms for pairing-based cryptosystems, Advances in cryptology--CRYPTO 2002, Lecture Notes in Comput. Sci., vol. 2442, Springer, 2002, pp. 354-368. MR 2054831 (2004m:94031)
  • 4. R. P. Brent and H. T. Kung, Fast algorithms for manipulating formal power series, Journal of the Association for Computing Machinery 25 (1978), no. 4, 581-595. MR 0520733 (58:25090)
  • 5. D. G. Cantor and E. Kaltofen, On fast multiplication of polynomials over arbitrary algebras, Acta Informatica 28 (1991), no. 7, 693-701. MR 1129288 (92i:68068)
  • 6. D. Coppersmith and S. Winograd, Matrix multiplication via arithmetic progressions, J. Symb. Comp 9 (1990), no. 3, 251-280. MR 1056627 (91i:68058)
  • 7. J. von zur Gathen and V. Shoup, Computing Frobenius maps and factoring polynomials, Comput. Complexity 2 (1992), no. 3, 187-224. MR 1220071 (94d:12011)
  • 8. P. Gaudry and É. Schost, Genus 2 point counting over prime fields, Journal of Symbolic Computation 47 (2012), no. 4, 368-400.
  • 9. D.-G. Han, D. Choi, and H. Kim, Improved computation of square roots in specific finite fields, IEEE Trans. Comput. 58 (2009), 188-196. MR 2488396 (2010f:94224)
  • 10. X. Huang and V. Y. Pan, Fast rectangular matrix multiplication and applications, J. Complexity 14 (1998), no. 2, 257-299. MR 1629113 (99i:15002)
  • 11. T. Itoh and S. Tsujii, A fast algorithm for computing multiplicative inverses in $ {\rm GF}(2^m)$ using normal bases, Inform. and Comput. 78 (1988), no. 3, 171-177. MR 959807 (89j:11121)
  • 12. E. Kaltofen and V. Shoup, Fast polynomial factorization over high algebraic extensions of finite fields, ISSAC'97, ACM, 1997, pp. 184-188. MR 1809986 (2001i:68174)
  • 13. K. S. Kedlaya and C. Umans, Fast polynomial factorization and modular composition, SIAM J. Computing 40 (2011), no. 6, 1767-1802. MR 2863194
  • 14. F. Kong, Z. Cai, J. Yu, and D. Li, Improved generalized Atkin algorithm for computing square roots in finite fields, Inform. Process. Lett. 98 (2006), no. 1, 1-5. MR 2201616 (2006h:68068)
  • 15. S. Müller, On the computation of square roots in finite fields, Des. Codes Cryptogr. 31 (2004), no. 3, 301-312. MR 2047886 (2005f:11278)
  • 16. N. Nishihara, R. Harasawa, Y. Sueyoshi, and A. Kudo, A remark on the computation of cube roots in finite fields, Cryptology ePrint Archive, Report 2009/457, 2009, http://eprint.iacr.org/.
  • 17. C. Padró and G. Sáez, Taking cube roots in $ \mathbb{Z}_m$, Applied Mathematics Letters 15 (2002), no. 6, 703 - 708. MR 1913273 (2003e:11139)
  • 18. S. C. Pohlig and M. E. Hellman, An improved algorithm for computing logarithms over $ {\rm GF}(p)$ and its cryptographic significance, IEEE Transactions on Information Theory IT-24 (1978), 106-110. MR 0484737 (58:4617)
  • 19. A. Schönhage and V. Strassen, Schnelle Multiplikation grosser Zahlen, Computing 7 (1971), 281-292. MR 0292344 (45:1431)
  • 20. D. Shanks, Five number-theoretic algorithms, Proceedings of the Second Manitoba Conference on Numerical Mathematics, 1972, pp. 51-70. MR 0371855 (51:8072)
  • 21. V. Shoup, Fast Construction of Irreducible Polynomials over Finite Fields, Journal of Symbolic Computation 17 (1994), no. 5, 371-391. MR 1289997 (95k:11156)
  • 22. -, A library for doing number theory (NTL), http://www.shoup.net/ntl/, 2009.
  • 23. A. Tonelli, Bemerkung über die Auflösung quadratischer Congruenzen, Göttinger Nachrichten (1891), 344-346.
  • 24. G. Tornaría, Square roots modulo $ p$, LATIN 2002: Theoretical Informatics, Lecture Notes in Comput. Sci., vol. 2286, Springer, 2002, pp. 430-434. MR 1966140 (2004a:11135)
  • 25. C. Umans, Fast polynomial factorization and modular composition in small characteristic, STOC, 2008, pp. 481-490. MR 2582906 (2011c:68221)
  • 26. J. von zur Gathen and J. Gerhard, Modern Computer Algebra, Cambridge University Press, 2003. MR 2001757 (2004g:68202)
  • 27. H. C. Williams, Some algorithms for solving $ x^{q}\equiv N$ $ ({\rm mod}\ p)$, Proceedings of the Third Southeastern Conference on Combinatorics, Graph Theory and Computing (Florida Atlantic Univ., Boca Raton, Fla., 1972), Florida Atlantic Univ., 1972, pp. 451-462. MR 0364065 (51:320)
  • 28. K. S. Williams and K. Hardy, A refinement of H. C. Williams' $ q$th root algorithm, Math. Comp. 61 (1993), no. 203, 475-483. MR 1182249 (93k:11003)

Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2010): 11Y16, 12Y05, 68W30

Retrieve articles in all journals with MSC (2010): 11Y16, 12Y05, 68W30


Additional Information

Javad Doliskani
Affiliation: Department of computer Science, University of Western Ontario
Email: jdoliska@uwo.ca

Éric Schost
Affiliation: Department of computer Science, University of Western Ontario
Email: eschost@uwo.ca

DOI: https://doi.org/10.1090/S0025-5718-2013-02715-9
Keywords: Root extraction, square roots, finite field arithmetic.
Received by editor(s): September 21, 2011
Received by editor(s) in revised form: April 29, 2012
Published electronically: May 28, 2013
Additional Notes: We thank NSERC and the Canada Research Chairs program for financial support. We also thank the referee for very helpful remarks.
Article copyright: © Copyright 2013 American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication.

American Mathematical Society