선형대수와 군(이인석)의 표지에 대하여

선형대수학 책을 추천해달라는 요청에 많은 사람들이 Friedberg-Insel-Spence > 이인석 > Hoffman-Kunze 순으로 추천해주는 듯 하다. 그 중에 선형대수와 군(이인석)은 한국어로 된 데다가 내용이 다른 책들에 비해 꿇리지도 않고, 수준도 어느정도 있어 많은 사람들이 좋아하는 것으로 보인다.

선형대수와 군 책 표지를 보면 웬 숫자들이 배열되어 있고 색이 칠해져 있는 것을 볼 수 있다. 많은 사람들이 어련히 다 뜻이 있겠거니, 아니면 예쁘도록 아무렇게나 대충 잘 배치해놨겠거니, 하면서 별 신경을 쓰고 있지는 않는 것 같다. 하지만 저자의 말에 따르면 표지 디자인 또한 연습문제로써 만들어 놓았다는 것 같다. (오오...)

여기에 다시 쓰자면, 표지에 있는 숫자들은 가로로 열 칸씩 숫자 하나를 나타내며, 맨 왼쪽 위에 있는 \( x_1 = 1015568748 \) 부터 시작해서 어떤 정수 \(a\), \(b\), \(N\)에 대하여 점화식

$$ x_{n+1} \equiv a x_n + b \mod N $$

을 이용해서 \( \{x_i\}_{i \in \mathbb{N}} \)을 구한 뒤 다섯 개씩 가로로 쭉 나열한 것이라고 한다. 이 때, 각각이 열 자리 숫자가 되게 하기 위해서 각 숫자의 앞에 필요한 경우 빈 자리를 채우기 위해 0을 집어넣었다고 한다. 즉, \( x_2 = 1586005467 \)이고 \( x_3 = 2165703038 \) 이며, 그렇게 세어 스물한 번째에는 \(0927463856\)이라고 써있으므로 \(x_{21} = 927463856 \)이 되는 것이다. 이렇게 유사 난수열을 생성하는 방법을 선형 합동 생성기(Linear Congruential Generator)이라고 부른다고 한다. 연습문제는 \(a\), \(b\), \(N\)을 구하라는 것이다.

어떻게 구하면 좋을까? 일단 어떻게 해서 \(N\)을 구했다고 해보자. 그렇다면 우리는 이미 모든 \( n \)에 대해 \( x_n\)와 \(x_{n+1}\)  사이의 관계식을 알고 있으므로, 적당한 \(i\), \(j\)를 골라서 \(a\), \(b\)에 대한 연립선형합동식

$$ \begin{cases} x_i \ a + b &=& x_{i+1} \\ x_j \ a + b &=& x_{j+1} \end{cases} $$

를 풀면 된다. 즉, 선형대수와 군이라는 책 제목에 맞도록 선형대수학의 향기를 한껏 끌어올리자면, Hoffman-Kunze가 그렇게 좋아하는 commutative ring with identity \(\mathbb{Z} / N\mathbb{Z}\) 위에서 다음 문제를 푸는 것으로 바뀐다.

$$ \begin{pmatrix} x_i & 1 \\ x_j & 1 \end{pmatrix} \begin{pmatrix} a \\ b \end{pmatrix} = \begin{pmatrix} x_{i+1} \\ x_{j+1} \end{pmatrix}$$

이 방정식의 해가 유일한가? 당연히, 

$$ \det \begin{pmatrix} x_i & 1 \\ x_j & 1 \end{pmatrix} = x_i - x_j $$

이 \(\mathbb{Z} / N\mathbb{Z}\)에서 invertible이면 해가 유일하게 결정될 것이다. 만약에 invertible이 아니라면... 해가 유일하게 결정되지 않는다. 이것을 곰곰히 다시 잘 생각해보면, \(\mathbb{Z} / N\mathbb{Z} \times \mathbb{Z} / N\mathbb{Z}\) 에서는 두 점을 지나는 "직선"이 유일하지 않을 수도 있다는 뜻이다...! (사실 당연한 이야기이다.  \(\mathbb{Z} / N\mathbb{Z} \times \mathbb{Z} / N\mathbb{Z} \) 가 torus \( \mathbb{R} / N\mathbb{Z} \times \mathbb{R} / N\mathbb{Z} \) 위의 '격자점'이 된다는 것에 주목하자. 토러스 위의 두 점을 잇는 '직선'은 torus를 몇 번 감아 도는 직선이냐에 따라 수없이 많다는 것에 미루어 보아, 유일하게 결정된다는 것이 오히려 특이한 경우라고도 할 수 있을 것이다.) 그렇다면 \(a\), \(b\)를 결정하기 위해서 어떻게 해야 할까? \(x_i - x_j\)가  \(\mathbb{Z} / N\mathbb{Z}\)에서 invertible하게 되는 \(i\), \(j\)를 찾거나, 아니면 여러 개의 \(i\), \(j\)에 대해 해집합을 구해서 교집합에 들어가는 \(a\), \(b\)를 구할 수밖에 없을 것이다(torus에서 두 점만 가지고 직선을 결정하는 것 보다, 한 점을 더 골라 세 점을 지나는 직선을 찾으면 가능한 직선의 후보가 줄어드는 것으로 생각해보자). 결론은, \(N\)을 안다면 간단한 계산문제가 된다는 것이다. (물론, 그 계산을 여러 번 해야 될 수도 있겠지만.)

