Archive

본 글에서는 Church Encoding의 기본적 개념과 이를 특정한 함수로 구현할 때 발생할 수 있는 문제점을 다룬다.

1. Church Numeral이란

Church Numeral은 어떤 함수 $f$에 대해 자연수 $k$를 $f^k$로 표현하는 것이다.

2. Church Numeral의 사칙연산

Church Numeral은 페아노 공리계를 만족하며 자연수에 대한 사칙연산을 정의할 수 있다.

• successor: 함수 $g$가 자연수 $n$을 encode하면 $f\circ g$는 $f\circ f^n=f^{n+1}$이므로 $g$의 successor이다.
• 덧셈: 자연수 $n$과 $m$을 encode하는 함수 $g$, $h$에 대해 $g\circ h$는 $f^n\circ f^m=f^{n+m}$이므로 $n+m$을 encode한다. 즉, $g\circ h$는 $g$와 $h$의 합이다.
• 곱셈: 자연수 $n$과 $m$와 $n$을 encode하는 함수 $g$에 대해 $g^m$은 $(f^n{)}^m=f^{nm}$이므로 $nm$을 encode한다. 즉 $g^m$은 $g$에 자연수 $m$을 곱한 결과이다.
• predecessor: $f$의 역함수 $f^{-1}$와 2 이상의 자연수 $n$을 encode하는 함수 $g$에 대해 $f^{-1}\circ g=f^{-1}\circ f^n=f^{n-1}$이므로 $f^{-1}\circ g$은 $n-1$을 encode하며 $g$의 predecessor이다.
• 뺄셈: 자연수 $n,m(n>m)$을 encode하는 함수 $g$, $h$에 대해 $g\circ h^{-1}$은 $f^n\circ (f^m{)}^{-1}=f^{n-m}$이므로 $n-m$을 encode한다. 즉, $g\circ h^{-1}$은 $g$와 $h$의 차이다. 이를 통해 $0$과 음수의 encoding을 자연스럽게 정의할 수 있다.

3. 유한 집합과 Church Numeral

Church Numeral을 특정한 함수를 이용하여 구현할 때, 어떤 함수를 쓰는지와는 무관하게 같은 수는 같은 함수로 encode된다. 다만, 사용하는 함수에 따라 "다른 수는 항상 다른 함수로 encode된다"는 명제는 성립하지 않을 수 있다. 특히, 유한 집합 $S$에 대해 $f:S\Rightarrow S$는 $f^a=f^b$를 만족하는 서로 다른 자연수 $a,b$를 무한히 많이 갖는다. 이를 증명해보자.

Proof: $\mathrm{\exists }a,b\in S:a\ne b\wedge f^a=f^b$ 

$S$의 각 원소를 정점으로 갖고, 간선 집합이 $\{x\to f(x)|x\in S\}$인 함수 $f:S\Rightarrow S$가 존재하는 그래프를 functional graph라고 한다. functional graph가 사이클을 갖지 않는다고 가정하면, 임의의 $x\in S$에 대해 집합 $\{x,f(x),f^2(x),\cdots ,f^{n(S)}(x)\}$는 크기가 $n(S)+1$이며 $S$의 부분 집합이다. 이는 모순이므로 functional graph는 사이클을 적어도 하나 가진다. 또한 모든 정점의 outdegree는 정확히 1이므로 모든 사이클은 단순 사이클이라는 것도 확인할 수 있다.

즉 functional graph는 단순 사이클과 그 사이클의 정점을 루트로 하는 몇 개의 트리로 구성된 component를 하나 이상 가진다. 따라서 모든 사이클의 길이 $L_1,L_2,\cdots$의 최소공배수 $L$, 어떠한 자연수 $N$에 대해 $x\ge N$이면 $f^x=f^{x+L}$인 $N$이 존재하므로 위 명제는 참인 동시에 그러한 $a,b$는 무한히 많이 존재한다.

4. 무한 집합과 Church Numeral

그렇다면, 무한 집합에서 정의되는 함수는 이러한 문제에서 자유로운가? $f(x)=ix$와 이를 일반화한 $f(x)=e^{i\frac{2k\pi }{n}}x$는 무수히 많은 길이 $n$의 단순 사이클이 나타난다.

