3
$\begingroup$

In my discrete maths homework, I'm being asked to find the inverse of a cipher function:

$f(p) = (3p + 5) \bmod{26}$

$f(p)$ accepts natural integers of the range ${0,1,...,25}$ (where A = $0$ and Z = $25$) and outputs in the same range.

Messing around for a lot of time, I ended up finding this function:

$f^{-1}(p) = \Big(\frac{p + 26(p \bmod{3})}{3} + 7\Big) \bmod{26}$

But it was obtained almost exclusively with the help of trial and error and C program I made to help me investigate, and that's not quite suitable to write on my copy.

First, is my function the best function that solves this problem? And second, how should I have found this the 'right' way?

2 Answers 2

2

You can solve it much like you would normally. "Normally," you would like that $f^{-1}(p)=\frac{p-5}{3}$. What this means modulo $26$ is $f^{-1}(p)=\bar{3}(p-5)$, where $\bar{3}$ is the inverse of $3$ modulo $26$. But notice that $\bar{3}=9$, since $3\cdot 9\equiv 1\pmod{26}$. So $ f^{-1}(p)=9(p-5)\equiv 9p-45\equiv 9p+7\pmod{26}. $

2

How would you invert if it were an ordinary equation? You'd go $x=3p+5$, $3p=x-5$, $p=3^{-1}(x-5)$, and report your answer as $f^{-1}(x)=3^{-1}(x-5)$. Well, it's the same with congruences as with equations, once you understand what $3^{-1}$ means in the context of calculations modulo 26. Do you?