그럼 \(N\)은 어떻게 구할까? 저자의 말에 'GCD attack'이라는 공략법을 이름만 소개하고 있다. 찾아보니 GCD attack은 다음과 같이 진행되는 것 같다. 

먼저 점화식을 이용해서 일반항을 구해보자. \(\equiv\)이나 \(\text{mod }N\)을 계속 쓰기는 귀찮으니까, 이 문단에서는 모든 논의가 \(\mathbb{Z} / N\mathbb{Z}\)에서 이루어진다고 하자 (물론 index는 예외로 하자...). 일단 \(x_2 = a x_1 + b\)이다. 따라서 \(x_3 = ax_2 + b = a^2 x_1 + ab + b\)이고, \(x_4 = ax_3 + b = a^3 x_1 + a^2 b + ab + b\)이고, ···. 따라서 

$$ x_n = a^{n-1} x_1+ \dfrac{a^{n-1}-1}{a-1} b $$

을 얻는다. 엄밀하게 보이고 싶다면 귀납법을 쓰면 되겠다. 이제, \(y_n = x_{n+1} - x_{n}\)으로 새로운 수열을 하나 정의하자. 앞에서 구한 일반항을 이용하면 

$$ y_n = (a^n - a^{n-1})x_1 + a^{n-1} b $$

인데, (\(n \ge 2\)라 가정하고) 우변을 공통인수 \(a\)로 묶어주면 \(y_n = a y_{n-1}\)이 성립하는 것을 알 수 있다. 따라서 \(\{ y_n\} _ {n \in \mathbb{N}} \)은 "등비수열"이 되고, \( y_{n+1} y_{n-1} - y_n^2 = 0\)이 성립하게 된다. 그런데 우리가 \(\mathbb{Z} / N\mathbb{Z}\) 위에서 생각하고 있다는 것을 떠올려보면, 우리는 사실 (다시 \(\mathbb{Z} / N\mathbb{Z}\)에서 \(\mathbb{Z}\)으로 논의의 대상을 바꿔서) 

$$ y_{n+1} y_{n-1} - y_n^2 \equiv 0 \mod N $$

임을 보인 것이다. 편의상 \(z_n = y_{n+2}y_{n} - y_{n+1}^2\)으로 두면, 모든 \(n \in \mathbb{N}\)에 대해 \(z_n\)이 \(N\)의 배수가 된다는 뜻이다. 그렇다면 \(N\)은 \(z_1\), \(z_2\), \(z_3\), \(\cdots\)의 공약수일 것이고, 따라서 \(N\)은 어떤 자연수 \(k\)에 대해서든 \(\text{gcd} (z_1, z_2, \cdots, z_k)\)의 약수일 것이다. 이렇게 \(N\)에 대해 아무것도 모르는 상태에서 여기까지 \(N\)이 될 수 있는 후보를 많이 압축하는 데에 성공했다. 좀 더 후보를 줄일 수는 없을까?

역시나 저자의 말에 써있는 대로, \(\{x_n\}_{n \in \mathbb{N}}\)이 유사 난수 생성기로 생성된 적당-한 난수라는 것을 받아들이면, \(\{z_n\}_{n \in \mathbb{N}}\)도 대-충 적당-한 난수열이라고 할 수 있을 것이다. 이를 받아들이고, 어떨 때 \(N = \text{gcd} (z_1, z_2, \cdots, z_k)\)이 성립할 수 있을 지 생각해보자. 일단 각 \(z_n\)이 \(N\)의 배수임을 알고 있으므로, 어떨 때 

$$1 = \text{gcd} (z_1 /N, z_2 /N, \cdots, z_k /N) $$

