# Find root in finite field

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

-
en.wikipedia.org/wiki/… – Emil Jeřábek Feb 11 '13 at 18:57
Thank you! But it is too general method. Is there anything more specific? – Alexey Feb 11 '13 at 19:47
Which of $x$, $N$, $a$ are given and which are the variables to be solved for? – Greg Martin Feb 11 '13 at 19:48
N and a are given. – Alexey Feb 11 '13 at 19:59
I will assume that $a,N,q$ are given and you want to solve for $x$. Even then, there is no simple single answer. The problem changes if $q$ is a big prime, versus the case $q$ a big power of a small prime, versus intermediate cases. It also changes if $N$ is big versus $N$ small. If are interested in a particular range, making that explicit will help getting a better answer. – Felipe Voloch Feb 11 '13 at 20:02