What efficient algorithms exist for the solving $x^N = a$ in GF(q)? What are their complexities?
$\begingroup$
$\endgroup$
5
-
2$\begingroup$ en.wikipedia.org/wiki/… $\endgroup$– Emil JeřábekCommented Feb 11, 2013 at 18:57
-
$\begingroup$ Thank you! But it is too general method. Is there anything more specific? $\endgroup$– Alexey MilovanovCommented Feb 11, 2013 at 19:47
-
1$\begingroup$ Which of $x$, $N$, $a$ are given and which are the variables to be solved for? $\endgroup$– Greg MartinCommented Feb 11, 2013 at 19:48
-
$\begingroup$ N and a are given. $\endgroup$– Alexey MilovanovCommented Feb 11, 2013 at 19:59
-
1$\begingroup$ 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. $\endgroup$– Felipe VolochCommented Feb 11, 2013 at 20:02
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
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.
answered Feb 11, 2013 at 19:59