Fast modular calculation [duplicate]

I have the following equation:

$$ n \equiv M^k\pmod b $$

where $n, k, b$ are integers, and $M$ is an unknown integer. How can I solve this equation to find $M$? Here $k$ and $b$ are public keys of the RSA algorithm and $n$ is the result of encryption. I need to find the encrypted message.

Solution 1:

Generally it's difficult to compute such $\rm\:k$'th roots in $\rm \mathbb Z/b\ $ except for simple special cases, e.g. when $\rm\ gcd(k,\phi(b)) = 1.\,$ Otherwise one generally has to resort to factoring $\rm\:b\:$ to get $\rm\: \phi(b)\: $ and hence the factorization of $\rm\ \Bbb Z/b^*\ $ into a product of cyclic groups. Then one may apply generalizations of the Shanks or Tonelli 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.