What efficient algorithms exist for the solving $x^N = a$ in GF(q)? What are their complexities?
Take the 2minute tour
×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Pasting the title of your question into Google gives references like http://www.math.leidenuniv.nl/~astolk/monday/notes/stolkroots.pdf and http://www.ma.utexas.edu/users/voloch/Preprints/roots.pdf  this should answer your question. 

