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

I think that can be solved using modular arithmetic. Another way is calculating 9=2^X in F₁₁ (Z/11Z), but that's part of modular arithmetic, too.

Another solution (where you'll find only ONE solution) is to solve the equation numerically, that's probably easier in a C program.

Answer 2

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.

Answer 3

Obviously, sequence of 2^n mod 11 will be cyclical.

2^0 mod 11 = 1
2^1 mod 11 = 2
2^2 mod 11 = 4
2^3 mod 11 = 8
2^4 mod 11 = 5
2^5 mod 11 = 10
2^6 mod 11 = 9
2^7 mod 11 = 7
2^8 mod 11 = 3
2^9 mod 11 = 6
2^10 mod 11 = 1
2^11 mod 11 = 2

So, cycle length is 10.

2^n mod 11 = 9 for n=6+10*m where m is integer