Modular Exponentiation

Question

I want to solve the following for \$x\$ (in Python):

\$x^{101} = 8765 \ (\mod{9691573})\$

I coded this:

n = 8765
power = 101
mod = 9691573

x = 0
while x < mod:
    if (x ** power) % mod == n:
        break
    x += 1

print x

This is basically the "brute force" approach.

What is the most efficient way to solve this problem programmatically?

Note:

solving the equation \$x^n = a \mod{M}\$ for the unknown \$x\$ in modular arithmetic means to find an integer \$x\$ such that \$x^n - a\$ is a multiple of the modulus \$M\$

Answer 1

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.

1. Factor mod, easy, mod is already prime, so it is factored.
2. Compute phi(mod). This is the euler totient function. For primes, phi(mod)=mod-1. So in your case, phi(mod)=9691572.
3. 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)
4. 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.