이외의 예시로는 $f(x)=\sqrt{1-x^2}$이 있다. 위의 예시와는 다르게, 2개의 수가 사이클을 이루고 나머지 2개의 수가 사이클에 붙어 있는 꼴이다.

두번째 예시인 $f(x)=\sqrt{1-x^2}$와 $f(x)=-\frac{1}{x}$ 등의 예시를 통해 길이가 2인 사이클을 구성하는 수들을 정의역으로 할 때 사용한 함수 $f$는 $y=x$에 대해 대칭임을 알 수 있다. 나아가, $f:\mathbb{R}\Rightarrow \mathbb{R}$의 모든 사이클의 길이가 2일 필요충분조건은 $f:S\Rightarrow S$가 $y=x$ 대칭이며 정의역 $T$에서 $f$와 동일한 $g:T\Rightarrow S$가 존재하는 만족하는 두 집합 $S$와 $T=\mathbb{R}\mathrm{\setminus }S$가 존재한다는 것임을 확인할 수 있다.

영문 위키피디아에 따르면 행렬이란 수, 기호, 표현식 등을 직사각형 형태로 배열한 배열이다. 다음과 같은 것 역시 행렬이라는 것을 쉽게 알 수 있다.

$$\left[\begin{array}{cc}{e}^x& -3.5\\ 3& 8\end{array}\right]$$

선형대수학은 행렬, 벡터 등 선형성과 관련된 것을 연구하는 학문으로써, 그 연구결과가 다양한 방식으로 활용되고 있다. 대표적인 예시로는 연립방정식의 해의 존재성, 유일성 등에 관한 증명, 혹은 실질적인 해의 계산 정도가 여러분에게 친숙할 것이다.

다만 프로그래머에게 행렬은 일반적으로 실수 내지는 복소수 상에서 정의되는 행렬만을 다루기에 나머지 연산이 접목된 연립 방정식의 풀이 등에서는 이를 행렬과 연관짓는 사고가 쉽게 가능하지는 않은 듯 하다. 따라서 본 글의 취지는 체란 무엇이며, 실수체가 아닌 체, 특히 갈루아체에서도 가우스-조던 소거를 통한 역행렬 계산이 가능함을 설명하는 것이다.

우선 '체(Field)'란 무엇인지에 대해 얘기해보자. 특별한 것은 아니고, 추상대수학에서 연산의 본질에 대해 탐구하기 위해 분류하는 것의 일종이다. 흔히 군, 환, 체라는 용어를 얼핏 들어본 적이 있을텐데, 각각의 정의를 살펴보자.

집합 $G$, 연산 $\circ$, 항등원 $e\in G$가 다음 조건을 만족하면 $(G,\circ ,e)$를 군이라 부른다.

• 결합 법칙: $\mathrm{\forall }a,b,c\in G,(a\circ b)\circ c=a\circ (b\circ c)$
• 항등원: $\mathrm{\forall }a\in G,\mathrm{\exists }e\in G:a\circ e=e\circ a=a$
• 역원: $\mathrm{\forall }a\in G,\mathrm{\exists }b\in G:a\circ b=b\circ a=e$

집합 $R$, 연산 $+,\circ$, 덧셈의 항등원 $0$에 대해 $(R,+,0)$이 군이고 아래 조건이 성립하면 $(R,+,\circ ,0)$을 환이라 부른다.

• 덧셈의 교환 법칙: $\mathrm{\forall }a,b\in R,a+b=b+a$
• 곱셈의 결합 법칙: $(a\circ b)\circ c=a\circ (b\circ c)$
• 덧셈에 대한 곱셈의 분배 법칙: $(a+b)\circ c=a\circ c+b\circ c$, $a\circ (b+c)=a\circ b+a\circ c$
  • 곱셈에 대한 교환 법칙이 성립하는지에 대한 조건이 없으므로 각 경우를 따로 정의함
  • 곱셈에 대한 교환 법칙이 성립하는 환을 가환환이라고 함

또한, 곱셈에 대한 항등원 1이 존재하며 0이 아닌 원소가 곱셈에 대한 역원을 가지면 해당 환을 나눗셈환이라고 한다.

마지막으로, 체는 가환환이며 나눗셈환인 $(F,+,\circ ,0,1)$을 체라고 부른다.

