5장. 유한체

개요

군·환·체의 대수 구조, GF(p) 유한체, 다항식 산술, GF(2ⁿ) 유한체, 기약 다항식, 생성원

유한체(Finite Field)는 AES, 타원 곡선 암호 등 다수의 암호 알고리즘에서 핵심적인 역할을 한다. 이 장에서는 군·환·체의 대수 구조를 기초부터 쌓아 올려 $\text{GF}(p)$와 $\text{GF}(2^n)$을 이해한다.

학습 목표

• 군(Group), 환(Ring), 체(Field)를 구분한다.
• $\text{GF}(p)$ 유한체를 정의한다.
• 일반 다항식 산술, $Z_p$ 계수 다항식 산술, $\text{GF}(2^n)$ 모듈러 다항식 산술의 차이를 설명한다.
• $\text{GF}(2^n)$ 유한체를 정의한다.

---

5.1 군 (Groups)

군 $\{G, \bullet\}$은 이항 연산 $\bullet$이 정의된 집합 $G$로, 다음 공리를 만족한다.

공리	이름	내용
A1	닫힘 (Closure)	$a, b \in G \Rightarrow a \bullet b \in G$
A2	결합법칙 (Associative)	$a \bullet (b \bullet c) = (a \bullet b) \bullet c$
A3	항등원 (Identity)	$a \bullet e = e \bullet a = a$인 $e \in G$ 존재
A4	역원 (Inverse)	$a \bullet a' = a' \bullet a = e$인 $a' \in G$ 존재

아벨 군 (Abelian Group)

위 공리에 교환법칙(A5: $a \bullet b = b \bullet a$)이 추가되면 아벨 군이다.

순환 군 (Cyclic Group)

$G$의 모든 원소가 고정 원소 $a$의 거듭제곱 $a^k$로 표현되면 순환 군이다. 이때 $a$를 **생성원(Generator)**이라 한다. 순환 군은 항상 아벨 군이다.

---

5.2 환 (Rings)

환 $\{R, +, \times\}$은 덧셈과 곱셈이 정의된 집합으로, 다음을 만족한다.

조건	설명
A1–A5	덧셈에 대해 아벨 군
M1	곱셈에 대해 닫힘
M2	곱셈의 결합법칙
M3	분배법칙: $a(b+c) = ab + ac$

환의 하위 분류

구조	추가 조건
가환환 (Commutative Ring)	M4: 곱셈의 교환법칙
정역 (Integral Domain)	M4 + M5(곱셈 항등원) + M6(영인자 없음)

$Z_n = \{0, 1, \ldots, n-1\}$에서 모듈러 산술을 적용하면 가환환이 된다.

---

5.3 체 (Fields)

체 $\{F, +, \times\}$은 정역에 곱셈 역원(M7)을 추가한 구조이다.

$a \neq 0 \Rightarrow \exists\, a^{-1} \in F \;\text{s.t.}\; a \cdot a^{-1} = 1$

동치 정의:

1. 덧셈에 대해 아벨 군
2. 0을 제외한 원소가 곱셈에 대해 아벨 군
3. 분배법칙 성립

군·환·체 공리 요약

공리	군	아벨 군	환	가환환	정역	체
A1–A4	✓	✓	✓	✓	✓	✓
A5 (교환)		✓	✓	✓	✓	✓
M1–M3			✓	✓	✓	✓
M4 (교환)				✓	✓	✓
M5 (항등원)					✓	✓
M6 (영인자 없음)					✓	✓
M7 (곱셈 역원)						✓

---

5.4 유한체 GF(p)

유한체의 위수

유한체의 원소 수(위수)는 반드시 소수의 거듭제곱 $p^n$ 형태이다. 이를 갈루아 체(Galois Field) $\text{GF}(p^n)$으로 표기한다.

GF(p)의 정의

소수 $p$에 대해 $\text{GF}(p) = Z_p = \{0, 1, \ldots, p-1\}$이고, 모든 산술은 $\bmod p$로 수행한다.

$p$가 소수이면 $Z_p$의 모든 0이 아닌 원소가 $p$와 서로소이므로 곱셈 역원이 존재하여 체가 된다.

GF(2) — 가장 단순한 유한체

+	0	1
0	0	1
1	1	0

×	0	1
0	0	0
1	0	1

$\text{GF}(2)$에서 덧셈은 XOR, 곱셈은 AND와 동일하다.

GF(p)에서 곱셈 역원 구하기

확장 유클리드 알고리즘으로 계산한다.

$ax + by = 1 \;\Rightarrow\; y = b^{-1} \bmod a$

예시: $\text{GF}(1759)$에서 $550^{-1}$

• 확장 유클리드 알고리즘 적용: $1759x + 550y = 1$
• 결과: $y = 355$
• 검증: $550 \times 355 \bmod 1759 = 1$ ✓

---

5.5 다항식 산술

다항식의 정의

$f(x) = a_n x^n + a_{n-1} x^{n-1} + \cdots + a_1 x + a_0 = \sum_{i=0}^{n} a_i x^i$

다항식 산술의 세 가지 분류

분류	계수 집합	모듈러 다항식	용도
일반 다항식 산술	실수, 정수 등	없음	기초
$Z_p$ 계수 다항식	$\text{GF}(p)$의 원소	없음	중간 단계
모듈러 다항식 산술	$\text{GF}(p)$의 원소	$m(x)$로 나머지	$\text{GF}(2^n)$ 구성

다항식 나눗셈

$f(x) = q(x) \cdot g(x) + r(x)$

• $\deg(q) = \deg(f) - \deg(g)$
• $\deg(r) \leq \deg(g) - 1$

$r(x) = 0$이면 $g(x)$는 $f(x)$의 **인수(factor)**이다.

