Taking Roots over High Extensions of Finite Fields

2011/10/19 by Doliskani, Javad, Schost, Eric
#11Y16 #12Y05 (Primary) 68W30 (Secondary) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences

paper · doi:10.48550/arxiv.1110.4350

Abstract

We present a new algorithm for computing m-th roots over the finite field \F_q, where q = pⁿ, 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(\M(n)log (p) + \CC(n)log(n)) operations in \F_p, where \M(n) and \CC(n) are bounds for the cost of polynomial multiplication and modular polynomial composition. Known results give \M(n) = O(nlog (n) loglog (n)) and \CC(n) = O(n^1.67), so our algorithm is subquadratic in n.

Related

• Improvement Of Barreto-Voloch Algorithm For Computing rth Roots Over Finite Fields
• Faster polynomial multiplication over finite fields
• Character Sums and Deterministic Polynomial Root Finding in Finite Fields
• On Taking r-th Roots without r-th Nonresidues over Finite Fields and Its Applications
• Enumerating all the Irreducible Polynomials over Finite Field