Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS
   
Mobile Device Pairing
Green Open Access
Mathematics of Computation
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
Published electronically: May 28, 2013
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?)


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: http://dx.doi.org/10.1090/S0025-5718-2013-02715-9
PII: S 0025-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.