Вопрос. Алгоритм CRC базируется на свойствах деления с остатком двоичных многочленов, то есть многочленов над конечным полем

Алгоритм CRC базируется на свойствах деления с остатком двоичных многочленов, то есть многочленов над конечным полем . Значение CRC является остатком от деления многочлена, соответствующего входным данным, на некий фиксированный порождающий многочлен.

Каждой конечной последовательности битов взаимно однозначно сопоставляется двоичный полином , последовательность коэффициентов которого представляет собой исходную последовательность. Например, последовательность битов 1011010 соответствует многочлену:

Количество различных многочленов степени меньшей равно , что совпадает с числом всех двоичных последовательностей длины .

Значение контрольной суммы в алгоритме с порождающим многочленом G(x) степени N определяется как битовая последовательность длины N, представляющая многочлен R(x), получившийся в остатке при делении многочлена P(x), представляющего входной поток бит, на многочлен G(x):

где

— многочлен, представляющий значение CRC.

— многочлен, коэффициенты которого представляют входные данные.

— порождающий многочлен.

— степень порождающего многочлена.

Умножение осуществляется приписыванием нулевых битов к входной последовательности, что улучшает качество хеширования для коротких входных последовательностей.

При делении с остатком исходного многочлена на порождающий полином G(x) степени N можно получить 2^N различных остатков от деления. G(x) всегда является неприводимым многочленом. Обычно его подбирают в соответствии с требованиями к хэш-функции в контексте каждого конкретного применения.