Problem D
A Matrix Decipher
Input File: pd.in
Let Z_{N} = {0, 1, 2, …, N2, N1}, 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 ddimensional 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_{1}]
[x_{2}]
[x_{3}]
見二
[h_{11} h_{12} h_{13}]
[h_{21} h_{22} h_{23}]
[h_{31} h_{32} h_{33}]
見三
[1 1 1]
[1 2 2]
[1 2 3]
見四
[2 10 0]
[10 2 10]
[0 10 1]
The first line of the input file always contains one integer indicating the number of test cases to come. Each of the test cases consists of d+2 lines with d = 2 or d = 3 in the first line indicating the dimension of the encipher matrix H followed by d lines of the entries of H row by row, the (d+2)th line is the input message of 12 characters.
The output format is similar to the input format. The first line of the ouput file contains one integer indicating the number of test cases. Each of the test cases consists of d+2 lines with d = 2 or d = 3 in the first line indicating the dimension of the decipher matrix H^{1}, the next d lines are the entries of H^{1} row by row, and the (d+2)th line is the decrypted message of 12 characters.
2 2 2 1 3 2 6:19278694:2 3 1 1 1 1 2 2 1 2 3 26242669:976
2 2 10 8 2 224488::3377 2 10 0 10 2 10 0 10 1 9876543210::
ID  User  Problem  Subject  Hit  Post Date 
沒有發現任何「解題報告」