실수 집합인 $\mathbb{R}$가 위의 조건을 모두 만족한다는 것은 쉽게 확인 가능하다.

체를 간단하게 말하자면, 사칙연산이 실수에서와 비슷하게 잘 정의되는 집합과 연산을 체라고 부르는 것이다.

유한체, 또는 갈루아 체는 유한한 개수의 원소를 갖는 체이다. 대표적으로 $p$로 나눈 나머지의 집합이 있으며, 이는 $\mathbb{Z}/p\mathbb{Z}$로도 표기한다. 유한체에 대한 자세한 내용은 위키백과 - 유한체에서 확인 가능하나, 본 글에서는 간단하게 $p$로 나눈 나머지의 집합에 대해서만 이야기할 예정이다.

중요한 점은 $\mathbb{Z}/p\mathbb{Z}$가 과연 체냐는 것이다. 다른 것들은 일반적인 사칙 연산과 비슷하나, 나눗셈의 경우는 잘 정의된다는 것이 다소 비직관적이다. 예를 들어, 정수 집합 $\mathbb{Z}$는 $1\in \mathbb{Z}$, $2\in \mathbb{Z}$에 대해 $1/2$가 정의되지 않지 않은가.

$\mathbb{Z}/p\mathbb{Z}$에서 곱셈의 역원, 즉 나눗셈은 잉여역수를 이용하여 정의된다. $a$의 잉여역수는 다음을 만족하는 정수 $b$이다.

$$ab\equiv ba\equiv 1(\text{mod }p)$$

위 식은 $ab=kp+1$인 정수 $k$가 존재함과 동치이다. 즉 $ab-pk=1$을 만족하는 정수 $b,k$의 존재성을 증명하면 $\mathbb{Z}/p\mathbb{Z}$가 체임을 알 수 있으며, 이는 디오판토스 방정식 $ax+by=gcd(a,b)$가 정수해를 갖는다는 사실로부터 쉽게 알 수 있다.($\because \mathrm{\forall }x:1\le x<p,gcd(x,p)=1$)

따라서 $\mathbb{Z}/p\mathbb{Z}$는 체이다.

가우스-조던 소거는 다음의 행 기본 연산을 이용하여 진행된다.

• $i$행을 0이 아닌 상수 $c$에 대해 $c$배 하여 $j$행에 더한다. $E(i,j;c)$
• $i,j$행을 교환한다. $E(i,j)$
• $i$행을 0이 아닌 상수 $c$에 대해 $c$배한다. $E(i;c)$

위 세 연산이 잘 정의된다면 가우스-조던 소거가 잘 정의된다고 볼 수 있으며, 위 연산들은 모두 체인 $\mathbb{Z}/p\mathbb{Z}$에서 잘 정의된다. 따라서 실수체에서와 마찬가지로 augmented matrix $[A|I]$를 가우스-조던 소거하면 $[I|A^{-1}]$를 얻을 수 있다.

이는, 실수에서와 마찬가지로 행렬을 이용해 $\mathbb{Z}/p\mathbb{Z}$에서 정의되는 연립방정식을 풀 수 있음을 의미한다.

일반적으로, 모듈로 연산의 법이 소수가 아닌 경우도 많이 마주할 수 있다. 이러한 경우 법을 소인수분해하여 $\prod {p_i}^{e_i}$ 꼴로 표현한 후 각 ${p_i}^{e_i}$에 대해 연립방정식을 푼 결과를 Chinese Remainder Theorem을 이용하여 통합해줌으로써 해결할 수 있다.

해당 글에서는 $\mathbb{Z}/p\mathbb{Z}$ 상의 순환 행렬에 대해 페르마 소정리가 성립함을 증명한다.

Theoretical Background

1. 페르마 소정리

소수 $p$와 정수 $a$에 대해 $a\equiv a^p(\text{mod }p)$가 성립한다.

2. 순환 행렬

$\mathbb{Z}/p\mathbb{Z}$ 상의 $n\times n$ 행렬 $M$이 다음과 같은 성질을 만족하면 $M$은 순환 행렬이다.
$$\mathrm{\forall }i,j,a,b\in \mathbb{Z}/p\mathbb{Z}\text{ which satisfies }i-j\equiv a-b(\text{mod }n),M_{ij}=M_{ab}$$

Proof

1. Matrix Expression of polynomial multiplication

