환(ring)에서 체(field)까지 - 7. 유한체(finite field)

written by jjycjn   2016. 5. 24. 07:24

유한체(Finite field)


유한체(finite field)는 대수적 구조(algebraic structure)에 따라 완벽히 분류할 수 있는 몇 안되는 예 중에 하나이다. 이전 절에서 유한체를 구성하는 방법 중 한가지를 살펴 보았다.


정리 7.1

주어진 소수 $p$에 대하여, $f(x)$가 차수(degree)가 $k$인 $\Z_p[x]$의 기약다항식(irreducible polynomial)이라 하자. 그러면 $\Z_p[x]/ \langle f(x) \rangle$는 위수(order)가 $p^k$인 체가 된다.


증명. 주어진 다항식이 기약이므로 이 다항식은 더 작은 차수를 가진 다항식들의 곱으로 표현할 수 없다. 이제 이전 절에서 살펴 보았듯이 $\Z_p[x]/ \langle f(x) \rangle$의 잉여류 대표원소들은 모두

\[ a_0 + a_1x + a_2x^2 + \cdots + a_{k-1}x^{k-1} \]

의 형태를 가진다고 가정할 수 있고, 이 집합은 $p^k$의 원소를 가진 환이 됨을 알 수 있다.

이제 $g(x)$를 $\Z_p[x]/ \langle f(x) \rangle$의 한 잉여류 대표원소라 하자. 이제 $f(x)$가 기약이므로 $\gcd(g(x),\, f(x)) = 1$를 얻는다. 여기에 유클리드 호제법을 이용하면 적당항 다항식 $a(x)$, $b(x)$에 대하여 $1 = a(x)g(x) + b(x)f(x)$를 얻는다. 따라서 $a(x)$가 $g(x)$의 역에 대한 잉여류 대표원소가 된다. ■


이제 임의의 소수 $p$와 양의 정수 $k$에 대하여, 차수(degree)가 $k$인 $\Z_p[x]$의 기약다항식(irreducible polynomial)이 존재함을 보일 수 있다. 따라서


정리 7.2

임의의 소수 $p$와 양의 정수 $k$에 대하여, 위수(order)가 $p^k$인 체가 존재한다.


참고.

  1. 사실 이러한 다항식은 유일하지 않다. 예를 들어 $p=3$이라 하자. 이제 차수 $k=2$인 $9$의 다항식들 중 (최고차항의 계수가 $1$이고) 기약인 다항식은 $3$가 존재한다. 또한 차수 $k=3$에 대하여는 $27$개의 다항식 중 $8$개가 기약이고, $k=5$이면 $243$개의 다항식 중 $48$개가 기약이다.
  2. 이차다항식이나 삼차다항식의 경우 기약성을 판별하기가 상대적으로 매우 쉽다. 만약 기약이 아니라면 일차다항식인 인수가 반드시 존재하고 이는 주어진 다항식의 근이 존재함과 동치이기 때문이다. 하지만, 고차다항식의 경우는 기약성의 판별이 상대적으로 쉽지 않다. 예를 들어 다항식 $x^4 + 1$는 $\Z_3[x]$에서 근이 존재하지 않지만, $(x^2 + 2x - 1)(x^2 - 2x - 1)$과 같이 분해되므로 기약이 아니다.


정리 7.3

위수(order)가 $p^k$인 두 체는 (환으로써) 동형(isomorphic)이다.


예제.

이전 절에서 $1 \mapsto 1$이고 $x \mapsto y + 1$로 정의한 사상은 $\Z_3[x]/ \langle x^2 +1 \rangle$에서 $\Z_3[y]/ \langle y^2+ 2y +2 \rangle$로 가는 환동형사상임을 확인했다.


이제 주어진 유한체(finite field)에 대하여, 이 체의 모든 원소들의 덧셈에 대한 위수(additive order)는 모두 같고 또한 이 위수는 반드시 소수여야 함을 증명할 수 있다.


정의 7.4

이러한 소수를 주어진 체의 표수(characteristic)라 한다.


정의 7.5

임의의 체에 대하여 $1$에 의해 생성된 부분체를 소부분체(prime subfield)라 한다. 또한 이는 $\Z_p$와 동형이다.


참고.

주어진 체에 대하여, 만약 원소 $1$이 유한한 위수를 가지지 않으면 (물론 이 경우 주어진 체는 유한이지 않다.) 이 체의 표수를 $0$으로 정의한다. 표수가 $0$인 체에 대하여, 원소 $1$에 의해 생성된 부분체는 유리수체 $\Q$와 동형이다.


정리 7.6

모든 체는 (그 체에 대한) 임의의 부분체 위에서 벡터공간(vector space)가 된다.


