mod 2 다항식 (Mod 2 Polynomial)

mod 2 다항식은 계수가 0 또는 1뿐이고 계수끼리의 계산을 2로 나눈 나머지로 하는 다항식입니다. 이런 다항식 전체는 다항식환 GF(2)[x]를 이룹니다. 비트열을 다항식의 계수로 보면(예: 1011 ↔ x³ + x + 1), 비트 연산과 다항식 대수를 같은 것으로 다룰 수 있습니다.

자세히 알아보기

덧셈과 뺄셈은 같은 연산이며, 각 자리 계수를 올림(carry) 없이 따로 더하므로 비트별 XOR와 같습니다. 곱셈은 보통의 다항식 곱셈을 하되 계수를 XOR로 합칩니다(무올림 곱셈). 나눗셈은 정수처럼 몫과 나머지가 생기며 나누어떨어지지 않을 수 있으므로, GF(2)[x]는 체가 아니라 환입니다.

정수의 소수에 해당하는 것이 기약 다항식입니다. 차수 n인 기약 다항식 P(x)로 나눈 나머지들의 집합은 2ⁿ개의 원소를 가진 유한체 GF(2ⁿ)이 됩니다. 기약 다항식 중에서도 x가 곱셈군 전체를 생성하는 것을 원시 다항식이라 하며, 이를 귀환 다항식으로 쓰는 LFSR은 최대 주기 2ⁿ − 1을 가집니다.

재미있는 성질로, mod 2에서는 (a + b)² = a² + b²이므로 다항식의 제곱은 각 계수 사이에 0을 끼워 넣는 것과 같습니다. 예를 들어 (x + 1)² = x² + 1입니다.

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

• CRC와 오류 검출: CRC-32는 데이터를 mod 2 다항식으로 보고 생성 다항식으로 나눈 나머지를 체크값으로 씁니다. 다만 CRC는 선형이어서 의도적 변조를 막지 못하므로, 무결성 보호에는 해시나 MAC을 써야 합니다.
• 비트코인 주소 체크섬: Bech32·Bech32m 주소(bc1…)의 체크섬은 GF(32) 위의 BCH 부호로, mod 2 다항식 대수를 확장한 구조입니다. 4글자 이하의 오류는 반드시 감지하도록 설계되었습니다.
• AES와 GCM: AES의 바이트 곱셈은 x⁸ + x⁴ + x³ + x + 1을 법으로 하는 GF(2⁸) 연산이고, AES-GCM의 GHASH는 x¹²⁸ + x⁷ + x² + x + 1을 법으로 하는 GF(2¹²⁸) 곱셈입니다. 최신 CPU는 이를 위해 무올림 곱셈 명령(PCLMULQDQ 등)을 제공합니다.

쉽게 말하면

mod 2 다항식은 '받아올림이 없는 이진수 계산'입니다. 1 + 1 = 0이 되고 다음 자리로 넘어가지 않습니다.

예시

(x³ + x + 1) + (x² + x) = x³ + x² + 1(1011 XOR 0110 = 1101). (x + 1)(x + 1) = x² + 2x + 1 = x² + 1입니다.