# Solve for x in $a = x^b$ (mod n) [duplicate]

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

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

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

In general there is no such method.

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

• 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). – Bradley Evans Apr 22 '17 at 6:06
• Do you know $p$ and $q$? – yberman Apr 22 '17 at 13:47
• No, unfortunately. – Bradley Evans Apr 23 '17 at 17:23
• So you are basically trying to undo RSA? – yberman Apr 23 '17 at 21:33