Finding the inversion of an easier function is simple. The way I find the way of doing this by flipping the x and the y in the equation and solving for y. But I am stuck on a certain part.
y = (6*x) mod 13
x = (6*y) mod 13
To compute the inverse of y = 6 * x mod 13, I am first going to solve for x and replace x with y (and vice versa) later.
Since y = 6 * x mod 13, x = 6^(-1) * y mod 13, where 6^(-1) is the modular multiplicative inverse of 6 for the modulus 13. Your task now becomes finding 6^(-1) mod 13. In other words, you have to find m such that 6 * m = 1 mod 13.
Note that 6 * 2 = 12 = -1 mod 13. Squaring both sides, 6 * 6 * 2 * 2 = 1 mod 13, or 6 * 24 = 1 mod 13. Since 24 = 11 mod 13, therefore 6 * 11 = 1 mod 13 and 11 = 6^(-1) mod 13.
Thus, our equation for x now becomes x = 11 * y mod 13. Replacing y -> x and x -> y, the inverse of the given function is given by y = 11 * x mod 13.
This nifty Python script can be used to test the validity of our result:
def f(x):
return (6 * x) % 13
def f_inv(x):
return (11 * x) % 13
for x in range(13):
print x, f_inv(f(x)), x == f_inv(f(x))
When run, it gives the following output:
0 0 True
1 1 True
2 2 True
3 3 True
4 4 True
5 5 True
6 6 True
7 7 True
8 8 True
9 9 True
10 10 True
11 11 True
12 12 True
Thus validating the premise that f^(-1)(x) = 11 * x mod 13 satisfies the required premise that f^(-1)(f(x)) = x.