유한체

1. 개요[편집]

유한체 Finite Field · Galois Field
기호	GF(q) 또는 𝔽q
존재 조건	q = pn (p 는 소수) — 그 외에는 없다
유일성	같은 q 면 동형사상 하나로 전부 같다
곱셈군	위수 q−1 의 순환군
이름	Évariste Galois (1830)
수치해석에서	반올림이 존재하지 않는 산술

유한체(finite field, Galois field)는 원소가 유한개이면서 사칙연산이 전부 되는 대수구조, 즉 덧셈·뺄셈·곱셈이 닫혀 있고 0이 아닌 모든 원소에 곱셈 역원이 있는 유한집합이다. 원소 개수 $q$ 를 붙여 $GF(q)$ 또는 $\mathbb{F}_q$ 로 쓴다.

수치해석 문서에서 유한체를 다루는 이유는 하나다. 여기에는 반올림 오차가 없다. 부동소수점 연산에서 $a/b$ 는 근사값이지만 $GF(q)$ 에서 $a/b$ 는 정확히 하나 있는 정확한 원소이고, 나눗셈이 정확하니 가우스 소거법에도 상쇄가 없고 조건수라는 개념 자체가 성립하지 않는다. 그 대가로 “크기”와 “가까움”을 잃는다 — 순서도 극한도 없으므로 반복법·수렴·근사는 통째로 사라진다. 정확성과 근사 가능성을 맞바꾼 세계이고, 그 거래가 이득인 자리(오류정정 부호, 정확 산술, 암호)에서 유한체가 산다.

2. 분류 정리 — q = p^n 만 존재한다[편집]

유한체 이론이 아름다운 이유는 분류가 완전히 끝나 있기 때문이다.

유한체 $GF(q)$ 가 존재할 필요충분조건은 $q = p^n$ ($p$ 는 소수, $n \ge 1$)이고, 주어진 $q$ 에 대해 유한체는 동형을 무시하면 유일하다.

앞쪽 절반의 증명 스케치는 이렇다. 체 $F$ 의 표수(characteristic)는 $1$ 을 몇 번 더해야 0이 되는가인데, 이것이 합성수 $ab$ 라면 $(a\cdot 1)(b\cdot 1)=0$ 인데 두 인수가 0이 아니라 체의 정의(영인자 없음)에 어긋난다. 따라서 표수는 소수 $p$ 이고, $F$ 는 소수체 $\mathbb{Z}/p\mathbb{Z} \cong \mathbb{F}_p$ 를 부분체로 품는다. 그러면 $F$ 는 $\mathbb{F}_p$ 위의 벡터공간이고, 유한하므로 차원 $n$ 이 유한이라 $|F| = p^n$ 이다.

뒤쪽 절반, 즉 존재와 유일성은 $x^{q}-x$ 라는 다항식 하나가 처리한다. $\mathbb{F}_p$ 위에서 이 다항식의 분해체가 정확히 $q$ 개의 근을 갖고 그 근들의 집합이 체를 이루며(프로베니우스가 체 준동형이라 근의 집합이 사칙연산에 닫힌다), 분해체는 동형을 무시하면 유일하다.

따라서 $GF(6)$ 이나 $GF(10)$ 은 없다. 원소가 6개인 체를 만들려는 시도는 반드시 실패한다. 반면 $GF(4)$ 는 존재하고, $\mathbb{Z}/4\mathbb{Z}$ 와는 다른 물건이다 — 후자는 $2 \cdot 2 = 0$ 이라 영인자가 있어 체가 아니다. ”$GF(p^n)$ 은 $\mathbb{Z}/p^n\mathbb{Z}$ 가 아니다”가 이 바닥의 첫 번째 함정이다.

부분체 구조도 깔끔하다. $\mathbb{F}_{p^m} \subseteq \mathbb{F}_{p^n}$ 인 것과 $m \mid n$ 인 것이 동치다. 즉 $GF(2^{12})$ 는 $GF(2), GF(4), GF(8), GF(16), GF(64)$ 를 부분체로 갖고 그게 전부다.