다항식 $f(x)={\displaystyle \sum _{k=0}^n{a}_k{x}^k}$를 다음과 같은 벡터에 대응시켜보자.
$$v=\left[\begin{array}{c}{a}_0\\ a_1\\ ⋮\\ a_n\end{array}\right]$$
다항식 $f,g$ 곱셈에서 $x^c$의 계수는 $a+b=c$를 만족하는 음이 아닌 가능한 모든 정수쌍 $a,b$에 대해 $f$의 $x^a$의 계수와 $g$의 $x^b$의 계수를 합한 값과 같으며, 두 $n$차 다항식을 곱하면 최대 $2n$차가 된다는 것은 익히 알려져 있다. 이를 고려할 때, '다항식 $f$를 곱한다'는 연산은 다음과 같은 $(2n+1)\times (n+1)$행렬로 표현할 수 있다.

$$\left[\begin{array}{cccc}{a}_0& 0& \cdots & 0\\ a_1& a_0& \cdots & 0\\ a_2& a_1& \cdots & 0\\ ⋮& ⋮& \ddots & ⋮\\ 0& 0& \cdots & a_n\end{array}\right]$$

2. Polynomial multiplication over $\mathbb{Z}/p\mathbb{Z}$

페르마 소정리에 의하여 0이 아닌 $x\in \mathbb{Z}/p\mathbb{Z}$는 $x^{p-1}\equiv 1(\text{mod }p)$를 만족하므로, $\mathbb{Z}/p\mathbb{Z}$에서 정의되며 근을 갖지 않는 다항식 $f$를 다음과 같은 $(p-1)\times (p-1)$ 순환 행렬에 대응시키면, 다항식 $f,g$와 이에 대응하는 행렬 $M_f,M_g$에 대해서 $f\times g$가 $M_f\times M_g$에 대응된다는 성질을 확인할 수 있다. 따라서 다항식을 $f$을 벡터가 아닌, 순환 행렬에 대응시키면 더 자연스러운 대응 관계를 관찰할 수 있다.

$$\left[\begin{array}{cccc}{a}_0& a_{p-2}& \cdots & a_1\\ a_1& a_0& \cdots & a_2\\ a_2& a_1& \cdots & a_3\\ ⋮& ⋮& \ddots & ⋮\\ a_{p-2}& a_{p-3}& \cdots & a_0\end{array}\right]$$

3. Fermat's Little Theorem of Circulant Matrix

(2.)에서의 관찰을 귀납적으로 적용하면, $\mathbb{Z}/p\mathbb{Z}$ 상에서 정의되고 근을 갖지 않는 $(p-2)$차 다항식 $f$에 대응되는 $(p-1)\times (p-1)$ 순환 행렬 $M$에 대해 $M^p$가 $\{f(x){\}}^p$에 대응된다. 페르마 소정리에 따라 $f(x)\equiv \{f(x){\}}^p(\text{mod }p)$이므로 $\{f(x){\}}^p$에 대응되는 $M^p$는 $f(x)$에 대응되는 $M$과 동일하여, $M\equiv M^p(\text{mod }p)$임을 알 수 있다.

4. Extension (Euler's Theroem of Circulant Matrix)

$\mathbb{Z}/n\mathbb{Z}$에서 위와 같은 과정을 진행할 수 있는지 확인해보자. 핵심 아이디어는 $\mathbb{Z}/p\mathbb{Z}$상에서 근을 갖지 않는 모든 다항식은 $p-2$차 이하로 나타나며, 다항식 곱셈을 행렬의 곱셈으로 표현할 수 있다는 것이었다. 마찬가지로 $\mathbb{Z}/n\mathbb{Z}$ 상에서 근을 갖지 않는 임의의 다항식은 오일러 소정리에 의해 $(\varphi (n)-1)$차 이하의 다항식으로 표현된다. 행렬과의 대응관계 역시 똑같이 정의할 수 있으므로, 다음과 같은 관계가 $\mathbb{Z}/n\mathbb{Z}$ 상에서 정의되며 근을 갖지 않는 $(\varphi (n)-1)$차 다항식에 대응되는 $\varphi (n)\times \varphi (n)$순환행렬 $M$에 대하여 $M\equiv M^{\varphi (n)}(\text{mod }n)$가 성립한다.