GF(2) 위의 다항식

$\text{GF}(2)$에서는 덧셈과 뺄셈이 동일하다 ($1 + 1 = 1 - 1 = 0$).

예시: $f(x) = x^7 + x^5 + x^4 + x^3 + x + 1$, $g(x) = x^3 + x + 1$일 때

• $f(x) + g(x) = x^7 + x^5 + x^4$
• $f(x) \div g(x)$: 몫 $x^4 + x^5 + x + 1$, 나머지 $0$ → $g(x) \mid f(x)$

기약 다항식 (Irreducible Polynomial)

체 $F$ 위에서 $f(x)$가 더 낮은 차수의 두 다항식의 곱으로 표현될 수 없으면 기약(irreducible)이라 한다. 정수에서의 소수에 대응된다.

예시: $x^3 + x + 1$은 $\text{GF}(2)$ 위에서 기약

다항식의 GCD

유클리드 알고리즘을 다항식에 확장 적용한다.

$\gcd[a(x),\; b(x)] = \gcd[b(x),\; a(x) \bmod b(x)]$

---

5.6 유한체 GF(2ⁿ)

필요성

$n$비트 데이터를 처리하는 암호 알고리즘에서 나눗셈을 사용하려면 $2^n$개 원소를 가진 체가 필요하다. $Z_{2^n}$에 모듈러 산술을 적용해도 체가 되지 않으므로, 다항식 산술 기반의 $\text{GF}(2^n)$을 구성한다.

구성 방법

$\text{GF}(2^n)$의 원소는 $\text{GF}(2)$ 위의 차수 $n-1$ 이하 다항식 전체이다. 총 $2^n$개 원소가 존재한다.

산술 규칙:

1. 계수 산술은 $\bmod 2$ (XOR)
2. 곱셈 결과가 차수 $n$ 이상이면 차수 $n$의 기약 다항식 $m(x)$로 나머지 계산

표현 방법

다항식의 각 계수를 비트로 나타내면 $n$비트 정수로 표현 가능하다.

$x^6 + x^4 + x^2 + x + 1 \;\longleftrightarrow\; 01010111 \;\longleftrightarrow\; \{57\}$

덧셈

계수별 $\bmod 2$ 덧셈 = 비트별 XOR

$\{57\} \oplus \{83\} = \{D4\}$

곱셈

AES에서 사용하는 $\text{GF}(2^8)$의 기약 다항식: $m(x) = x^8 + x^4 + x^3 + x + 1$

$x$와의 곱셈 (xtime 연산):

$x \cdot f(x) = \begin{cases} (b_6 b_5 b_4 b_3 b_2 b_1 b_0\, 0) & b_7 = 0 \\ (b_6 b_5 b_4 b_3 b_2 b_1 b_0\, 0) \oplus (00011011) & b_7 = 1 \end{cases}$

1비트 좌측 시프트 후, 최상위 비트가 1이면 $(00011011)$과 XOR한다.

일반 곱셈: xtime을 반복 적용하고 중간 결과를 XOR로 합산한다.

예시: $\{57\} \times \{83\}$

$\{57\} \times \{83\} = \{57\} \times [\{01\} \oplus \{02\} \oplus \{80\}]$ $= \{57\} \oplus \{AE\} \oplus \{38\} = \{C1\}$

이는 다항식으로 $x^7 + x^6 + 1$에 해당한다.

곱셈 역원

확장 유클리드 알고리즘을 다항식에 적용한다.

$a(x) \cdot v(x) + b(x) \cdot w(x) = \gcd[a(x),\; b(x)]$

$\gcd = 1$이면 $w(x) = b(x)^{-1} \bmod a(x)$

예시: $(x^7 + x + 1)^{-1} \bmod (x^8 + x^4 + x^3 + x + 1) = x^7$

생성원 (Generator)

위수 $q$인 유한체 $F$의 생성원 $g$는 $g^0, g^1, \ldots, g^{q-2}$로 $F$의 모든 0이 아닌 원소를 생성하는 원소이다.

$\text{GF}(2^3)$에서 $m(x) = x^3 + x + 1$의 생성원 $g$:

$g^3 = g + 1$을 이용하여 계산하면:

거듭제곱	다항식	이진수
$0$	$0$	000
$g^0$	$1$	001
$g^1$	$g$	010
$g^2$	$g^2$	100
$g^3$	$g + 1$	011
$g^4$	$g^2 + g$	110
$g^5$	$g^2 + g + 1$	111
$g^6$	$g^2 + 1$	101

거듭제곱 표현에서 곱셈: $g^a \times g^b = g^{(a+b) \bmod (2^n - 1)}$

예시: $g^4 \times g^6 = g^{10 \bmod 7} = g^3 = g + 1$

---

주요 용어

한국어	영어	설명
군	Group	닫힘·결합·항등·역원 공리를 만족하는 집합
아벨 군	Abelian Group	교환법칙이 추가된 군
순환 군	Cyclic Group	하나의 생성원으로 모든 원소 생성
환	Ring	덧셈(아벨 군) + 곱셈(닫힘·결합·분배)
정역	Integral Domain	가환환 + 곱셈 항등원 + 영인자 없음
체	Field	정역 + 곱셈 역원
유한체	Finite Field	유한 개 원소를 가진 체
갈루아 체	Galois Field	유한체의 다른 이름, $\text{GF}(p^n)$
기약 다항식	Irreducible Polynomial	더 낮은 차수의 곱으로 분해 불가능한 다항식
생성원	Generator	유한체의 모든 비영 원소를 거듭제곱으로 생성
다항식 환	Polynomial Ring	체 위의 다항식 전체가 이루는 환