[암호학] 12. 갈루아 체

[암호학] 12. 갈루아 체

체의 원소가 유한개이면, 그 체를 유한체(finite field)라고 한다. 

체 $F$의 단위원(곱셈항등원) 1에 대하여 $$n1=\underbrace{1+1+\cdots+1}_{n개}=0$$ 인 양의 정수 $n$이 존재할 때, 이러한 양의 정수 중 최소인 $n$을 체 $F$의 표수(characteristic)라 하고 $\text{char}F$로 나타내다. 

위의 조건을 만족하는 양의 정수 $n$이 존재하지 않으면 $\text{char}F=0$으로 나타내고, 체 $F$를 표수가 0인 체라고 한다. 

체 $F$의 표수가 $p$이면, $p$는 소수이고 모든 $a\in F$에 대하여 다음이 성립한다. $$pa=\underbrace{a+a+\cdots+a}_{p개}=0$$ 임의의 소수 $p$에 대하여 $\text{char}\mathbb{Z}_{p}=p$이고, $$\text{char}\mathbb{Z}=\text{char}\mathbb{Q}=\text{char}\mathbb{R}=\text{char}\mathbb{C}=0$$ 이다. 

체 $F$가 표수가 0인 체이면, 체 $F$는 유리수 체 $\mathbb{Q}$와 동일한 부분체를 포함하고, 체 $F$가 유한체이면, 적당한 소수 $p$에 대하여 $F$의 표수는 $p$이고, $F$는 체 $\mathbb{Z}_{p}$와 동일한 부분체를 포함하며 적당한 양의 정수 $n$에 대하여 $|F|=p^{n}$이다. 역으로 임의의 소수 $p$와 양의 정수 $n$에 대하여 $p^{n}$개의 원소로 이루어진 유한체가 존재하고 이러한 유한체는 유일하다.     

체 $F$의 원소 $a_{0},\,a_{1},\,...,\,a_{n}$과 부정원(indeterminate) $x$로 구성된 식 $$f(x)=a_{n}x^{n}+\cdots+a_{1}x+a_{0}$$ 를 체 $F$위의 다항식(polynomial)이라고 하고, 이때 $n$을 $f(x)$의 차수(degree)라고 하고 $\text{deg}f(x)=n$으로 나타낸다. 체 $F$위의 다항식 전체의 집합을 $F[x]$로 나타낸다. 즉 $$F[x]=\{a_{n}x^{n}+\cdots+a_{1}x+a_{0}\,|\,a_{0},\,a_{1},\,...,\,a_{n}\in F,\,n\in\mathbb{N}\cup\{0\}\}$$ $F[x]$는 체 $F$위의 벡터공간이고 단위원을 가진 환이다. 가환환 $F[x]$를 체 $F$위의 다항식 환(polynomial ring)이라고 한다. 

단위원을 가진 환 $R$의 덧셈 부분군 $N$이 모든 $a,\,b\in R$에 대하여 $$aN\subset N,\,Nb\subset N$$ 이면, $N$을 환 $R$의 아이디얼(ideal)이라고 한다.

체 $F$위의 1차 이상의 다항식 $f(x)$가 자기보다 차수가 낮은 두 다항식의 곱으로 인수분해되지 않는 다항식을 기약다항식(irreducible polynomial)이라고 한다. 

다항식 $f(x)\in F[x]$와 $\alpha\in F$에 대하여 $f(\alpha)=0$이면, $\alpha$를 다항식 $f(x)$의 근(zero 또는 root)이라고 한다. 

다항식 $f(x)$가 근을 갖지 않으면 $f(x)$는 기약다항식이다.  

체 $F$와 $E$에 대해 $F\leq E$이면, $E$를 $F$의 확대체(extension field)라고 한다. 

크로네커 정리(Kronecker theorem). $F$를 체, $f(x)\in F[x]$라 하자. 그러면 $F$의 확대체 $E$와 $\alpha\in E$가 존재해서 $f(\alpha)=0$이다.  

