Need help on where to start here.

Given $a^b\mod c = d$, where $b$, $c$ and $d$ is known, how do I find $a$?


I just wrote some arbitrary number here:

$x^{13} \mod 47 = 17$, how do I convert this to x = .... mod 47? From my understanding, it will be $x= 7^{1/13} \mod 47$ but how do I simplify that to an all-integer form.

  • $\begingroup$ Do we have any constraints on the values of $b,c,$ and $d$? $\endgroup$ – Mike Pierce Jan 14 '15 at 16:53
  • $\begingroup$ We have a constraints on the number of digit available on the calculator used to perform the computation to find a. @mapierce271 $\endgroup$ – Stupid Jan 14 '15 at 17:19

You do the same thing as if this was an equation in more familiar arithmetic: compute the $b$-th roots of $d$ modulo $c$.

  • $\begingroup$ Ah okay, can do that with a calculator. Although it mention about the digit limitation of the calculator used. Do you know anything about that? @Hurkyl $\endgroup$ – Stupid Jan 14 '15 at 17:18
  • $\begingroup$ I'm used to having a computer program that can either deal with big integers, or actually has modular exponentiation built-in. If you have to do it yourself, you could use one of the "square and multiply" algorithms for computing exponentiation. $\endgroup$ – user14972 Jan 14 '15 at 17:41
  • $\begingroup$ I chose an arbitrary number here $x^{13} \mod 47 = 17$, how do I convert this to x = .... mod 47? Because in this case it will be $x= 7^{1/13} \mod 47$ how do I simplify that? @Hurkyl $\endgroup$ – Stupid Jan 14 '15 at 22:29
  • $\begingroup$ What confuse me here is the exponent $1/13$, what can we do with it to simplify the expression? Cause if there is a rule for it, please do tell. $\endgroup$ – Stupid Jan 14 '15 at 22:36
  • $\begingroup$ @Stud: I had assumed the phrase "modular roots" would ring a bell, or at least provide a hint for searching. Your particular example is a simple case, though, since in arithmetic modulo 47, exponents are integers modulo 46 (or modulo a factor of 46, depending on the particular base), and you can simplify 1/13 modulo 46. $\endgroup$ – user14972 Jan 16 '15 at 4:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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