Problem E
Over the Hill, Part 1
Hill encryption (devised by mathematician Lester S. Hill in
1929) is a technique that makes use of matrices and modular
arithmetic. It is ideally used with an alphabet that has a
prime number of characters, so we’ll use the
-
Replace each character in the initial text (the plaintext) with the substitution A
, B , , (space) . If the plaintext is ATTACK AT DAWN this becomes -
Group these number into three-component vectors, padding with spaces at the end if necessary. After this step we have
-
Multiply each of these vectors by a predetermined
encryption matrix using modulo arithmetic. If the encryption matrix isthen the first vector is transformed as follows:
-
After multiplying all the vectors by the encryption matrix, convert the resulting values back to the
-character alphabet and concatenate the results to obtain the encrypted ciphertext. In our example the ciphertext is FPLSFA4SUK2W9K3.
This method can be generalized to work with any
Input
Input begins with a line containing a positive integer
Output
Output the corresponding ciphertext on a single line.
Sample Input 1 | Sample Output 1 |
---|---|
3 30 1 9 4 23 7 5 9 13 ATTACK AT DAWN |
FPLSFA4SUK2W9K3 |
Sample Input 2 | Sample Output 2 |
---|---|
6 26 11 23 14 13 16 6 7 32 4 29 29 26 19 30 10 30 11 6 28 23 5 24 23 6 24 1 27 24 20 13 9 32 18 20 18 MY HOVERCRAFT IS FULL OF EELS |
W4QVBO0NJG5 Y76H5A6XHR11BV670Z |