이 성립하는 지를 알아보면 충분하다. 그런데, \( \{ 1,2,\cdots, n\}\)에서 \( k\)개의 숫자를 임의로 뽑았을 때 최대공약수가 \(1\)일 확률이 \(n \to \infty\)일 때 \(1/\zeta(k)\)에 수렴한다는 것은 잘 알려진 사실이다. 이 때 \( \lim_{k \to \infty} 1/\zeta(k) = 1\)이기 때문에, \(k\)가 충분이 커지면 \(N = \text{gcd} (z_1, z_2, \cdots, z_k)\)일 확률이 \(1\)에 수렴하게 된다. \(N\)이 충분히 커서 \(N \to \infty\)인 경우라고 생각해도 된다고 하면, \(k=2\)일 때 \( N = \text{gcd}(z_1, z_2)\)일 확률은 \(1/\zeta(2) \approx 60.8 \%\) 이고, \( k = 7\)이면 \( N = \text{gcd}(z_1, z_2, \cdots, z_7)\)일 확률은 무려 \(1/\zeta(7) \approx 99.1 \%\)이 된다. \(\{z_n\}_{n \in \mathbb{N}}\)을 어떻게 구성했는 지를 떠올려보면, \(x_1\)부터 \(x_5\)까지를 이용하면 \(z_1\)과 \(z_2\)를 구할 수 있고, \(x_{10}\)까지를 이용하면 \(z_7\)까지 구할 수 있음을 알 수 있다. 저자의 말에 의하면 \(x_1\)부터 \(x_5\)까지만을 이용하면 '모범답안'을 구할 수 있다고 했지만, 이를 모르는 상태에서 \(x_1\)부터 \(x_5\)까지만을 이용해서 \(N\)을 구하면 그 구한 값이 실제로 \(N\)이 될 확률은 \(60 \%\)를 약간 넘을 뿐이다. 개인적으로는 \(x_1\)부터 \(x_{10}\)까지를 이용해서 구한 값은 정답일 확률이 \(99\%\)을 넘으니 \(N\)이라고 믿어도 좋을 듯 하다. 

실제로 이 방식을 이용해서 \(k = 10\)일 때 \(N\)을 구해보면 (정확히는 예상해보면) \(N = 4294967296 = 2^{32}\)을 얻는다. 저자의 말대로, \(k = 2\)일 때도 이 값을 얻을 수 있기는 하다. \(N\)을 알았으니 이제 \(a\), \(b\)를 구해보자. 먼저, \(i = 1\), \(j = 2\)를 이용하면 \(a\), \(b\)가 유일하게 결정되는 지 살펴보자. 일단 \(x_1 - x_2\)는 홀수이다. 여기서 잠시 생각해보자. \(m \in \mathbb{Z}/N\mathbb{Z}\)이 invertible한 것은 어떤 경우일까? 어떤 \(X\)가 존재하여 

$$mX \equiv 1 \mod N$$

인 경우일 것이다. 즉, 또 어떤 \(Y\)가 존재하여 \(mX+NY=1\)이 성립하는 경우이다. 그런데 이것은 기초정수론에서 배우듯 \(\gcd(m, N) = 1\)이라는 뜻이다. 게다가 extended Euclidean algorithm을 이용하여 \(X, Y\)를 구하는 것까지 기초정수론에서 배운다. 우리의 문제에 적용하면, 아까 \(x_1 - x_2\)는 홀수인데  \(N = 2^{32}\)였으므로 \(\gcd(x_1 - x_2, N) = 1\)이고, 따라서 \(x_1 - x_2\)는 invertible하다. \(i = 1\), \(j = 2\)는 \(a\), \(b\)를 유일하게 결정할 수 있게 해줄 좋은 선택이었던 것이다. 이제 \(a\), \(b\)를 구하는 것은 순전히 계산문제이다. 다음과 같이 계산하면 된다. (다시 한번, 우리는 \(\mathbb{Z}/N\mathbb{Z}\) 위에서의 선형대수를 하고 있다는 것을 상기하자...)

$$ \begin{array}{rcl} \begin{pmatrix} a \\ b \end{pmatrix} &=& \begin{pmatrix} x_1 & 1 \\ x_2 & 1 \end{pmatrix} ^{-1} \begin{pmatrix} x_2 \\ x_3 \end{pmatrix} \\ &=& (x_1 - x_2)^{-1} \begin{pmatrix} 1 & -1 \\ -x_2 & x_1 \end{pmatrix} \begin{pmatrix} x_2 \\ x_3 \end{pmatrix} \\ &=& \cdots \\ &=& \begin{pmatrix} 1664525 \\ 1013904223 \end{pmatrix}. \end{array}$$

따라서 선형대수와 군의 표지 디자인은 \( x_1 = 1015568748 \)에서 시작해서, 

$$ x_{n+1} \equiv 1664525 x_n + 1013904223 \mod N $$

을 이용해서 생성된 수열을 이용한 것이다. 

그런데... 결과를 잘 살펴보면 \(x_0 = 1\)부터 생성을 시작했다고 봐도 무방하다는 것을 알 수 있다. 게다가 주어진 \(a\), \(b\), \(N\)의 값은 계산수학 분야의 유명한 책인 Numerical Recipies에서 제안하는 선형 합동 생성기의 '설정값'이라고 한다. 결국 선형대수와 군의 표지 디자인은 절대 아무렇게나(?) 한 것이 아니라는 것이다...