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.
- Factor
mod
, easy, mod
is already prime, so it is factored.
- Compute
phi(mod)
. This is the euler totient function. For primes, phi(mod)=mod-1
. So in your case, phi(mod)=9691572
.
- Compute
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)
- Compute
8765^d modulo mod
. In python you want to do this using pow
. 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 680457
.
You can check the answer by doing pow(680457, 101, 9691573)
and make sure it return 8765
.
If the modulus were not prime, you'd have to factor it to compute phi(mod). After that, everything else is the same.
n
, computephi(n)
. Computed
such thate * d = 1 mod phi(n)
using extended euclidean. Compute8765^d mod n
using square-and multiply. Read the wikipedia article on RSA for details. \$\endgroup\$ – CodesInChaos Oct 13 '14 at 9:55