실수체 $\mathbb{R}$위에서 $p(x)=x^{2}+1$은 기약이므로 $p(x)$는 $\mathbb{R}$에서 근을 갖지 않는다. 크로네커 정리로부터 $i$가 존재해서 $p(i)=0$, 즉 $i^{2}=-1$인 $i$가 존재한다. $$a+bi\,(a,\,b\in\mathbb{R})$$ 과 같은 수를 복소수라 하고 이러한 수 전체의 집합을 $\mathbb{C}$로 나타낸다. 즉 $$\mathbb{C}=\{a+bi\,|\,a,\,b\in\mathbb{R}\}$$ 이때 $$\begin{align*}(a+bi)+(c+di)&=(a+c)+(b+d)i\\(a+bi)(c+di)&=(ac-bd)+(ab+bd)i\end{align*}$$ 이므로 $\mathbb{C}$는 덧셈과 곱셈에 대해 체를 이룬다. 복소수체 $\mathbb{C}$를 $\mathbb{R}$위의 벡터공간으로 보면 $\mathbb{C}$는 $\{1,\,i\}$를 기저로 갖는 벡터공간이다. 

임의의 소수 $p$와 양의 정수 $n$에 대하여 $q=p^{n}$이라고 할 때 위와 같은 방법으로 체 $\mathbb{Z}_{p}$로부터 $q$개의 원소로 이루어진 갈루아 체(Galois field) $GF(q)$를 만들 수 있다.    

실제로 체 $\mathbb{Z}_{p}$위의 적당한 $n$차 기약다항식 $$p(x)=x^{n}+c_{n-1}x^{n-1}+\cdots+c_{1}x+c_{0}\,(c_{0},\,c_{1},\,...,\,c_{n-1}\in\mathbb{Z}_{p})$$ 에 대하여 $p(\alpha)=0$인 원소 $\alpha$를 도입해 $$\xi=a_{0}+a_{1}\alpha+\cdots+a_{n-1}\alpha^{n-1}\,(a_{0},\,a_{1},\,...,\,a_{n-1}\in\mathbb{Z}_{p})$$ 와 같은 원소 전체의 집합을 $GF(q)$로 나타내자. 즉 $$GF(q)=\{a_{0}+a_{1}\alpha+\cdots+a_{n-1}\alpha^{n-1}\,|\,a_{0},\,a_{1},\,...,\,a_{n-1}\in\mathbb{Z}_{p}\}$$ 이때 $\alpha$는 다항식 $p(x)$의 근이므로 다음이 성립한다. $$\begin{align*}&\alpha^{n}+c_{n-1}\alpha^{n-1}+\cdots+c_{1}\alpha+c_{0}=0\\&\alpha^{n}=-c_{0}-c_{1}\alpha-\cdots-c_{n-1}\alpha^{n-1}\end{align*}$$ 집합 $GF(q)$의 임의의 두 원소 $$\begin{align*}\xi&=a_{0}+a_{1}\alpha+\cdots+a_{n-1}\alpha^{n-1}\\ \eta&=b_{0}+b_{1}\alpha+\cdots+b_{n-1}\alpha^{n-1}\end{align*}$$ 에 대하여 $\xi$와 $\eta$의 합을 $$\xi+\eta=(a_{0}+b_{0})+(a_{1}+b_{1})\alpha+\cdots+(a_{n-1}+b_{n-1})\alpha^{n-1}$$ 곱을 $$\begin{align*}\xi\eta&=(a_{0}+a_{1}\alpha+\cdots+a_{n}\alpha^{n-1})(b_{0}+b_{1}\alpha+\cdots+b_{n-1}\alpha^{n-1})\\&=d_{0}+d_{1}\alpha+\cdots+d_{n-1}\alpha^{n-1}\,\left(d_{k}=\sum_{l=1}^{k}{a_{l}b_{k-l}}\right)\end{align*}$$ 이라 하자. 이와 같이 $GF(q)$위에 덧셈과 곱셈을 정의하면 $GF(q)$는 이 두 연산에 대해 체가 된다. 또한 $GF(p)\subset GF(q)$이고 $GF(q)$를 $GF(p)$위의 벡터공간으로 볼 수 있고 즉, $$GF(q)=\{a_{0}+a_{1}\alpha+\cdots+a_{n-1}\alpha^{n-1}\,|\,a_{0},\,a_{1},\,...,\,a_{n-1}\in GF(p)\}$$ 다음이 성립한다. $$a_{0}+a_{1}\alpha+\cdots+a_{n-1}\alpha^{n-1}=0\,\Leftrightarrow\,a_{0}=a_{1}=\cdots=a_{n-1}=0$$ 따라서 체 $GF(q)$를 $GF(p)=\{0,\,1,\,...,\,p-1\}$위의 벡터공간으로 생각하면, $GF(q)$는 $\{1,\,\alpha,\,...,\,\alpha^{n-1}\}$를 기저로 갖는 $n$차원 벡터공간이다.     

