Thread: 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.

Thanks in advance!

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.

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)



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.