Taking roots over high extensions of finite fields
Javad Doliskani, Éric Schost · Mathematics of Computation · 2013
We present a new algorithm for computing m m -th roots over the finite field F q \mathbb {F}_q , where q = p n q = p^n , with p p a prime, and m m any positive integer. In the particular case m = 2 m=2 , the cost of the new algorithm is an expected O ( M ( n ) log ( p ) + C ( n ) log ( n ) ) O(\mathsf {M}(n)\log (p) + \mathsf {C}(n)\log (n)) operations in F p \mathbb {F}_p , where M ( n ) \mathsf {M}(n) and C ( n ) \mathsf {C}(n) are bounds for the cost of polynomial multiplication and modular polynomial composition. Known results give M ( n ) = O ( n log