Problem D

A Matrix Decipher

Input File: pd.in

        Let Z_N = {0, 1, 2, …, N-2, N-1}, where N is a positive integer. An integer linear transformation under (mod N) can be defined as

        f(x) = Hx, where x ∈ Z^d_N, and H ∈ Z_N^d*d

That is, x is a d-dimensional column vector and H is a d by d matrix whose elements are from Z_N.

          For d = 3, we have f([見1]) = [見2]*[ 見1] = H[見1], where h_ij ∈Z_N, 1 <= i,j <= 3. The inverse integer transformation exists only if gcd(det(H), N) = 1, that is, the determinant of matrix H is relatively prime to N. This problem assumes that N = 11.

          Let Ω = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, :} be the set of 11 characters represented as numbers 0,1, …, 10, respectively. A matrix encipher takes a message, a character string consisting of 12 characters from Ω = {0, 1, 2, …, 8, 9, :}, as input and ouputs an enciphered message of the same length based on applying an integer linear transformation successively on the d characters in each group from the input message string. For example, for d = 3, a message “9870::”, decomposed as two groups of 3 characters, “987” and “0::”, is enciphered as “262976” based on the transformation matrix H = [見3]. The corresponding decipher takes “262976” as input associated with the integer transformation matrix H^-1 = [見4] which converts “262976” back to “9870::”. This problem asks you to design a matrix decipher H^-1 based on a given matrix encipher H to decrypt an enciphered message.

見一

[x₁]
[x₂]
[x₃]

見二

[h₁₁ h₁₂ h₁₃]
[h₂₁ h₂₂ h₂₃]
[h₃₁ h₃₂ h₃₃]

見三
[1 1 1]
[1 2 2]
[1 2 3]

見四

[2 10 0]
[10 2 10]
[0 10 1]