체크섬 (Checksum)

전송되는 데이터의 정확성을 보장하기 위해, 데이터에 체크섬(checksum)을 덧붙이기도 한다. 다음과 같은 방식으로 체크섬을 계산한다고 하자.

비트 문자열로 주어진 메시지 $M$이 있을 때, 역시 비트 문자열인 체크섬 생성기 $G$를 고른다. 그리고 $M$의 끝에 $G$의 비트 수보다 $1$ 적은 개수의 $0$을 덧붙여 확장된 메시지 $M'$을 만든다. $M'$과 $G$의 각 자리 비트를 체 $\mathbb{F}_2$ 위 다항식의 계수로 해석하면(가장 왼쪽 비트가 최고차항의 계수), $M'$에 대응하는 다항식을 $G$에 대응하는 다항식으로 나눈 나머지를 구할 수 있다. 이 나머지의 계수 열을 메시지 $M$의 체크섬이라고 부른다.

당신의 과제는 메시지 $M$의 체크섬을 계산하는 것이다. 다만 어떤 이유로, 생성기를 이진수로 해석한 값이 소수일 때 그 체크섬을 더 신뢰하므로, 이 경우에만 체크섬을 계산한다. 생성기가 소수가 아니라면 ERROR를 출력한다.

첫째 줄에 테스트 케이스의 수를 나타내는 정수 $T$ ($1 \le T \le 10^3$)가 주어진다. 이어지는 $T$개의 줄에는 각각 하나의 테스트 케이스가 주어지며, 각 케이스는 공백 하나로 구분된 두 개의 비트 문자열로 이루어진다. 첫 번째 비트 문자열은 메시지 $M$이고(길이는 $512$비트를 넘지 않는다), 두 번째 비트 문자열은 생성기 $G$이다(길이는 $48$비트를 넘지 않는다). $M$과 $G$에는 앞자리 $0$이 없다.

각 테스트 케이스마다 한 줄에, 해당 체크섬을 십진수로(앞자리 $0$ 없이) 출력한다. 단, 생성기가 소수가 아니라면 그 줄에는 ERROR를 출력한다.

체 $\mathbb{F}_2$에 대하여

$\mathbb{F}_2$는 집합 $\{0, 1\}$을 뜻하며, 다음과 같이 덧셈 $+$과 곱셈 $\cdot$을 정의한다.

• $1 + 1 = 0 + 0 = 0$ 이고 $1 + 0 = 0 + 1 = 1$
• $1 \cdot 0 = 0 \cdot 1 = 0 \cdot 0 = 0$ 이고 $1 \cdot 1 = 1$

또한 $\mathbb{F}_2$에서는 $-1 = 1$, $-0 = 0$이 성립한다. 따라서 어떤 수를 빼는 것은 그 수를 더하는 것과 같다는, 다소 놀라운 결론이 나온다. 예를 들어 $0 - 1 = 0 + 1 = 1$, $1 - 1 = 1 + 1 = 0$이다.

$\mathbb{F}_2$를 계수로 갖는 다항식에 대한 연산도 똑같이 수행한다. 예를 들어 $(x^3 + x + 1)(-x - 1) = (x^3 + x + 1)(x + 1) = x^4 + x^2 + x + x^3 + x + 1 = x^4 + x^3 + x^2 + 1$ 이다.

예시 풀이

생성기를 이진수로 해석한 값이 합성수이면 답은 ERROR이다. 예를 들어 $100$, $110$, $1000$은 각각 합성수인 $4$, $6$, $8$의 이진 표현이다.

생성기가 소수이면 체크섬을 계산한다. 예를 들어 $M = 1101$, $G = 10$이면 $M' = 11010$이고, 대응하는 다항식은 $W_{M'}(x) = x^4 + x^3 + x$, $W_G(x) = x$이다. $\mathbb{F}_2$ 위에서 $W_{M'}$을 $W_G$로 나누면 몫은 $x^3 + x^2 + 1$, 나머지는 $0$이므로 체크섬은 $0$이다.

또 $M = 1000$, $G = 11$이면 $M' = 10000$이고 $W_{M'}(x) = x^4$, $W_G(x) = x + 1$이다. 나누면 몫은 $x^3 + x^2 + x + 1$, 나머지는 $1$이므로 체크섬은 $1$이다.