Find the decoding formula for the encoding formula $y=9x+10$ and use it to decode "KOMF"
Please give me a clear explanation and step by step solutions. Thank you.
Asked
Active
Viewed 6,733 times
0
-
1Hint: Can you come up with an additive inverse for $10$ and a multiplicative inverse for $9$, both modulo $26$? – MPW Feb 11 '14 at 05:12
2 Answers
1
I think you're asking for the inverse of the function $$f(n) = 9 n + 10 \mod 26$$ While you can write it explicitly, I think it would be a bit of a piecewise mess. Since this is on such a small finite domain it may be easier to just compute it all and invert "by hand." To wit:
{0, 22}, {1, 25}, {2, 2}, {3, 5}, {4, 8}, {5, 11}, {6, 14}, {7, 17},
{8, 20}, {9, 23}, {10, 0}, {11, 3}, {12, 6}, {13, 9}, {14, 12}, {15, 15},
{16, 18}, {17, 21}, {18, 24}, {19, 1}, {20, 4}, {21, 7}, {22, 10},
{23, 13}, {24, 16}, {25, 19}
Assuming
KOMF = 11, 15, 13, 6
we get
3, 15, 9, 14 = COIN
Edit: Here's a general technique $$ n = 9f^{-1}(n) + 10 \Rightarrow f^{-1}(n) = ( n - 10 ) \cdot 9^{-1}$$ Where by $9^{-1}$ I mean a multiplicative inverse of $9$ mod $26$ i.e. some $n$ with the property that $9 \cdot n = 1 \mod 26$.
That is we must have $9 n = 1 + 26 m$ for some integer $m$. In general use your favorite method to solve this diophantine equation (note, in general there need not be a solution: what if 9, 26 had not been coprime?). In this case though, it's easy to see that we have a solution where $m =1$ and $n = 3$.
Pull it all together: $$f^{-1}(n) = 3(n -10) = 3n +22$$
Frederick
- 272
-
Of course looking at my computation I now see that there is an obvious closed form for the inverse. Can you find it? – Frederick Feb 11 '14 at 05:15
-
Can you give me a different way of solving it? What if it's a bigger number? Sort of a step by step process. Thank you – user127543 Feb 12 '14 at 00:54
-
0
This is based on the Modular Systems lesson from my Math class and this is what I've picked up from it so my apologies if it's quite juvenile.
Your equation is basically:
$y=9x+10 (\mod 26)$ because you're trying to decode, which would mean that you'll be looking at the set of letters a.k.a. the alphabet, which has 26 letters (26 elements)
$$x (\mod26) \cdot 9 = 1 \implies x=3 $$
Multiply $3$ with the original equation $(\mod 26)$. This gives us:
$$3y=x+4,$$
for a final decoding equation: $$x=3y+22.$$
Substitute the values as you would in coding. The given values would be the $Y$ values (KOMF) and you'll be solving for the $X$ values
K O M F
Y: $11 \space \space 15 \space \space 13 \space \space 6$
X: $3 \space \space \space 15 \space \space \space 9 \space \space \space 14$
KOMF = COIN
