Ожидаемые столкновения для идеального 32-битного CRC

Question

Я пытаюсь определить, как мой CRC сравнивается с " идеальным " 32-битным CRC.

Итак, я запустил свой crc более 1 миллиона совершенно случайных выборок данных и собрал количество столкновений. Я хочу сравнить это число с количеством столкновений, которое я мог бы ожидать от " идеально "crc.

Кто-нибудь знает, как рассчитать ожидаемое столкновение для" идеального"32-битного crc?

Answer 1

Сравните ваш собственный CRC с 0x1EDC6F41 как с вашим "идеальным" эталоном.

Сказав это, не существует идеального 32-битного CRC. Различные полиномы имеют разные характеристики столкновения в зависимости от длины хешируемых данных. Однако в работе Кастаньоли в 1993 году было установлено, что считается лучшим 32-разрядным значением CRC в самом широком диапазоне длин данных, который равен 0x1EDC6F41. Этот полином используется некоторыми сетевыми протоколами, такими как iSCSI, а также инструкцией x86 CRC32.

Answer 2

Это прекрасно объясняет «проблему дня рождения» и все о предсказании вероятности коллизии CRC32 вероятность хэширования