2
$\begingroup$

This question already has an answer here:

I would like to solve for $x$ in $a = x^b\ (mod\ n)$ given $a$, $b$, $n$. How might I go about doing this?

$\endgroup$

marked as duplicate by Claude Leibovici, Shailesh, Zain Patel, Leucippus, user223391 Apr 24 '17 at 4:03

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • 1
    $\begingroup$ That answer primarily covers square roots, it doesn't seem to well cover a generalized case where b is some arbitrary integer. $\endgroup$ – Bradley Evans Apr 22 '17 at 6:01
0
$\begingroup$

In general there is no such method.

Are the numbers small enough to brute force? Can you factor $n$?

$\endgroup$
  • $\begingroup$ In the specific case I'm working (bit of a tricky personal cryptanalysis brain teaser) n is known to be the product of primes p and q (n is semi-prime), and n is sufficiently large to make brute force unfeasible. b is quite small, however (in my particular case, 5, but I was trying to come up with a more general picture). $\endgroup$ – Bradley Evans Apr 22 '17 at 6:06
  • $\begingroup$ Do you know $p$ and $q$? $\endgroup$ – yberman Apr 22 '17 at 13:47
  • $\begingroup$ No, unfortunately. $\endgroup$ – Bradley Evans Apr 23 '17 at 17:23
  • $\begingroup$ So you are basically trying to undo RSA? $\endgroup$ – yberman Apr 23 '17 at 21:33

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