Investigation of the computational complexity of generating checksums for the CRC algorithm depending on the width of the generating polynomial

Turdiev Odilzhan Akramovich

Statement of the problem: The need to ensure the integrity of data transmitted in communication networks makes the issue of ensuring the formation of checksums actual. At the same time, it is advisable to reduce the complexity of algorithms for generating checksums to increase data integrity. The well-known CRC (Cyclic Redundancy Code) checksum generation algorithm has high computational complexity. The aim of the work is to perform search studies to substantiate the fundamental possibility of reducing the computational complexity of the algorithm for generating CRC checksums and searching for possible ways of practical implementation. The scientific novelty of the research lies in the fact that the first considers the computational complexity of the CRC algorithm depending on the generating polynomials and their bit width.

Keywords:computational complexity, generator polynomial, cyclic redundancy code, batch errors, erroneous bits, integrity.