cho.sh

체크섬 (Checksum)

아직 제출이 없습니다시간 제한1초메모리 제한128 MB

문제

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

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

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

입력

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

출력

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

힌트

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

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

  • 1+1=0+0=01 + 1 = 0 + 0 = 0 이고 1+0=0+1=11 + 0 = 0 + 1 = 1
  • 1⋅0=0⋅1=0⋅0=01 \cdot 0 = 0 \cdot 1 = 0 \cdot 0 = 0 이고 1⋅1=11 \cdot 1 = 1

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

F2\mathbb{F}_2를 계수로 갖는 다항식에 대한 연산도 똑같이 수행한다. 예를 들어 (x3+x+1)(−x−1)=(x3+x+1)(x+1)=x4+x2+x+x3+x+1=x4+x3+x2+1(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이다. 예를 들어 100100, 110110, 10001000은 각각 합성수인 44, 66, 88의 이진 표현이다.

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

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