10
\$\begingroup\$

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\$

\$\endgroup\$
  • \$\begingroup\$ This is the RSA problem with e=101 and n=9691573. Factor the modulus n, compute phi(n). Compute d such that e * d = 1 mod phi(n) using extended euclidean. Compute 8765^d mod n using square-and multiply. Read the wikipedia article on RSA for details. \$\endgroup\$ – CodesInChaos Oct 13 '14 at 9:55
  • 3
    \$\begingroup\$ @CodesInChaos I'd say this qualifies as an answer instead if a comment. \$\endgroup\$ – agtoever Oct 17 '14 at 14:29
  • \$\begingroup\$ @CodesInChaos note that the modulus is prime. \$\endgroup\$ – mikeazo Oct 20 '14 at 11:49
  • \$\begingroup\$ Is this really a code review question? It technically contains a working piece of code, but to efficiently compute this you will need to write completely different code. I think this would be a better fit of stackoverflow. \$\endgroup\$ – CodesInChaos Oct 20 '14 at 12:35
  • \$\begingroup\$ @CodesInChaos I disagree whole heartedly. This is a great fit for Code Review. (8 other people seem to agree with me about that.) We often deal with performance issues. Suggesting alternative algorithms is commonplace here. \$\endgroup\$ – RubberDuck Oct 20 '14 at 21:20
3
\$\begingroup\$

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.