3. 만드는 법 — 소수체 위의 기약다항식[편집]

실제 구현에서 $GF(p^n)$ 은 다항식 나머지환으로 만든다. $\mathbb{F}_p$ 계수의 $n$ 차 기약다항식(irreducible polynomial) $m(x)$ 를 하나 고르면

$$GF(p^n) \;\cong\; \mathbb{F}_p[x] \big/ \bigl(m(x)\bigr)$$

이다. 원소는 차수 $n$ 미만의 다항식 $a_{n-1}x^{n-1}+\cdots+a_0$ 이고, 계수 벡터를 그대로 저장하면 된다. 덧셈은 계수별 $\mathbb{F}_p$ 덧셈(따라서 $p=2$ 면 그냥 XOR), 곱셈은 다항식 곱한 뒤 $m(x)$ 로 나눈 나머지, 역원은 확장 유클리드 알고리즘으로 $a(x)s(x)+m(x)t(x)=1$ 을 풀어 $s(x)$ 를 취한다.

기약다항식은 흔하다. 차수 $n$ 인 모닉 기약다항식의 개수는 뫼비우스 반전으로

$$N_p(n) = \frac{1}{n}\sum_{d \mid n} \mu(d)\, p^{n/d} \;\approx\; \frac{p^n}{n}$$

이므로, 무작위로 고른 $n$ 차 다항식이 기약일 확률이 대략 $1/n$ 이다. 기약다항식을 찾는 일은 소수를 찾는 일보다 쉽다. 어떤 것을 고르든 결과 체는 동형이므로 선택은 순전히 구현 편의(비트 수, 삼항식 여부, 하드웨어 명령어 지원)의 문제다.

4. 곱셈군은 순환군이다[편집]

유한체를 계산에 쓸 수 있게 만드는 결정적 사실.

$\mathbb{F}_q^{\times} = \mathbb{F}_q \setminus \{0\}$ 는 위수 $q-1$ 의 순환군이다.

즉 어떤 원소 $\alpha$ 하나가 존재해 0이 아닌 모든 원소가 $\alpha^0, \alpha^1, \dots, \alpha^{q-2}$ 로 전부 나온다. 이런 $\alpha$ 를 원시원소(primitive element)라 하고, 개수는 $\varphi(q-1)$ 개다. 증명은 “유한 아벨군에서 최대 위수 원소가 모든 원소의 위수를 나눈다 + $x^d=1$ 의 근이 최대 $d$ 개”의 조합인데, 뒤쪽이 체이기 때문에 성립한다는 것이 요점이다.

이것이 곧바로 로그/안티로그 표를 낳는다. 원시원소 $\alpha$ 를 고정하고

• antilog[i] = $\alpha^i$ (길이 $q-1$)
• log[a] = $\alpha^a$ 를 만드는 지수 $i$ (길이 $q$)

두 배열을 미리 만들어 두면 곱셈과 나눗셈이 정수 덧셈·뺄셈으로 바뀐다.

$$a \cdot b = \text{antilog}\bigl[(\log a + \log b) \bmod (q-1)\bigr], \qquad a^{-1} = \text{antilog}\bigl[(q-1-\log a) \bmod (q-1)\bigr]$$

$GF(2^8)$ 이면 표 두 개가 각각 255·256바이트라 L1 캐시에 통째로 들어간다. 로그표 방식의 유일한 약점은 덧셈이 표에서 벗어난다는 것인데(지수 표현에서 덧셈은 자명하지 않다), 여기에는 $\alpha^{Z(k)} = 1 + \alpha^k$ 로 정의되는 체흐 로그(Zech logarithm) 표를 추가로 두는 고전적 처방이 있다. 표 크기가 부담되면 그냥 표현을 왔다 갔다 한다.¹

