갈루아 체 (Galois Field)

갈루아 체(Galois Field)는 원소의 개수가 유한하면서 덧셈·뺄셈·곱셈·0이 아닌 수로의 나눗셈이 모두 자유롭게 정의되는 체(field)입니다. 유한체(finite field)라고도 하며, 영어 발음대로 '갈루아 필드'라고도 부릅니다. 원소 수 q는 반드시 소수 p의 거듭제곱 p^k이고, 같은 크기의 유한체는 본질적으로 하나뿐이어서 GF(q), GF(p^k) 또는 𝔽_q로 표기합니다. 이름은 19세기 수학자 에바리스트 갈루아에서 왔습니다.

자세히 알아보기

체는 유리수나 실수처럼 사칙연산이 항상 가능한 수 체계입니다. 체 안의 두 원소를 더하거나 곱한 결과는 항상 같은 체의 원소이고, 모든 원소는 덧셈 역원을, 0이 아닌 모든 원소는 곱셈 역원을 가집니다. 갈루아 체는 이런 성질을 유한한 원소 집합 안에서 그대로 갖춘 것이어서, 컴퓨터가 반올림 오차 없이 정확한 값으로 계산할 수 있습니다.

가장 단순한 갈루아 체는 소수 p에 대한 GF(p)로, 0부터 p−1까지의 정수에 p를 법으로 하는 덧셈과 곱셈을 적용한 것입니다. 예를 들어 GF(7)에서 5 + 4 = 9 ≡ 2이고, 3 × 5 = 15 ≡ 1이므로 3의 곱셈 역원은 5입니다. p가 소수이기 때문에 0이 아닌 모든 원소가 역원을 가지며, 이것이 체가 되는 핵심 조건입니다. 반면 원소 수가 6처럼 소수의 거듭제곱이 아니면 체가 만들어지지 않습니다. 6을 법으로 하면 2 × 3 = 0이 되어 2와 3에는 곱셈 역원이 없기 때문입니다.

k ≥ 2인 GF(p^k)는 정수의 나머지 연산만으로는 만들 수 없고, GF(p) 계수의 다항식을 차수 k인 기약 다항식(더 이상 인수분해되지 않는 다항식)으로 나눈 나머지로 구성합니다. 컴퓨터에서 특히 중요한 것은 GF(2ⁿ)입니다. 원소를 n비트 문자열로 표현할 수 있고, 덧셈은 비트별 XOR, 곱셈은 다항식 곱셈 후 기약 다항식으로 나머지를 취하는 연산이 되어 올림(carry)이 없습니다.

유한체에서는 0이 아닌 원소들이 곱셈에 대해 순환군을 이룬다는 성질이 있습니다. 그래서 생성원(원시원) 하나의 거듭제곱으로 모든 원소를 표현할 수 있고, 이는 이산 로그 문제와 의사난수 수열(LFSR, m-수열) 설계의 기초가 됩니다.

블록체인·암호화폐에서는

• 타원곡선 암호: 비트코인·이더리움의 서명 곡선 secp256k1은 소수 p = 2²⁵⁶ − 2³² − 977 위의 GF(p)에서 정의됩니다. 개인 키로 공개 키를 계산하는 모든 점 연산은 이 체 위의 덧셈·곱셈·역원 계산입니다.
• AES: 거래소·지갑 백업 암호화에 쓰이는 AES는 바이트를 GF(2⁸) 원소로 보고, 기약 다항식 x⁸ + x⁴ + x³ + x + 1을 사용합니다. S-box는 GF(2⁸)의 곱셈 역원을 구한 뒤 아핀 변환을 적용한 것이고, MixColumns 단계도 이 체의 곱셈입니다. AES-GCM의 인증 부분(GHASH)은 GF(2¹²⁸) 곱셈입니다.
• 영지식 증명: zk-SNARK·STARK는 회로 전체를 큰 소수체 위의 다항식 방정식으로 바꿔 증명합니다. 이더리움 사전 컴파일 계약이 지원하는 BN254와 이더리움 합의 계층의 BLS 서명에 쓰이는 BLS12-381 곡선도 모두 유한체 위에서 정의됩니다.
• 오류 정정: 비트코인 Bech32 주소의 체크섬은 GF(32) 위의 BCH 부호입니다. 리드-솔로몬 부호는 주로 GF(2⁸)에서 동작하며 CD, DVD, QR 코드, 심우주 통신에서 손상된 데이터를 복원하고, 블록체인의 데이터 가용성 설계에도 사용됩니다.

쉽게 말하면

갈루아 체는 '숫자가 유한한 개수뿐인데도 사칙연산이 전부 깔끔하게 되는 세계'입니다. 시계처럼 한 바퀴 돌면 처음으로 돌아오지만, 나눗셈까지 항상 답이 하나로 정해집니다.

예시

GF(2⁸)에서 0x57 + 0x83 = 0xD4입니다(비트별 XOR). AES 표준(FIPS 197)의 예시처럼 0x57 × 0x83 = 0xC1이 되는데, 이는 다항식 곱셈 결과를 x⁸ + x⁴ + x³ + x + 1로 나눈 나머지입니다.