Note: this is not exactly the RSA problem. For it to be the RSA problem, the modulus would have to be composite. Turns out, in this case, the modulus is prime.
Note also: this is not the discrete log problem, as in the discrete log problem we are trying to find the exponent, not the base.
That said, you can find the answer using the method that CodesInChaos recommended.
mod is already prime, so it is factored.
phi(mod). This is the euler totient function. For primes,
phi(mod)=mod-1. So in your case,
d such that
power*d=1 modulo phi(mod). Use the extended euclidean algorithm to do this. You will get
d=7868405. There are python libraries that will do it for you (pycrypto Crypto.Util.number.inverse)
8765^d modulo mod. In python you want to do this using
pow takes a third argument (a modulus) which is way optimized when compared to
** followed by
%. It does the square-and-multiply method. In this case,
pow(8765, 7868405, 9691573) returns
You can check the answer by doing
pow(680457, 101, 9691573) and make sure it return
If the modulus were not prime, you'd have to factor it to compute phi(mod). After that, everything else is the same.