주의할 것 하나. 기약다항식이라고 해서 $x$ 가 원시원소인 것은 아니다. 기약이면서 $x$ 가 곱셈군을 생성하는 다항식을 따로 원시다항식(primitive polynomial)이라 부른다. 실제 사례가 바로 아래에 있다.

5. 프로베니우스 자기동형사상[편집]

표수 $p$ 의 세계에서는 이항정리의 중간항이 전부 $p$ 로 나누어떨어져 사라진다. 그래서

$$(a+b)^p = a^p + b^p$$

이 성립한다. 초심자가 저지르는 “신입생의 꿈”이 여기서만은 정리다. 이 덕에

$$\sigma : \mathbb{F}_{p^n} \to \mathbb{F}_{p^n}, \qquad \sigma(a) = a^p$$

가 체 자기동형사상이 되고, 이것을 프로베니우스 사상이라 한다. 성질 세 가지만 챙기면 된다.

• $\sigma$ 의 고정점 집합은 정확히 소수체 $\mathbb{F}_p$ 다. 즉 $a^p = a \iff a \in \mathbb{F}_p$ (페르마 소정리의 체 버전).
• $\sigma$ 의 위수는 $n$ 이고, 갈루아군 $\mathrm{Gal}(\mathbb{F}_{p^n}/\mathbb{F}_p) = \langle \sigma \rangle \cong \mathbb{Z}/n\mathbb{Z}$ 는 순환군이다. 유한체의 갈루아 이론이 정수 나눗셈으로 환원되는 이유이며, 갈루아 대응이 이보다 단순할 수 없다.
• $\alpha$ 의 최소다항식의 근은 $\alpha, \alpha^p, \alpha^{p^2}, \dots$ 라는 켤레(conjugate) 들이다.

마지막 항목이 부호이론에서 매일 쓰인다. 이진 BCH 부호를 설계할 때 “근으로 $\alpha^1, \alpha^3, \alpha^5, \dots$ 를 요구했더니 켤레인 $\alpha^2, \alpha^4, \alpha^6$ 도 자동으로 딸려 온다”는 계산이 정확히 프로베니우스 궤도(cyclotomic coset)를 세는 일이다. 계수를 $\mathbb{F}_2$ 로 유지하려면 생성다항식이 켤레 전체를 근으로 가져야 하기 때문이다.

6. GF(2^8)과 계산 — AES가 대표 사례[편집]

바이트 하나가 원소 하나에 대응해서 $GF(2^8)$ 이 실무의 압도적 주력이다. 덧셈이 XOR이고 원소가 uint8_t 하나라 구현이 사실상 공짜다.

AES의 유한체는 다음 기약다항식으로 정의된다.

$$m(x) = x^8 + x^4 + x^3 + x + 1 \qquad (\text{0x11B})$$

곱셈의 기본 연산은 $x$ 를 곱하는 xtime — 왼쪽으로 1비트 밀고, 8번째 비트가 넘치면 0x1B 를 XOR한다. 일반 곱셈은 이 연산과 XOR을 8번 반복하는 러시아 농부 곱셈이다. AES에서 유한체가 실제로 쓰이는 곳은 두 군데다.

• S-box. $GF(2^8)$ 에서의 곱셈 역원($0 \mapsto 0$)을 취한 뒤 $\mathbb{F}_2$ 위의 아핀변환을 한 번 건다. 역원 사상이 비선형성(차분·선형 특성)을 담당하고, 아핀변환은 역원 사상의 대수적 구조가 지나치게 깔끔한 것을 흐트러뜨린다.
• MixColumns. 4바이트 열을 $GF(2^8)$ 계수의 다항식으로 보고 $x^4+1$ 을 법으로 고정된 다항식 $\mathtt{03}x^3+\mathtt{01}x^2+\mathtt{01}x+\mathtt{02}$ 를 곱한다. 순환행렬 곱이라 확산(diffusion)을 담당한다.