*체 $E$가 체 $F$의 차수가 $n$인 유한확대체이고 $F$의 원소의 개수가 $p$이면, $E$는 $p^{n}$개의 원소를 갖는다.

$GF(2)=\{0,\,1\}$위에서 2차 다항식 $p(x)=x^{2}+x+1$은 기약다항식이다. $\alpha$를 $p(x)$의 근이라고 하면 $$GF(2^{2})=\{a_{0}+a_{1}\alpha\,|\,a_{0},\,a_{1}\in GF(2)\}=\{0,\,1,\,\alpha,\,1+\alpha\}$$ 이고 $$\alpha^{2}+\alpha+1=0,\,\alpha^{2}=-\alpha-1$$ 이다. 갈루아 체 $GF(2^{2})$에 대해 $GF(2^{2})^{*}=GF(2^{2})-\{0\}$이라 할 때 $$GF(2^{2})=\{1,\,\alpha,\,\alpha^{2}\},\,\alpha^{3}=1$$ 이므로 곱셈군 $GF(2^{2})^{*}$는 $\alpha$를 생성원으로 갖는 순환군이다. 

임의의 소수 $p$와 양의 정수 $n$에 대하여 $q=p^{n}$이라 하자. 갈루아 체 $GF(q)$에서 임의의 두 원소 $\xi,\,\eta$에 대해 다음이 성립한다. 

(1) $\text{char}GF(q)=p$이고 따라서 $p\xi=0$

(2) $(\xi+\eta)^{p}=\xi^{p}+\eta^{p}$, $(-\xi)^{p}=-\xi^{p}$, $(\xi\eta)^{p}=\xi^{p}\eta^{p}$ 

(3) 모든 $a\in GF(p)=\mathbb{Z}_{p}$에 대하여 $a^{p}=a$이다.  

(4) 체 $GF(p)$위의 다항식 $f(x)$에 대하여 $\xi$가 $f(x)$의 근이면, $\xi^{p}$도 $f(x)$의 근이다.  

증명: 

(1) $GF(q)$에서 $1\in GF(p)\subset GF(q)$이므로 $p\cdot1=0$이고 따라서 $GF(q)$의 표수는 $p$이므로 $p\xi=0$이다.  

(2) 임의의 $\xi,\,\eta\in GF(q)$에 대하여 $$(\xi+\eta)^{p}=\xi^{p}+\binom{p}{1}\xi^{p-1}\eta+\cdots+\binom{p}{p-1}\xi\eta^{p-1}+\eta^{p}$$ 이고 $$\binom{p}{1},\,...,\,\binom{p}{p-1}$$ 은 모두 $p$의 배수이므로, (1)에 의해 $(\xi+\eta)^{p}=\xi^{p}+\eta^{p}$이다. $p$가 홀수 소수이면 $(-\xi)^{p}=-\xi^{p}$이고 $p=2$이면 $$(-\xi)^{p}=(-\xi)^{2}=\xi^{2}=-\xi^{2}$$ 이고 (1)에 의해 $\xi^{2}=-\xi^{2}$이므로 $(-\xi)^{2}=(-\xi)^{2}=-\xi^{p}$이다. 분명히 $(\xi\eta)^{p}=\xi^{p}\eta^{p}$이다.  

(3) (2)에 의해 $a\in GF(p)$에 대하여 다음이 성립한다. $$a^{p}=(\underbrace{1+\cdots+1}_{a개})^{p}=1^{p}+\cdots+1^{p}=1+\cdots+1=a$$ (4) 다항식 $f(x)=a_{n}x^{n}+a_{n-1}x^{n-1}+\cdots+a_{1}x+a_{0}$에 대하여 $f(\xi)=0$이면, 위의 (2), (3)에 의해 다음의 결과를 얻는다. $$\begin{align*}0&=\{f(\xi)\}^{p}=(a_{n}\xi^{n}+a_{n-1}\xi^{n-1}+\cdots+a_{1}\xi+a_{0})^{p}\\&=a_{n}^{p}(\xi^{p})^{n}+a_{n-1}^{p}(\xi^{p})^{n-1}+\cdots+a_{1}^{p}\xi^{p}+a_{0}^{p}\\&=a_{n}(\xi^{p})^{n}+a_{n-1}(\xi^{p})^{n-1}+\cdots+a_{1}\xi^{p}+a_{0}\\&=f(\xi^{p})\end{align*}$$ 임의의 소수 $p$와 양의 정수 $n$에 대하여 $q=p^{n}$이라 하자. 갈루아 체 $GF(q)$의 곱셈군 $GF(q)^{*}=GF(q)-\{0\}$는 위수가 $q-1$인 순환군이다. 

