갈루아체 GF(2ⁿ) 산술 계산기
비트열을 다항식으로 보고 더하기(XOR)·곱하기·나누기·역원을 계산합니다. 곱셈표와 로그표를 함께 보여 주고, 기약다항식이 아니면 왜 체가 되지 않는지 확인할 수 있습니다.
GF(2^m) — 원소가 2^m개인 체입니다. m = 8이면 바이트 하나가 원소 하나입니다. 2~8.
곱한 뒤 이 다항식으로 나눈 나머지를 답으로 삼습니다. 이것이 달라지면 곱셈표가 통째로 달라집니다.
0 ~ 255. 지금은 0x57 = 01010111₂ = x^6+x^4+x^2+x+1
0 ~ 255. 지금은 0x83 = 10000011₂ = x^7+x+1
a × b
0xC1 (193)
x^6+x^4+x^2+x+1 곱하기 x^7+x+1를 x^8+x^4+x^3+x+1로 나눈 나머지입니다.
로그표 — 곱셈을 덧셈으로
0이 아닌 원소는 생성원 g 하나의 거듭제곱으로 모두 만들어집니다. 그래서 g^i × g^j = g^((i+j) mod 255)이 되어 곱셈이 지수의 덧셈으로 바뀝니다. 임베디드 구현이 256×256 곱셈표 대신 로그표·역로그표 두 개만 들고 다니는 이유입니다.
생성원의 거듭제곱 (g = 0x03)
0x01 0x03 0x05 0x0F 0x11 0x33 0x55 0xFF 0x1A 0x2E 0x72 0x96 0xA1 0xF8 0x13 0x35 0x5F 0xE1 0x38 0x48 0xD8 0x73 0x95 0xA4 0xF7 0x02 0x06 0x0A 0x1E 0x22 0x66 0xAA 0xE5 0x34 0x5C 0xE4 0x37 0x59 0xEB 0x26 0x6A 0xBE 0xD9 0x70 0x90 0xAB 0xE6 0x31 0x53 0xF5 0x04 0x0C 0x14 0x3C 0x44 0xCC 0x4F 0xD1 0x68 0xB8 0xD3 0x6E 0xB2 0xCD …
255개를 한 번씩 빠짐없이 훑고 다시 처음으로 돌아옵니다. 0만 빠집니다 — 0은 아무리 곱해도 0이라 이 순환에 낄 수 없습니다.
사용 방법
- 1차수 m을 골라 GF(2^m)을 정합니다. m = 8이면 바이트 하나가 원소 하나입니다.
- 2기약다항식을 고릅니다. AES는 0x11B를 씁니다.
- 3a와 b를 넣어 더하기·곱하기·나누기·역원을 확인합니다.
- 4로그표에서 곱셈이 지수의 덧셈으로 바뀌는 것을 봅니다.
- 5작은 m에서는 곱셈표 전체를 훑어 0이 어디에만 있는지 확인합니다.
자주 묻는 질문
원소가 유한한데도 더하기·빼기·곱하기·나누기가 모두 되는 수 체계입니다. GF(2^m)은 m비트 비트열을 다항식으로 보고, 곱한 뒤 정해진 m차 기약다항식으로 나눈 나머지를 답으로 삼습니다. 0b1011은 x³+x+1입니다.
계수가 0 아니면 1이고 1+1 = 0이라 자리올림이 없기 때문입니다. 그래서 더하기와 빼기가 같은 연산이 되고, 부호라는 것이 아예 없습니다. a − b와 a + b가 둘 다 a XOR b입니다.
인수분해되는 다항식으로 나머지를 잡으면 0이 아닌 둘을 곱했는데 0이 되는 짝(영인자)이 생기기 때문입니다. 그러면 역원이 없는 원소가 생겨 나눗셈이 안 되고, 체가 아니라 환이 됩니다. 이 도구는 고른 다항식이 정말 기약인지 시험 나눗셈으로 직접 확인합니다.
x⁸+x⁴+x³+x+1, 16진수로 0x11B입니다. MixColumns 단계의 곱셈이 이 체에서 이뤄집니다. 리드–솔로몬 부호(QR 코드·CD)는 흔히 0x11D를 씁니다. 같은 GF(2^8)이라도 다항식이 다르면 곱셈표가 통째로 달라지므로, 다른 구현과 값을 견줄 때는 먼저 맞춰야 합니다.
곱셈을 덧셈으로 바꾸기 위해서입니다. 0이 아닌 원소는 생성원 g 하나의 거듭제곱으로 모두 만들어지므로 g^i × g^j = g^((i+j) mod (2^m−1))이 됩니다. 그래서 256×256 곱셈표(65,536칸) 대신 로그표와 역로그표 두 개(합쳐 511칸)만 들고 다니면 됩니다.
0에 무엇을 곱해도 0이라 1을 만들 수 없기 때문입니다. 보통의 수 체계에서 0으로 나눌 수 없는 것과 같은 이유이고, 갈루아체에서도 예외는 이것 하나뿐입니다. 0이 아닌 원소는 모두 역원을 정확히 하나씩 가집니다.
전송되지 않습니다. 계산은 모두 브라우저 안에서 이뤄지고, 입력한 값은 이 기기에만 남습니다.
알아두면 좋은 점
- 정답지는 AES 표준 문서(FIPS 197)의 예제입니다. 0x57 × 0x83 = 0xC1, 0x57 × 0x13 = 0xFE, xtime(0x57) = 0xAE, 0x53의 역원 = 0xCA를 검사에 박아 두었습니다.
- 체의 성질을 모든 원소 쌍에서 전수로 확인합니다. 닫힘·교환·항등, 0이 아닌 둘을 곱해 0이 되지 않는 것(영인자 없음), (a÷b)×b = a가 모든 짝에서 성립하는 것을 봅니다. 결합법칙과 분배법칙은 작은 체에서 세 원소를 전부 훑어 확인했습니다.
- 0이 아닌 원소가 역원을 「정확히 하나」 가지는 것을 세어 확인합니다. 두 개 이상이거나 없으면 체가 아닙니다.
- 기약 판정 자체도 검산합니다. 차수별 기약다항식 개수가 가우스 식 (1/m)Σμ(d)2^(m/d)와 같은지 1~12차에서 대조했습니다(8차는 30개).
- 생성원 개수가 오일러 피 함수 φ(2^m−1)과 같은 것, 생성원의 거듭제곱이 0을 뺀 원소 전부를 한 번씩 훑는 것, 곱셈이 로그표의 덧셈과 일치하는 것을 GF(2^8) 전체 쌍에서 확인했습니다.
- AES 다항식에서 3은 생성원이지만 2는 아니라는 것(2의 위수가 51)도 검사에 넣었습니다. 로그표의 밑을 3으로 잡는 구현이 많은 이유입니다.
- 차수는 2~8까지 다룹니다. 곱셈표 전체는 원소가 16개 이하일 때만 그립니다.
함께 보면 좋은 도구
마지막 검증: 2026년 9월 1일 · 결과는 참고용 추정치입니다.