여기서 앞 절의 경고가 실물로 확인된다. AES의 0x11B는 기약이지만 원시다항식이 아니다. 실제로 $x$(= 0x02)의 곱셈 위수는 255가 아니라 51이고, $x+1$(= 0x03)이 곱셈군을 생성한다. 그래서 AES 필드에 로그표를 만들려면 밑을 0x03으로 잡아야 한다. 참고로 QR 코드가 쓰는 $x^8+x^4+x^3+x^2+1$(0x11D)은 원시다항식이라 0x02가 그대로 생성원이다 — 같은 $GF(2^8)$ 이지만 표현이 다르면 로그표도 다르다는, 동형과 동일이 다르다는 사실의 실무적 귀결이다.²

하드웨어 지원. 캐리 없는 곱셈(carry-less multiplication)은 $\mathbb{F}_2[x]$ 의 다항식 곱 그 자체이고, x86의 PCLMULQDQ(CLMUL) 명령이 64비트 다항식 곱을 한 번에 처리한다. AES-GCM의 GHASH는 $GF(2^{128})$ (약다항식 $x^{128}+x^7+x^2+x+1$) 위의 곱셈이라 CLMUL 하나로 수십 배 빨라지고, CRC 계산도 같은 명령으로 가속된다. ARM에는 PMULL 이 대응한다. “유한체 곱셈”이 CPU 명령어로 존재하는 시대라는 점이 이 구조의 실용성을 말해 준다.

7. 오류정정 — 리드-솔로몬과 BCH[편집]

유한체가 세상에서 가장 많이 실행되는 용도. **리드-솔로몬 부호**의 아이디어는 한 줄이다 — 데이터 $k$ 심볼을 $\mathbb{F}_q$ 계수 다항식의 계수로 놓고, 그 다항식을 서로 다른 $n$ 개 점에서 평가한 값을 보낸다. 차수 $k-1$ 이하 다항식은 서로 다른 $k$ 개 점의 값으로 유일하게 결정되므로($GF$ 위의 라그랑주 보간, 크라메르 법칙의 반데르몽드 판), 임의의 $k$ 심볼만 살아남아도 복원된다. 결과적으로

$$d_{\min} = n - k + 1$$

로 싱글턴 한계를 등호로 달성한다(MDS 부호). 지워짐(erasure)은 $n-k$ 개까지, 위치를 모르는 오류는 $\lfloor (n-k)/2 \rfloor$ 개까지 고친다. 정확 산술이 아니었다면 “정확히 복원”이라는 말 자체가 성립하지 않는다는 점이 핵심이다.

• CD: CIRC — $GF(2^8)$ 위의 RS(32,28)과 RS(28,24)를 인터리빙으로 겹쳤다. 손톱만 한 긁힘이 수천 비트를 날려도 인터리빙이 그 손상을 여러 코드워드에 흩뿌리고, 각 코드워드는 자기 몫만 고치면 된다.
• QR 코드: $GF(2^8)$ 위의 RS. 오류정정 레벨 L/M/Q/H가 각각 대략 7/15/25/30%의 심볼 손상을 견딘다. 코드 한복판에 로고를 얹어도 읽히는 이유.
• 보이저 탐사선: RS(255,223)을 컨볼루션 부호와 연접(concatenate)했다. 심우주 통신의 표준 구성.
• NAND 플래시·SSD: 이진 BCH 또는 LDPC. 셀 미세화로 원시 비트오류율이 올라갈수록 ECC 강도가 함께 올라간다.

BCH 부호는 더 일반적인 틀이다. $\mathbb{F}_q$ 위의 순환부호를 만들되 생성다항식이 연속한 거듭제곱 $\alpha^b, \alpha^{b+1}, \dots, \alpha^{b+\delta-2}$ 를 근으로 갖게 하면 최소거리가 $\delta$ 이상임이 보장된다(BCH 한계). 리드-솔로몬은 $n = q-1$ 이고 심볼 알파벳이 곧 $\mathbb{F}_q$ 인 BCH의 특수한 경우다.

