A problem on Number theory You are given three non-negative integers $A$, $B$ and $C$, find a number $X$ (say) satisfy
$X^A \equiv B\pmod{2C + 1}$ and $0 \le X \le 2C$.
I am inquisitive about how to approach this one?
 A: Assuming X coprime to 2C+1. Then Euler totient theorem gives $X^{\varphi(2C+1)} \equiv 1 \mod 2C+1$.
Assuming further that A coprime to $\varphi(2C+1)$. Then (By Bezout's identity) there's a D such that $AD \equiv 1 \mod \varphi(2C+1)$. In which case $(X^A)^D \equiv X^{(AD)} \equiv X \equiv B^D \mod 2C+1$
In steps:
1- Compute $\varphi(2C+1)$ (Which should be very time consuming if it's a product of large primes). 
2- Obtain D (through extended euclidean algorithm!)
3- Compute $B^D \mod 2C+1$.
Note, if a fast solution to your problem exists, then RSA cryptography would be insecure.
A: Generally it's difficult to compute such $\rm\:A$'th roots in $\rm \mathbb Z/m\ $ except for simple special cases, e.g. when $\rm\ gcd(A,\phi(m)) = 1\:.\ $ Otherwise one generally has to resort to factoring $\rm\:m\:$ to get $\rm\: \phi(m)\: $ and hence the factorization of $\rm\ Z/m^*\ $ into a product of cyclic groups. Then one may apply generalizations of Shanks's  square-root algorithm. See for example Section 3.2: Extensions of Shanks's algorithm to r'th roots in cyclic groups in Lindhurst: Computing roots in finite fields and groups, with a jaunt through sums of digits. One can also generalize the Euler criterion for square-roots - see my post here and Chapter 4 of Ireland and Rosen, A Classical Introduction to Modern Number Theory.
