[암호학] 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