복호 절차는 전부 유한체 선형대수다. 수신어에 패리티 근을 대입해 신드롬을 구하고, 신드롬으로 세운 키 방정식을 버레캠프-매시 알고리즘(또는 확장 유클리드)으로 풀어 오류위치 다항식을 얻고, 그 근을 치엔 탐색으로 전수조사하고, 오류 크기는 포니 공식으로 계산한다. 이 파이프라인 어디에도 부동소수점이 없고, 따라서 “거의 맞다”가 없다. 고쳤거나 못 고쳤거나 둘 중 하나다.

8. 유한체 위의 선형대수 — 반올림이 아예 없다[편집]

$\mathbb{F}_q$ 위에서 가우스 소거법을 돌리면 부동소수점 수치해석의 걱정거리가 통째로 증발한다.

• 피벗팅은 안정성이 아니라 “0이 아닌 원소 찾기”용이다. 부분 피벗팅의 목적이 성장인자 억제였던 것과 달리, 여기서는 그냥 나눌 수 있는 원소를 찾는 것이 전부다.
• 랭크·영공간이 정확히 나온다. 부동소수점에서 랭크 판정은 특이값 절단이라는 임의의 문턱값 문제인데, 유한체에서는 이분법이다.
• 조건수라는 개념이 없다. 노름이 없으니 정의되지 않는다.

$\mathbb{F}_2$ 위에서는 덤이 더 붙는다. 원소가 비트 하나라 64개 열을 워드 하나에 담고, 행 소거가 그냥 XOR 한 번이다. 이 비트병렬성 덕에 $\mathbb{F}_2$ 위의 거대 희소행렬 소거가 실용 가능하고, 실제로 정수 인수분해(이차 체 체·수체 체)의 마지막 단계가 수백만 차원 $\mathbb{F}_2$ 선형계를 블록 비더만/블록 랑초스로 푸는 일이다. 네 러시아인의 방법(M4RI) 같은 전용 알고리즘도 따로 발달해 있다.

여기 조용히 숨어 있는 또 하나의 응용이 **난수 생성기**다. 메르센 트위스터·xorshift·WELL 계열은 상태 전이가 $\mathbb{F}_2$ 위의 선형사상이라, 주기가 $2^{19937}-1$ 이라는 것도 623차원 균등분포를 갖는다는 것도 실험이 아니라 $\mathbb{F}_2$ 선형대수로 증명된 명제다. 같은 선형성이 상태 복원 공격의 원인이라는 것까지가 세트다.

9. 정확해로 가는 우회로 — 소수체 계산 + CRT[편집]

유한체가 수치해석 문서에 실릴 자격을 얻는 대목이 여기다. 정수·유리수 계수 문제의 정확해를 유한체를 경유해서 구한다.

정수 행렬 $A \in \mathbb{Z}^{n\times n}$ 의 행렬식을 정확히 구한다고 하자. 유리수 산술로 소거하면 중간 항의 분자·분모가 지수적으로 부풀어 계산이 죽는다(중간식 팽창, intermediate expression swell). 표준 처방은 이렇다.

1. 아다마르 한계로 $|\det A| \le \prod_j \|\mathbf a_j\|_2$ 를 계산해 답의 크기 상한 $B$ 를 잡는다.
2. $\prod_i p_i > 2B$ 가 되도록 기계어 워드에 들어가는 소수 $p_1,\dots,p_k$ 를 고른다.
3. 각 $\mathbb{F}_{p_i}$ 에서 $\det A \bmod p_i$ 를 $O(n^3)$ 소거로 구한다. 각 계산은 오버플로 없는 정수 연산뿐이고 서로 완전히 독립이라 병렬화가 자명하다.
4. **중국인 나머지 정리**로 $\det A \bmod \prod p_i$ 를 복원하고, 대칭 잉여계로 부호를 붙여 정수 답을 읽는다.

