역행렬
본문알파벳을 A = 0, B = 1, ⋯, Z = 25로 바꾸고, 두 글자씩 묶어 열벡터로 만든 뒤 행렬 \(K = \begin{pmatrix}3 & 3\\ 2 & 5\end{pmatrix}\)를 곱하고 26으로 나눈 나머지를 취해 암호문을 만든다. 이 방법으로 "HI"를 잠그면 "TC"가 된다. 암호문을 받은 친구가 원래 글자를 되찾으려면 \(K\)가 한 일을 되돌리는 행렬이 필요하다. 그런 행렬은 어떻게 구하고, 어떤 행렬이면 열쇠를 만들 수 없을까?
2.2.1곱한 것을 되돌리는 행렬
정사각행렬 \(A\)에 대해 \(AX = XA = I\)인 행렬 \(X\)가 있으면 \(X\)를 \(A\)의 역행렬이라 하고 \(A^{-1}\)로 쓴다. \(A\vec x = \vec b\)에서 양변에 \(A^{-1}\)을 곱하면 \(\vec x = A^{-1}\vec b\)이므로, 역행렬은 \(A\)가 한 일을 되돌린다. 역행렬은 가우스 소거법으로 구할 수 있다. \(A\)와 단위행렬 \(I\)를 나란히 놓은 \((A \mid I)\)에 행 연산을 해서 왼쪽을 \(I\)로 만들면, 오른쪽이 \(A^{-1}\)이 된다. 왼쪽을 \(I\)로 만들 수 없으면 역행렬이 없다.
\(A = \begin{pmatrix}a & b\\ c & d\end{pmatrix}\)이고 \(ad - bc \ne 0\)이면 \[A^{-1} = \frac{1}{ad - bc}\begin{pmatrix}d & -b\\ -c & a\end{pmatrix}\]이다. \(ad - bc = 0\)이면 역행렬이 없다. \(n\times n\) 행렬 \(A\)가 역행렬을 가질 필요충분조건은 열벡터들이 일차독립인 것이다.
역행렬이 없는 행렬은 서로 다른 두 벡터를 같은 벡터로 보낸다. 예를 들어 \(\begin{pmatrix}1 & 2\\ 2 & 4\end{pmatrix}\)은 두 열이 실수배여서 평면 전체를 한 직선으로 납작하게 누른다. 납작해진 직선 위의 한 점으로 간 벡터들이 무수히 많으므로, 어느 것이 원래 벡터였는지 되찾을 수 없다. 그래서 역행렬이 있는지는 열벡터가 일차독립인지, 행렬식이 0이 아닌지로 계산하기 전에 알 수 있다.1
2.2.2나머지 세계의 역행렬
암호에서는 26으로 나눈 나머지만 다루므로 분수를 쓸 수 없다. 그래서 \(\dfrac{1}{ad - bc}\) 대신 \((ad - bc)\times k\)를 26으로 나눈 나머지가 1이 되는 수 \(k\)를 곱한다. \(K\)의 행렬식은 \(3\times5 - 3\times2 = 9\)이고, \(9\times3 = 27\)을 26으로 나눈 나머지가 1이므로 \(k = 3\)이다. 행렬식이 26과 공약수를 가지면, 곧 짝수이거나 13의 배수이면 그런 \(k\)가 없어서 열쇠 행렬을 만들 수 없다. 그래서 힐 암호의 열쇠는 행렬식이 26과 서로소인 행렬로 골라야 한다.
2.2.3예제 풀이
처음 질문의 열쇠 \(K\)로 "HI"를 잠가 암호문을 구하고, 26으로 나눈 나머지 세계의 역행렬로 다시 열어 보아라. 또 \(\begin{pmatrix}2 & 1\\ 4 & 3\end{pmatrix}\)은 열쇠로 쓸 수 있는가?
\(K\begin{pmatrix}7\\ 8\end{pmatrix} = \begin{pmatrix}45\\ 54\end{pmatrix}\)이고, 26으로 나눈 나머지는 \((19, 2)\), 곧 "TC"이다. 역행렬은 \(3\begin{pmatrix}5 & -3\\ -2 & 3\end{pmatrix} = \begin{pmatrix}15 & -9\\ -6 & 9\end{pmatrix}\)이고, 음수를 26을 더해 바꾸면 \(\begin{pmatrix}15 & 17\\ 20 & 9\end{pmatrix}\)이다.
\(\begin{pmatrix}15 & 17\\ 20 & 9\end{pmatrix}\begin{pmatrix}19\\ 2\end{pmatrix} = \begin{pmatrix}319\\ 398\end{pmatrix}\)이고, 26으로 나눈 나머지는 \((7, 8)\), 곧 "HI"로 되돌아온다. \(\begin{pmatrix}2 & 1\\ 4 & 3\end{pmatrix}\)은 행렬식이 \(6 - 4 = 2\)로 짝수여서 26과 공약수 2를 가지므로, 나머지 세계에서 역행렬이 없어 열쇠로 쓸 수 없다. 실제로 이 행렬은 서로 다른 글자 묶음을 같은 암호문으로 보내기도 한다. 즉 역행렬은 행렬을 곱한 일을 되돌리는 행렬이며, 행렬식이 0이 아닐 때, 나머지 세계에서는 행렬식이 법과 서로소일 때만 존재한다.
아래 탐구 카드에서 역행렬이 있는지 계산하기 전에 판단해 보고, 행렬로 잠근 암호를 역행렬로 풀어 보자.
- 이 암호는 1929년 미국의 수학자 힐이 발표했다. 한 글자씩이 아니라 여러 글자를 한꺼번에 섞어 글자의 빈도로 깨뜨리기 어려웠지만, 원문과 암호문 몇 쌍이 알려지면 연립방정식으로 열쇠를 거꾸로 구할 수 있어 오늘날에는 쓰이지 않는다.
역행렬 \(A^{-1}\)은 \(AA^{-1} = A^{-1}A = I\)인 행렬로 \(A\)가 한 일을 되돌리며, \((A \mid I)\)를 가우스 소거법으로 \((I \mid A^{-1})\)로 바꾸어 구한다. \(2\times2\) 행렬은 \(ad - bc \ne 0\)일 때만 역행렬이 있고, 열벡터가 일차종속이면 평면을 납작하게 눌러 되돌릴 수 없다. 처음 질문의 열쇠 \(K\)는 행렬식 9가 26과 서로소여서 나머지 세계의 역행렬 \(\begin{pmatrix}15 & 17\\ 20 & 9\end{pmatrix}\)로 "TC"를 "HI"로 연다.