In classical cryptography, the Hill cipher is a polygraphic substitution cipher based on linear algebra. Invented by Lester S. Hill in 1929, it was the first polygraphic cipher in which it was practical (though barely) to operate on more than three symbols at once. The following discussion assumes an elementary knowledge of matrices. Encryption Each letter is represented by a number modulo 26. Though this is not an essential feature of the cipher, this simple scheme is often used: To encrypt a message, each block of n letters (considered as an n-component vector) is multiplied by an invertible n × n matrix, against modulus 26. To decrypt the message, each block is multiplied by the inverse of the matrix used for encryption. The matrix used for encryption is the cipher key, and it should be chosen randomly from the set of invertible n × n matrices (modulo 26). The cipher can, of course, be adapted to an alphabet with any number of letters; all arithmetic just needs to be done modulo the number of letters instead of modulo 26. Consider the message 'ACT', and the key below (or GYBNQKURP in letters): Since 'A' is 0, 'C' is 2 and 'T' is 19, the message is the vector: Thus the enciphered vector is given by: which corresponds to a ciphertext of 'POH'. Now, suppose that our message is instead 'CAT', or: This time, the enciphered vector is given by: which corresponds to a ciphertext of 'FIN'. Every letter has changed. The Hill cipher has achieved Shannon's diffusion, and an n-dimensional Hill cipher can diffuse fully across n symbols at once. Decryption In order to decrypt, we turn the ciphertext back into a vector, then simply multiply by the inverse matrix of the key matrix (IFKVIVVMI in letters). We find that, modulo 26, the inverse of the matrix used in the previous example is: Taking the previous example ciphertext of 'POH', we get: which gets us back to 'ACT', as expected. Two complications exist in picking the encrypting matrix: Not all matrices have an inverse. The matrix will have an inverse if and only if its determinant is not zero. The determinant of the encrypting matrix must not have any common factors with the modular base. Thus, if we work modulo 26 as above, the determinant must be nonzero, and must not be divisible by 2 or 13. If the determinant is