한 원소 $\alpha\in GF(q)$의 위수가 $q-1$일 때 즉, $$GF(q)^{*}=\langle\alpha\rangle=\{1,\,\alpha,\,\alpha^{2},\,...,\,\alpha^{q-2}\},\,\alpha^{q-1}=1$$ 일 때 $\alpha$를 갈루아 체 $GF(q)$의 원시원소(primitive element)라고 한다. 

$GF(q)^{*}=\langle \alpha^{i}\rangle$일 필요충분조건은 $\text{gcd}(i,\,q-1)=1$이므로 $a^{i}$가 체 $GF(q)$의 원시원소일 필요충분조건은 $\text{gcd}(i,\,p-1)=1$이다. 따라서 갈루아 체 $GF(q)$에는 $\phi(q-1)$개의 원시원소가 존재한다. 임의의 정수 $i$에 대하여 $$(\alpha^{i})^{q-1}=(\alpha^{q-1})^{i}=1^{i}=1,\,(\alpha^{i})^{q}=(\alpha^{q})^{i}=\alpha^{i}$$ 이므로 $GF(q)^{*}$의 각 원소의 위수는 $q-1$의 약수이고 $GF(q)^{*}$의 원소는 $x^{q-1}-1$의 근이므로 따라서 $GF(q)$는 다항식 $f(x)=x(x^{q-1}-1)=x^{q}-x$의 근 전체의 집합이다.   

임의의 소수 $p$와 양의 정수 $n$에 대하여 $q=p^{n}$이라 하자. 갈루아 체 $GF(q)$의 원소 $\xi$에 대하여 다음의 세 조건을 만족하는 체 $GF(p)$위의 다항식 $g(x)$를 체 $GF(p)$위의 $\xi$의 최소다항식(minimum polynomial)이라고 한다. 

(i) $\text{deg}g(x)\geq0$

(ii) $g(\xi)=0$

(iii) 다항식 $f(x)\in GF(p)[x]$에 대하여 $f(\xi)=0$일 필요충분조건은 $g(x)$가 $f(x)$의 인수, 즉 $g(x)|f(x)$이다.

갈루아 체 $GF(q)$의 원시원소 $\alpha$의 체 $GF(p)$위에서의 최소다항식 $p(x)$를 체 $GF(p)$위의 원시다항식(primitive polynomial)이라고 한다. 

최소다항식은 정의에 의해 $n$차 이하의 기약다항식($\because\,\xi\in GF(p)$)이고, 원시다항식은 체 $GF(p)$위의 $n$차 기약다항식이다.  

임의의 소수 $p$와 양의 정수 $n$에 대하여 $q=p^{n}$이라 하자. 갈루아 체 $GF(q)$의 원소 $\xi$의 체 $GF(p)$위의 최소다항식을 $g(x)$라고 하면 다음이 성립한다.

(1) $g(x)$는 체 $GF(p)$위에서 $x^{q-1}-1$의 약수이다. 

(2) $\xi^{p}$는 $g(x)$의 근이고 $\xi^{p}$의 최소다항식은 $g(x)$이다. 

임의의 소수 $p$와 양의 정수 $m$에 대하여 $q=p^{n}$라 하고 갈루아 체 $GF(q)$의 원시원소 $\alpha$에 대해 $p(x)$를 $p(\alpha)=0$인 체 $GF(p)$위의 $n$차 원시다항식이라 하자. 그러면 다음이 성립한다. 

(1) $p(x)$는 체 $GF(p)$위에서 $x^{q-1}-1$의 약수이다. 

(2) 체 $GF(q)$에서 $p(x)$는 $n$개의 서로 다른 근 $$\alpha,\,\alpha^{p},\,\alpha^{p^{2}},\,...,\,\alpha^{p^{n-1}}$$ 을 갖고, 이들은 $GF(q)$의 원시원소이며 그 최소다항식은 $p(x)$이다. 그리고 체 $GF(p)$위의 $n$차 원시다항식은 $\displaystyle\frac{\phi(q-1)}{n}$개 존재한다. 

참고자료:

암호학과 부호이론, 박승안, 경문사

A First Course in Abstract Algebra, Fraleigh, Addison-Wesley