Kod kontrolny CRC jest ciągiem bitów dodawanym do pliku lub wysyłanej informacji aby umożliwić późniejsze wykrycie przekłamania danych.

Obliczanie CRC opiera się na obliczaniu reszty z dzielenia wielomianu przez wielomian, przy czym współczynniki tych wielomianów są elementami ciała Z₂ reszt modulo 2 (czyli 0 i 1, operacje arytmetyczne wykonywane modulo 2, więc np. x+x=(1+1)x=0x=0). Wielomiany takie możemy reprezentować jako ciągi binarne, w ten sposób, że wielomian w(x) stopnia k reprezentujemy za pomocą ciągu (k+1)-bitowego, w którym kolejne pozycje odpowiadają kolejnym współczynnikom wielomianu, przy czym pierwszy z lewej bit odpowiada współczynnikowi przy x^k. W ten sposób możemy wzajemnie jednoznacznie wyznaczyć na podstawie wielomianu liczbę binarną,np.

x⁷+x⁵ +x¹+1 <=> 10100011₂ <=> 163₁₀

W najprostszej wersji obliczanie CRC wygląda następująco:

1. Mamy ustalony z góry wielomian p(x) stopnia k.
2. Wpierw na podstawie danych, dla których ma być obliczone CRC, jest tworzony wielomian w(x) w ten sposób, że dane traktowane są jako długa liczba binarna, do której dopisujemy k zer z prawej i na podstawie tego ciągu wyznaczamy w(x).
3. Obliczana jest reszta r(x) z dzielenia w(x) przez p(x).
4. Reszta r(x) jest kodem CRC, kórego reprezentacja binarna jest doklejana do danych.

Wejście

W pierwszym wierszu podana jest liczba testów, każdy kolejny wiersz zawiera jeden test.

Każdy test składa się z liczby zapisanej szesnastkowo (co najwyżej 8 cyfr), reprezentującej wielomian p(x) oraz, po spacji, łańcucha znaków (bez białych znaków, max. 10 000 znaków) dla którego ma być obliczone CRC.

Wyjście

Na wyjściu należy podać kody CRC w postaci liczb zapisanych szesnastkowo, po jednym w każdym wierszu.

Przykład

Wejście:
4
11021 Pan_kotek_byl_chory
12021 i_lezal_w_lozeczku
1BABA i_przyszedl_pan_doktor,
1AAAA "Jak_sie_masz,_Koteczku?"

Wyjście:
E53D
A98D
1E8A
573C

Bibliografia

1. Kalkulator CRC
2. Wikipedia