Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS

Remote Access
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
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?)

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

Éric Schost
Affiliation: Department of computer Science, University of Western Ontario

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.

Comments: Email Webmaster

© Copyright , American Mathematical Society
Contact Us · Sitemap · Privacy Statement

Connect with us Facebook Twitter Google+ LinkedIn Instagram RSS feeds Blogs YouTube Podcasts Wikipedia