Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question

2 Answers 2

up vote 2 down vote accepted

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}. $$

share|improve this answer
    
Thank you! (15 chars) –  zneak May 26 '11 at 17:15

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?

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.