MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|improve this question
2… – 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
up vote 2 down vote accepted

Pasting the title of your question into Google gives references like and -- this should answer your question.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.