선형계 $A\mathbf x = \mathbf b$ 의 유리수 해도 같은 방식이다. 각 소수체에서 풀어 CRT로 $\mathbf x \bmod M$ 을 얻은 뒤, 유리수 복원(rational reconstruction)으로 $|a|,|b| \lesssim \sqrt{M/2}$ 인 $a/b \equiv x \pmod M$ 을 확장 유클리드로 찾아 유리수를 되살린다. 크라메르 법칙이 유리식으로 답을 표현하는 것과 궁합이 좋고, 대안으로는 $p$-진 리프팅(딕슨 알고리즘)이 있다.

주의할 함정은 불운한 소수(unlucky prime)다. $p \mid \det A$ 이면 $\mathbb{F}_p$ 에서 행렬이 특이해져 랭크 정보가 틀어진다. 그런 소수는 유한개이므로 결과가 어긋나는 것을 탐지해 버리고 새 소수를 뽑으면 되며, 실용적으로는 소수를 하나 더 써서 검증한다. 컴퓨터 대수 시스템이 정수 행렬식·그뢰브너 기저·종결식·다항식 인수분해를 계산할 때 내부에서 상시 돌리는 것이 이 모듈러 전략이고, 스미스 표준형이나 유리 표준형처럼 정확 산술이 본질인 계산도 마찬가지다.

한 줄로 정리하면 — 유한체는 “근사가 아니라 정확이 필요한 자리”의 산술 기반이다. 부동소수점이 크기와 근사를 주는 대신 정확성을 포기했다면, 유한체는 정반대의 거래를 했다. 어느 쪽이 옳은지는 문제가 정한다.³

10. 관련 문서[편집]

• 크라메르 법칙 · 행렬식 · 가우스 소거법 · LU 분해
• 컴퓨터 대수 시스템 · 중국인 나머지 정리 · 리드-솔로몬 부호
• 스미스 표준형 · 유리 표준형 · 최소다항식
• 난수 생성기 · 메르센 트위스터 · 이산 로그
• 부동소수점 연산 · 조건수 · 희소행렬
• 브론스키 행렬식 · 전체 단모듈성

11. Footnotes[편집]

1. 체흐 로그는 야코비 로그라고도 부른다. $\alpha^m + \alpha^n = \alpha^n(1+\alpha^{m-n}) = \alpha^{n + Z(m-n)}$ 이라 지수 표현만으로 덧셈이 처리되는데, 표 크기가 $q$ 에 비례해서 $GF(2^{16})$ 정도부터는 캐시를 벗어난다. 그래서 현대 구현은 표를 버리고 CLMUL 명령으로 다항식 곱을 직접 때리는 쪽으로 갔다. 룩업 테이블이 곱셈보다 빨랐던 시절의 유물이 하드웨어의 발전으로 뒤집힌 흔한 사례. ↩

2. 갈루아 본인은 이 구조를 1830년경 열아홉 살에 정리해 두고 스물한 살에 결투로 죽었다. 결투 전날 밤 친구에게 쓴 편지에 “시간이 없다(Je n’ai pas le temps)“고 여백에 적어 두었다는 일화가 유명한데, 사실 그 문구는 다른 원고의 여백이고 편지 자체는 꽤 침착하다. 어느 쪽이든 유한체에 그의 이름이 붙은 것은 정당하다 — 존재·유일성·곱셈군의 순환성이 전부 그의 노트에 있다. ↩

3. 그래서 “유한체로 CFD를 풀 수 있나”라는 질문의 답은 아니오다. 미분·극한·수렴이 전부 위상에 기대는데 유한체에는 위상이 없다. 다만 유한체 위의 이산 구조가 시뮬레이션에 전혀 안 나오는 것은 아니어서, 셀룰러 오토마타나 $\mathbb{F}_2$ 기반 격자 기체 모형처럼 상태공간 자체가 유한체인 모형은 실제로 있다. 그런 경우엔 반올림 오차가 정확히 0이라는 성질이 그대로 시뮬레이션의 재현성으로 이어진다. ↩