What efficient algorithms exist for the solving $x^N = a$ in GF(q)?
What are their complexities?



Find root in finite field
Pasting the title of your question into Google gives references like
<http://www.math.leidenuniv.nl/~astolk/monday/notes/stolk-roots.pdf> and
<http://www.ma.utexas.edu/users/voloch/Preprints/roots.pdf>
-- this should answer your question.


