1

I have to calculate the $n$-th root of a number $x$ modulo $m$:

$$\sqrt[n]{x} = a\quad \mod(m),$$

where $x$, $n$ as well as $m$ are known. The only unknown number is $a$.

It would already help me a lot, if I could convert it to a type of problem like

$$x^y = a \quad \mod(m)$$

where $x$, $y$ and $m$ are known.

xxsl
  • 99
  • Some questions: Such an $n$-th root does not always exist. Are we assuming that $x,n,m$ are such that there is one? If an $n$-th root exists, it is in general not unique. Do you want to find them all, or just one? Any conditions on $a$ and $m$, such as coprimality, or can they be anything? – Bart Michels Oct 17 '16 at 20:43

1 Answers1

2

If $\gcd(a, m) = 1$, then by Euler's theorem we have, for any natural number $i$, that $$ a^{i\phi(m) + 1} \equiv a \pmod m $$ where $\phi(m)$ is the Euler totient of $m$. That means that if $a^n \equiv x$, then we are looking for some $i$ that makes $i\phi(m) + 1$ a multiple of $n$. In other words, we are looking for $i, j$ such that $jn = i\phi(m) + 1$. Because if we find such a number, then $x^j = (a^n)^j = a^{nj} = a^{i\phi(m) + 1}\equiv a$. So taking the $n$-th root is the same as raising to the $j$-th power.

How do we find such a number $j$? We need $\phi(m)$, first and foremost. (Which is very hard work to do unless $m$ is relatively small, or you know the prime decomposition of $m$. This is the main source of security behind, for instance, the RSA algorithm. They supply $m$ and $n$ to anyone who wants to encrypt, which you do by raising your card number, say, to the $n$-th power modulo $m$, and then they keep $\phi(m)$ very secret so that they are the only ones who can calculate $j$.)

We need that $n$ to be such that $\gcd(n, \phi(m)) = 1$, because otherwise there are no $i, j$ such that $jn - i\phi(m) = 1$. Then we need to find $i$ and $j$ (technically we only need $j$, but they come in a pair). Once you've done that, you can take the $n$-th root of any $x$ you want, provided $\gcd(x, m) = 1$, by calculating $x^j$.

Arthur
  • 199,419
  • Thank you for your quick answer. I will try to solve the problem now. – xxsl Oct 17 '16 at 20:49
  • 1
    You can replace $\phi(n)$ by $\lambda(n)$, the Carmichael function (it is usually smaller) and your construct will continue to work. – achille hui Oct 17 '16 at 20:52
  • @achillehui True. But while the Charmichael function by definition is the smallest positive function that makes this work, and thus you don't have to prove Euler's theorem, $\phi$ is easier to compute. – Arthur Oct 17 '16 at 20:54
  • How could I verify, e.g. using Wolfram Alpha, that my solution is correct? – xxsl Oct 17 '16 at 21:04
  • That depends on how big your numbers are. But WA is very good at calculating, say, a table of $(a^{12})^{43}$ modulo $15$ to see whether it happens to be $a$ for those numbers where $\gcd(a, 15)$. if that's your thing (I don't know whether those are actual numbers that would appear together in this setting, but I hope you get my point). – Arthur Oct 17 '16 at 21:06