$E$가 체 $F$의 부분체라 하자. 그러면 $E$ 위에서 $F$의 기저(basis)를 찾을 수 있다. 이제 기저의 워소의 개수를 $E$ 위에서의 $F$의 차원(dimension)이라 하고 $[E: F]$로 나타낸다. 특히, 체 $F$가 유한이고 $\abs{F} = p^k$라 하면, 이는 소부분체 위에서 차원이 $k$인 벡터공간이다.

이제 $r$이 소부분체의 원소는 아닌 $F$의 원소라 하자. 이제 $F$의 원소들 $1,\, r,\, r^2,\, r^3,\, \ldots$을 생각해 보자. $F$가 유한이므로 이 원소들의 수열은 결국 선형독립(linearly independent)을 이루지 못하게 된다. 이제 $\{1,\, r,\, r^2,\, \ldots,\, r^{m-1}\}$이 선형독립인 집합이라 하자. 또한 소부분체 $\Z_p$의 원소를 계수로 가지는 다항식 $f(r) = a_0 + a_1r + a_2r^2 + \cdots + a_{m-1}r^{m-1} = 0$들을 생각해 보자.

이제 이러한 다항식 $f$들에 의해 생성된 부분집합은 크기가 $p^m$인 부분체를 이룬다. 이 다항식 $f$를 원소 $r$의 최소다항식(minimal polynomial)이라 하고, 체 $F$가 이 부분체에 대하여 벡터공간이 되어야 하므로 $m$이 $k$를 나눠야 함을 알 수 있다.


이제 유한체에 대한 또 하나의 중요한 정리에 대해 살펴보자.


정리 7.7

유한체(finite field)의 곱셈군(multiplicative group)은 언제나 순환군(cyclic group)이다.


먼저 $p$가 소수일 때, $\Z_p$의 곱셈군 $U_p$는 순환군이였음을 기억하자. 따라서 위 정리를 증명하기 위해서는 아래의 보조정리를 먼저 살펴 보아야 한다.


보조정리.

체의 원소를 계수(coeffieitent)로 가지는 차수가(degree)가 $k$인 다항식은 많아야 $k$개의 근(root)을 갖는다.


증명. 만약 $f(x)$가 근 $\alpha$를 가지면, $f(x)$를 $x - \alpha$로 나누어 $f(x) = (x - \alpha) q(x) + r$를 얻는다. 이제 $f(\alpha) = 0$이므로, $r = 0$이여야만 하고 따라서 $f(x)$는 $x - \alpha$로 나누어진다. 따라서 $f(x)$는 각각의 근에 대하여 일차다항식을 인수로 가져야 하고 $\deg(f)$보다 많은 개수의 근을 가질 수 없다. ■


이제 증명을 정리하기 이전에 특수한 경우를 먼저 살펴 보자. $9$개의 원소를 가지는 체의 곱셈군을 생각해 보자. 이 곱셈군의 위수는 $8$이고 따라서 $C_8$, $C_4 \times C_2$, or $C_2 \times C_2 \times C_2$ 중의 하나와 동형이다. 만약 이 곱셈군이 $C_8$이 아니라면, 어떤 원소 $r$이든지 $r^4 = 1$을 만족해야만 한다. 하지만 이 경우, 다항식 $x^4 - 1$이 너무 많은 근을 갖게 되어 모순이 생긴다.


정리의 증명.

위수가 $p^k$인 유한체의 곱셈군은 위수 $p^k - 1$를 갖는다. 이제 소수 $q$가 존재하여 $p^k - 1$를 나눈다고 가정해 보자. 그러면 이제 위수가 $q$의 거듭제곱인 원소로 이루어진 집합은 위수가 (적당한 $s$에 대하여) $q^s$인 부분군을 이룬다. 만약 이 부분군이 순환군이 아니라면 이 부분군의 어떤 원소 $r$이든지 $r^{s-1} = 1$을 만족해야만 하고 따라서 다항식 $x^{s-1} - 1$은 너무 많은 근을 갖게 된다. 그러므로 주어진 곱셈군은 순환군들의 직접곱(direct product)의 형태를 가질 수 없고 따라서 순환군이 된다. ■


참고. 체 $GF(p^k)$의 곱셈군이 순환군이란 사실은 계산을 매우 간단히 줄여준다. 왜냐하면 이 곱셈군의 생성원(generator) $z$이 존재하여, 이 군의 모든 원소들을 $z$의 거듭제곱으로 나타낼 수 있고 이를 이용하여 원소들의 곱을 쉽게 계산할 수 있기 때문이다. 또한 두 원소 $z^m$과 $z^n$의 합을 구하고자 할 때, $z^m + z^n = z^m(1 + z^{n-m})$라는 사실을 이용하여 $1 + z^r$ 형태의 원소를 $z$의 거듭제곱으로 표현해 둔 표만 있다면 덧셈 또한 손쉽게 계산할 수 있다.

  ::  
  • 공유하기  ::