Results 1 to 2 of 2

Math Help - decoding

  1. #1
    Member
    Joined
    Jan 2008
    Posts
    114

    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!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Senior Member
    Joined
    Jan 2008
    From
    UK
    Posts
    484
    Thanks
    66
    Quote Originally Posted by hunkydory19 View Post
    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. 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)

    111\times73\equiv 667 (mod 676)

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

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

    Quote Originally Posted by hunkydory19 View Post
    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.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Coset Decoding
    Posted in the Number Theory Forum
    Replies: 0
    Last Post: May 25th 2010, 05:01 PM
  2. Decoding a message
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: November 9th 2009, 03:01 PM
  3. Decoding letters
    Posted in the Algebra Forum
    Replies: 1
    Last Post: October 28th 2009, 02:15 AM
  4. encoding and decoding help
    Posted in the Number Theory Forum
    Replies: 4
    Last Post: June 7th 2008, 10:44 AM
  5. Decoding bits set
    Posted in the Math Software Forum
    Replies: 0
    Last Post: December 30th 2007, 12:16 AM

Search Tags


/mathhelpforum @mathhelpforum