Search code examples
mathnumberstheorymodular

Decrypt following string

The matrix A is 7 1 4 5

0-25 represent a-z in alphabetical order. Find A inverse and hence decrypt the ciphertext fact .working modulo 26

Got this question in a test answer was supposed to be a word I got veho can anyone help?

Solution

  • The inverse of 

    A = [7 1]
    [4 5]

    computed in Z_26 (the integers modulo 26)

    is 

    A^-1 = [1   5]
       [20 17]

    This is just the formula that, if 

    A = [a b]
    [c d]

    Then

    A^-1 =      1/      *  [d -b]
        (ad - bc)      [-c a]

    To use this mod 26, you need to find the reciprocal of ad-bc = 31 = 5. This is just its multiplicative inverse, which is 21 (since 5*21 = 105 = 1 in Z_26).

    Thus A^-1 = 21 * [5 -1]  =  21 * [5 25]  = [105 525] = [1   5]
                 [-4 7]          [22 7]    [462 147]   [20 17]

    To test,

    [1   5] [7 1] = [27    26] = [1 0]   (mod 26)
[20 17] [4 5]   [208 105]    [0 1]

    It should be easy enough to use this inverse to decrypt -- just make sure to do all the arithmetic mod 26.