1. ## decoding

In a cryptosystem we use the ordinary alphabet numbered 0 to 25. We number digraphs using enumeration to base 26. We encode digraphs using the affine transformation

f(x) = 213x + 111(mod 676)

What is the decoding transformation?

Let y = 213x + 111(mod 676)
Then y = 213x = y - 111(mod 676)
We need to find the inverse of 213 modulo 676
Using Euclid's algorithm we have 9 x (-3) = 1 mod 676
Hence we multiply both sides of 213x = y - 111(mod 676) by (-3) to obtain:
x = -3(y - 111)(mod 676)
Hence x = -3y + 333 mod 676
Since -3 equiv 73(mod 676)

We have decoding transformation g(x) = 73x + 333 mod 676

Can anyone please explain explain where I have gone wrong here, as i know the answer should be g(x) = 73x + 9 mod 676.

2. Originally Posted by hunkydory19
Using Euclid's algorithm we have 9 x (-3) = 1 mod 676
How did you get this?

I ended up with 213x73-23x676=1 at the end of Euclid's algorithm so 73 is fine. $\displaystyle 213\times73\equiv 1 (mod) 676$

Once you've got the inverse for 213 it's quite easy to finish off.

Just try it out with an easy number, say 0.

y=213x0+111 (mod 676)
y=111

Then to decode 111x73+A=0 (mod 676)

$\displaystyle 111\times73\equiv 667 (mod 676)$

$\displaystyle 667+A\equiv 0 (mod 676)$ and you can see A=9 works fine.

A "practical" method. Is it OK for you?

Originally Posted by hunkydory19
Can anyone please explain explain where I have gone wrong here, as i know the answer should be g(x) = 73x + 9 mod 676.
I can't explain where you went wrong as I'm afraid I don't understand your working. I don't think you posted enough of it.

By the way, this is the first number theory I've done in ......8 years. Hope it's OK.