How find a variable value in MOD expression?

Question

9 = 2^X mod 11

What is X and how do you find X?

Its related to finding the plain text in RSA algorithm and I'm writing a C program for it.

Answer 1

The answer is 6 + 10i for any integer i.

A simple way to get solutions for small moduli is to iterate over all values of x. You only need to check between 0 and 10 (= 11 - 1) to find the first solution, if any solution exists.

x = 0
while x < 50:
    if 9 == 2**x % 11:
         print x
    x += 1

Output:

6
16
26
36
46

Obviously this will take a long time if the modulus is large.

More information is on the Discrete Logarithm page. Note:

No efficient classical algorithm for computing general discrete logarithms logbg is known. The naive algorithm is to raise b to higher and higher powers k until the desired g is found; this is sometimes called trial multiplication. This algorithm requires running time linear in the size of the group G and thus exponential in the number of digits in the size of the group.

If it were easy to invert modular exponetiation, it wouldn't be a good cryptographic primitive.