Editing Hill cipher (section)

==Decryption==
In order to decrypt, we turn the ciphertext back into a vector, then simply multiply by the [[matrix inversion|inverse matrix]] of the key matrix (IFK{{silver (color)|/}}VIV{{silver (color)|/}}VMI in letters). We find that, [[modular arithmetic|modulo]] 26, the inverse of the matrix used in the previous example is:
:<math>\begin{pmatrix} 6 & 24 & 1 \\ 13 & 16 & 10 \\ 20 & 17 & 15 \end{pmatrix}^{-1} \pmod{26}\equiv \begin{pmatrix} 8 & 5 & 10 \\ 21 & 8 & 21 \\ 21 & 12 & 8 \end{pmatrix} </math>
Taking the previous example ciphertext of 'POH', we get:
:<math>\begin{pmatrix} 8 & 5 & 10 \\ 21 & 8 & 21 \\ 21 & 12 & 8 \end{pmatrix} \begin{pmatrix} 15 \\ 14 \\ 7 \end{pmatrix} = \begin{pmatrix} 260 \\ 574 \\ 539 \end{pmatrix} \equiv \begin{pmatrix} 0 \\ 2 \\ 19 \end{pmatrix} \pmod{26}</math>
which gets us back to 'ACT', as expected.

One complication exists in picking the encrypting matrix:
# Not all matrices have an [[invertible matrix|inverse]]. The matrix will have an inverse if and only if its [[determinant]] is inversible modulo n, where n is 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 0, or has common factors with the modular base, then the matrix cannot be used in the Hill cipher, and another matrix must be chosen (otherwise it will not be possible to decrypt). Fortunately, matrices which satisfy the conditions to be used in the Hill cipher are fairly common.

For our example key matrix:
:<math>\begin{vmatrix} 6 & 24& 1 \\ 13 & 16 & 10 \\ 20 & 17 & 15 \end{vmatrix} = 6(16\cdot15-10\cdot17)-24(13\cdot15-10\cdot20)+1(13\cdot17-16\cdot20) = 441 \equiv 25 \pmod{26}</math>
So, modulo 26, the determinant is 25. Since <math>25=5^2</math> and <math>26=2 \times 13</math>, 25 has no common factors with 26, and this matrix can be used for the Hill cipher.

The risk of the determinant having common factors with the modulus can be eliminated by making the modulus [[prime number|prime]]. Consequently, a useful variant of the Hill cipher adds 3 extra symbols (such as a space, a period and a question mark) to increase the modulus to 29.